edited by
4,185 views
2 votes
2 votes
The language given is $\text{$L = \{ w | w $ contains an equal no of occurrences of substrings '$ab'$ and $'ba' \}.$ }$ $L$ is regular $?$

Note$:-$   $aba ∈ L $since $'aba'$ contains $1$ occurrence of $'ab'$ and $1$ occurrence of $'ba'$ but $ abab ∉ L$
edited by

3 Answers

Best answer
6 votes
6 votes

Yes it is regular ..The reason being we have equivalent regular expression for it..The regular expression for the given language is given by :

(a+ b* a+) *  + (b+ a* b+)* 

Hence we can have equivalent NFA and DFA also..

Thus the given langauge is regular

selected by
0 votes
0 votes
In order to check the whether there are equal occurences of two distinct expressions in a string there should be some way for us to maintain the count of each expression. And taking into account that this is an infinite relation (as there is no bound to the count ) this language is not regular. And this can also proven by pumping lemma.

A very simple example as you might already know.

L= { a^n b^n | n>=1} represents a relation which is not bound and hence it is not regular.

 On the other hand.

L= {a^n b^n| n<=3} represents a bounded finite relation and hence is regular.
0 votes
0 votes
answer : language is regular

Explanation :

if you observe the language, once u get 'ab' then on the next string u could get am 'a' or 'b' making 'ba' or waiting for 'a' because on the input 'b' again. So at any point of time u can have the difference of 'ab' and 'ba' to be at most 1, not more than that. thus reducing the power of the language of a regular language.

Please comment below if further clarification is needed. i will explain u with a DFA .

Related questions

0 votes
0 votes
1 answer
4
Purple asked Jan 12, 2017
423 views
Answe is B, but why is L2 not regular? How to solve it? For L2, $ y=x^{1/n}$ I am not understanding why is this not right?