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, L can generate all strings in <math>\Sigma</math>*, by making x = (a+b)* and w = \epsilon. Hence, L is regular.


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

Here, our problem is this- given a word s, whether it belongs to L or not. I say that a word belongs to L, iff it starts and end with a or starts and ends with b (and contains at least 3 letters in total). Now, in case of wxw, the same logic won't work. As you told if s ∈ {a (a+b)^+ a} U {b (a+b)^+ b}, then its of the form wxw. But if s ∉ {a (a+b)^+ a} U {b (a+b)^+ b}, we can't say its not of the form wxw. For example, take s as abbab, its of the form wxw with w = "ab" and x = "b". Thus the reduction will work only one way and hence it cannot be used.