Difference between revisions of "Identify the class of the language"

Revision as of 13:53, 8 February 2014

1. $L = \{wxw | 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.

2. $L = \{wxw| w,x ∈ \{{a,b}\}^+\}$

Here, L is not generating all strings in <math>\Sigma^*</math> as the strings like abab are not generated by L. L is actually accepting 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>.

@@ Line 6: / Line 6: @@
 ===2.  $L = \{wxw| w,x ∈ \{{a,b}\}^+\}$===
-Here, L is not generating all strings in <math>\Sigma^*</math> as the strings like abab are not generated by L. Here, L accepts all strings except those of the form ww, w \in (a+b)^*. To do this is not possible with a PDA and we need a LBA making L CSL.
+Here, L is not generating all strings in <math>\Sigma^*</math> as the strings like abab are not generated by L. L is actually accepting 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>.
 .WW | such that W=(a+b)*