3,197 views
4 votes
4 votes
Consider the following language:?

L= {w | w $\epsilon$ {0,1}* , w has equal number of occurrences of ‘001’ and ‘010’}

Is L regular? If so, please provide a DFA for L.

2 Answers

Best answer
14 votes
14 votes

Answer : Non-Regular.


1. Intuitive(Informal) Idea : The given language is Non-regular because a Finite automata can not count the occurrences of $001$ and $010.$ For instance, There could be any number of $001$ sub-strings in the given string before substring $010$ appears for the first time and vice versa. So, there is no connection between the occurrence of the substring $001$ and $010$. They are complete independent in the sense that any could occur any number of time without the other occurring. 

For instance, Consider the following string :

$w1 =  $  00110011001100110011001100110011001100111111111010110101101011010110101101011010110101101011010 

The above string belongs to the language because It has $Ten$ occurrences of $001,010$ each. 

But with small modification, the following string does not belong to the given language :

$w2 =$  00110011001100110011001100110011001100111111111101011010110101101011010110101101011010110101101011010 

Now, by looking at the above strings, we can observe that a FA cannot accept such language because by the time It will reach the middle Blue marked-1's, It wouldn't know How many occurrence of $001$ it has seen and hence, after the blue marked-1's It would not be able to distinguish between between the above two strings as in which to accept and which to reject.

So, It was the Intuitive(informal) Idea to understand why the given language is Non-Regular by informally showing that FA doesn't have the capability to differentiate between the strings of above type. (One can extend this informal idea to other types of strings as well.)


2. Formal Proof of Non-regularity of the given language :

We will show that the given language doesn't satisfy the Pumping lemma(PL) condition for the Regular languages. 

Let's assume that given language $L$ is Regular and hence, It  must satisfy PL. Hence, there exists some constant $P$(Pumping length) such that for all the strings $w$ in the language such that $|w| \geq P$, we can find some Non-empty sub-string near the beginning of the string $w$ such that It can be pumped. (This is somewhat informal idea of PL of Regular languages, for formal definition and explanation of PL, refer the links given below) 

Now, Consider the following string $w :$  

  00110011001100110011001100110011........001100111111111010110101101011010110101101011010110101101011.......010

This string is such that there are $2P$ occurrences of $001$ before the middle Blue marked-1's and there are $2P$ occurrences of $010$ after the middle blue marked-1's. So, this string does belong to the given language and has the length $\geq P$, so It is a valid candidate for our PL condition. But If you apply PL condition on this string, you will find that this string cannot be pumped in any manner (whichever sub-string I choose near the beginning of the string, some Pumped strings will not belong to $L$   ) and hence, $L$ does not satisfy PL of Regular languages and hence, $L$ is Non-regular.

$\color{Red}{\text{Understand Complete Pumping Lemma, Crystal Clear:}}$

Here is Complete Pumping Lemma Lecture: https://youtu.be/8cdPjuYbIrU 

This Pumping Lemma lecture contains EVERYTHING about Pumping Lemma of Regular Languages, i.e. Proof, Examples, Variations, GATE PYQs, Finding minimum pumping length etc. Watch this lecture for Complete, Correct & Clear Understanding.


P.S. Notes :

1. Refer the following for more examples and detailed explanation of Pumping lemma for Regular languages.

https://gateoverflow.in/146637/prove-a-language-is-regular-using-pumping-lemma?show=225390#a225390

https://gateoverflow.in/3787/gate2005-it-40?show=296671#a296671

2. Refer similar looking questions where Sub-string occurrence matching, in fact, is Regular and Try to find the difference between those languages and this language. 

https://cs.stackexchange.com/questions/12139/is-the-language-of-words-containing-equal-number-of-001-and-100-regular

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

https://cs.stackexchange.com/questions/57342/write-a-regular-expression-contains-an-equal-number-of-01-and-10-subtrings

edited by
0 votes
0 votes
When you write 001 twice 001001 there is 010 in between. If you write 010 twice 010010 you get 001 in between. So if you write n times anyone of the pattern the other pattern can be found either n+1 times or n times or n-1 times. You can construct nfa for this.

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
0 answers
2
TusharKumar asked Jan 21, 2023
311 views
Let L be a language over {a,b} that contains the same number of occurrences of a and b. which of the following is non-regular? a. b. c. d. MSQ & answer is a,c,d