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

Line 5: Line 5:
  
 
===2.  $L = \{wxw| w,x ∈ \{{a,b}\}^+\}$===
 
===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.
+
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.
 +
 
 +
1.WW | such that W=(a+b)*
 +
2.WW | such that W=(a+b)+
 +
6.WWr | such that W=(a+b)*
 +
7.WWr| such that W=(a+b)+
 +
8.1.WXWr | such that W,X=(a+b)*
 +
9.WXWr | such that W,X=(a+b)+

Revision as of 13:52, 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. 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.

1.WW | such that W=(a+b)* 2.WW | such that W=(a+b)+ 6.WWr | such that W=(a+b)* 7.WWr| such that W=(a+b)+ 8.1.WXWr | such that W,X=(a+b)* 9.WXWr | such that W,X=(a+b)+

Retrieved from "https://gatecse.in/w/index.php?title=Identify_the_class_of_the_language&oldid=2340"

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, 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.