Arjun Suresh (talk | contribs) (Created page with "==1) w,x ∈ {a,b}* is regular 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 st...") |
Arjun Suresh (talk | contribs) |
||
| Line 1: | Line 1: | ||
| − | == | + | == $w,x ∈ {a,b}* $== |
| Line 6: | Line 6: | ||
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. | 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. | ||
| − | ==2) w,x ∈ {a,b}+ | + | ==2) $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.
==1) w,x ∈ {a,b}* is regular
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.
GATECSE