View source for Identify the class of the language ← Identify the class of the language

You do not have permission to edit this page, for the following reason:

The action you have requested is limited to users in one of the groups: Users, Administrators.

You can view and copy the source of this page.

Templates used on this page:

Return to Identify the class of the language.

Retrieved from "https://gatecse.in/wiki/Identify_the_class_of_the_language"

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 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}\}^+\}$