L is regular or not??

Question

Let $\sum$ = {a, b} and Let L = { w | w contains an equal no of occurrences of substring 'ab' and 'ba' }. Thus aba $\in$ L since 'aba' contains one occurrence of 'ab' and one occurence of 'ba' but abab $\notin$ L.

Then which of the following is TRUE?

Select one:

A. L is regular.

B. L is DCFL but not regular.

C. L is CFL but not regular.

D. L is recursive but not a CFL.

Comments

https://gateoverflow.in/4300/l-is-regular-or-not

Answer 1

L is regular. Because we cannot have two ab in a string without having a ba or vice-verse. So, there are only 3 states possible- one where number of "ab" and "ba" are same, one where number of "ab" is 1 more than number of "ba" and the final one where number of "ba" is 1 more than number of "ab". So, we just need a finite state automata to represent this.

Answer 2

There can be no direct step-wise procedure to solve such questions.In the above question, we need to check option wise.

A language is said to be regular if you can construct a finite automaton for it. Here is the  DFA for required language.

Answer 3

The Regular Expression of Given language is

(ab)*a + (ba)*b

Hence it is Regular