Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 8: | Line 8: | ||
Here, L is not generating all strings in <math>\Sigma^*</math> as the strings like abab are not generated by L. L is actually generating all strings except those of the form <math>ww, w \in (a+b)^*</math>. To do this is not we need at least an <math>LBA</math>, making <math>L</math>, a <math>CSL</math>. | Here, L is not generating all strings in <math>\Sigma^*</math> as the strings like abab are not generated by L. L is actually generating all strings except those of the form <math>ww, w \in (a+b)^*</math>. To do this is not we need at least an <math>LBA</math>, making <math>L</math>, a <math>CSL</math>. | ||
| − | + | ===3. $L = \{ww| w ∈ \{{a,b}\}^*\}$=== | |
| − | |||
| − | + | ===4. $L = \{ww| w ∈ \{{a,b}\}^+\}$=== | |
| − | |||
| − | + | ===5. $L = \{ww_R| w ∈ \{{a,b}\}^*\}$=== | |
| − | + | ||
| + | ===6. $L = \{ww_R| w ∈ \{{a,b}\}^+\}$=== | ||
| + | |||
| + | |||
| + | ===7. $L = \{wxw_R| w,x ∈ \{{a,b}\}^+\}$=== | ||
| + | |||
| + | |||
| + | ===8. $L = \{wxw_R| w,x ∈ \{{a,b}\}^+\}$=== | ||
Here, <math>L</math> can generate 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, L is not generating all strings in <math>\Sigma^*</math> as the strings like abab are not generated by L. L is actually generating all strings except those of the form <math>ww, w \in (a+b)^*</math>. To do this is not we need at least an <math>LBA</math>, making <math>L</math>, a <math>CSL</math>.
Here, <math>L</math> can generate 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, L is not generating all strings in <math>\Sigma^*</math> as the strings like abab are not generated by L. L is actually generating all strings except those of the form <math>ww, w \in (a+b)^*</math>. To do this is not we need at least an <math>LBA</math>, making <math>L</math>, a <math>CSL</math>.
GATECSE