5,472 views
3 votes
3 votes

We can say there are four types of strings in the language so the regex will be: a(a+b)+a + b(a+b)+b + a(a+b)+b + b(a+b)+a  Please expleain where I am wrong

3 Answers

3 votes
3 votes

 L = { w x w ∣ w , x ∈ ( a + b ) + }

In the above language w,x belongs to (a+b)+ so w and x can take any value like  a,b,ab,ba,aa,bb,aba,bab,bba,bbb,aaa,aab,bba......

Here the main thing to notice is that the language will contain strings which is made up of total three parts in which the first part and the last part are same and the middle part can be anything like {aaa,aba,bab,bbb,bbabb, aabbbaa,abbbab, baabba ....}

which can be seen like this a-a-a, a-b-a, b-a-b, b-bab-b,  aa-bbb-aa, ab-bbb-ab, ba-ab-ba  where first and third parts are identical so we need some matching mechanism because of strings of type ab-bbb-ab and ba-ab-ba we cant solve it using PDA so we need TM for this so the language is not regular.

edited by
0 votes
0 votes
here the value of X in unbounded so we can take length of X as we like but until this condition satisfies

like W != phi; soo, as X value is unbounded no comparesion and storing, counting doesnt takes place  over the W .so its an REGULAR grammer

if X value bounded like |X| =2 then automatically it is an  NON REGULAR GRAMMER

i think is X is bounded then it bcomes DETERMINISTIC CONTEXT FREE GRAMMER / LANGUAGE
0 votes
0 votes
ANY STRING OF LENGTH >= 3 IS ACCEPTED BY FA

Related questions

4 votes
4 votes
1 answer
2
Garrett McClure asked Oct 9, 2017
1,224 views
The tail of a language is the set of all suffixes of its strings, that is tail(L) = {y : xy ∈ L for some x ∈ Σ ∗ }.How do I show that the family of regular languag...
1 votes
1 votes
1 answer
3
7 votes
7 votes
2 answers
4