Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 6: | Line 6: | ||
===2. $L = \{wxw| w,x ∈ \{{a,b}\}^+\}$=== | ===2. $L = \{wxw| w,x ∈ \{{a,b}\}^+\}$=== | ||
| − | Here, <math>L</math> doesn't contain all strings in <math>\Sigma^*</math> as the strings like <math>abab</math> are not generated by <math>L</math>. We can see all words starting and ending in <math>a</math> or starting and ending in <math>b</math> are in <math>L</math>. But <math>L</math> also contains words starting with <math>a</math> and ending in <math>b</math> like <math>abbab, aabbbabaab</math> etc where the starting sub-string exactly matches the ending sub-string and at least a letter sperates them. To generate such strings we need at least an <math>LBA</math>, making <math>L</math>, a <math>CSL</math>. | + | Here, <math>L</math> doesn't contain all strings in <math>\Sigma^*</math> as the strings like <math>abab</math> are not generated by <math>L</math>. We can see all words starting and ending in <math>a</math> or starting and ending in <math>b</math> are in <math>L</math>. But <math>L</math> also contains words starting with <math>a</math> and ending in <math>b</math> like <math>abbab, aabbbabaab</math> etc where the starting sub-string exactly matches the ending sub-string and at least a letter sperates them. To generate such strings we need at least an <math>LBA</math> (this is at least as hard as generating <math>ww, w \in (a+b)^*</math>), making <math>L</math>, a <math>CSL</math>. |
===3. $L = \{ww| w ∈ \{{a,b}\}^*\}$=== | ===3. $L = \{ww| w ∈ \{{a,b}\}^*\}$=== | ||
Here, <math>L</math> contains all strings in <math>\Sigma^*</math>, by making <math>x = (a+b)^*</math> and <math>w = \epsilon</math>. Hence, <math>L</math> is regular.
Here, <math>L</math> doesn't contain all strings in <math>\Sigma^*</math> as the strings like <math>abab</math> are not generated by <math>L</math>. We can see all words starting and ending in <math>a</math> or starting and ending in <math>b</math> are in <math>L</math>. But <math>L</math> also contains words starting with <math>a</math> and ending in <math>b</math> like <math>abbab, aabbbabaab</math> etc where the starting sub-string exactly matches the ending sub-string and at least a letter sperates them. To generate such strings we need at least an <math>LBA</math> (this is at least as hard as generating <math>ww, w \in (a+b)^*</math>), making <math>L</math>, a <math>CSL</math>.
Here, <math>L</math> contains all strings in <math>\Sigma^*</math>, by making <math>x = (a+b)^*</math> and <math>w = \epsilon</math>. Hence, <math>L</math> is regular.
Here, <math>L</math> doesn't contain all strings in <math>\Sigma^*</math> as the strings like <math>abab</math> are not generated by <math>L</math>. We can see all words starting and ending in <math>a</math> or starting and ending in <math>b</math> are in <math>L</math>. But <math>L</math> also contains words starting with <math>a</math> and ending in <math>b</math> like <math>abbab, aabbbabaab</math> etc where the starting sub-string exactly matches the ending sub-string and at least a letter sperates them. To generate such strings we need at least an <math>LBA</math>, making <math>L</math>, a <math>CSL</math>.
GATECSE