Virtual Gate Test Series: Theory Of Computation - Regular Languages

Question

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$

Comments

It is regular

Answer 1

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

Comments

@habib the regex provided by you is incorrect as it doesn't accept the string 'ababa'.

Pls check it.

---

@  Habibkhan sir the regular expression given by you not accepts single a or single b.

which is also the part of language

plz check ......

---

Correct regex would be

a(a + bb*a)* + b(b+aa*b)* + epsilon

Answer 2

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.

Comments

See this one

https://gateoverflow.in/1995/gate2014-2_36

---

Thanks Arjun.  i refered the link that you gave. Please help me out on this.

 By pumping lemma's theorem if the string

ababa(please assume that length of this string is greater than the no of states in the DFA). And it E L

And by seperating the string into the sections uvw. Assume that the machine stays in the same state before and after consuming V. if V only contains the substing ab then on pumping b

ababba does not E L

---

Sorry my doubt is cleared. Even the second string belongs to L. Please ignore last comment.

Answer 3

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 .