edited by
702 views
5 votes
5 votes

Which is Regular considering the following sets :

L$_1$={a$^p$b$^q$ | p+q ≥ 10$^6$}

L$_2$={a$^m$b$^n$ | m−n ≥ 10$^6$} 

Note that p, q, m and n can only belong to set .

  1. Both L1 and L2 are Regular
  2. L1 is Regular L2 is Not
  3. Neither L1 nor L2 Regular
  4. L2 is Regular L1 is not
edited by

1 Answer

Best answer
3 votes
3 votes

Answer : B.


$L_1 = \{ a^pb^q | p + q  \geq 10^6 \}$ 

$L_1$ is Regular. Moreover, $10^6$ is nothing but a large constant number. If it had been $10^7 \,\,or\,\,10^2$ instead of $10^6$, It wouldn't have mattered, Right? So, Let's get rid of such big number and replace it with, say, $1.$

So, $L_1' = \{ a^pb^q | p + q  \geq 1 \}$ Which is a Regular language. It is same as  $\{a ^*b^* \} - \{  \in \}.$

Similarly, $L_1$ is also regular because $L_1$ is the Intersection of $\{ a^*b^*\}$ and $\{ w \in \{a ,b \}^* |\,\, |w| \geq 10^6\},$ both of which are Regular.


$L_2 = \{ a^mb^n | m - n  \geq 10^6 \}$ 

Again,  $10^6$ is nothing but a large constant number. If it had been $10^7 \,\,or\,\,10^2$ instead of $10^6$, It wouldn't have mattered, Right? So, Let's get rid of such big number and replace it with, say, $1.$

$L_2' = \{ a^mb^n | m - n  \geq 1 \}$ Which is nothing but $L_2' = \{ a^mb^n | m > n \}$ Which is a DCFL (so is CFL).

It is CFL because we can Push $a's$ on the stack and keep pushing them onto the Stack and when we see $b's$ then we pop One a for one b. And at last, when the string ends, if we have $a's$ on the stack then string will be accepted, otherwise rejected. That's informal idea of PDA(or DPDA ) programming for this language. Now you can make a DPDA for this language. Or we can write a CFG for this language as follows :

$S \rightarrow aSb|A$

$A \rightarrow aA|a$

This is the CFG that generates All and Only the strings of $L_2'.$


Why $L_2'$ is Not Regular??

Though by now you must have understood that $L_2$ is Not Regular because FA cannot remember How many $a's$ have appeared before $b's$ start to appear. Like take the string $a^{100} b^{98}$, $100\,\,a's$ have appeared before $b's$ start to appear But when $b's$ start to appear, FA doesn't know Exactly How many $a's$ had appeared. So, It can't really check between number of $a's$ and $b's.$ 

So, the above is Informal but Intuitive idea behind $L_2'$ Not being a Regular language. But Let me show you that $L_2'$ is Not Regular using Pumping lemma and then Using Myhill-Nerode equivalence relation.


Using Pumping lemma for Regular languages to Show that $L_2'$ is Not Regular :

Pumping lemma states a Deep Property that All Regular languages share. By Showing that a language does not have the property stated by Pumping lemma, we are guaranteed that It is Not Regular. 

Pumping Lemma(PL) is a necessary condition for Regular languages but not sufficient condition

i.e. All Regular languages must satisfy this condition and some Non-regular languages also satisfy this condition.

So, Regular Language → Satisfies Pumping Lemma

∴ Contrapositive statement is Doesn't Satisfy Pumping Lemma → Not Regular Languages


Pumping lemma for Regular languages says

" If a language L is Regular,

then $\exists P \geq 1$, such that 

$\forall \,\,strings\,\,w \in L$, If $|w| \geq P$ then

$\exists x,y,z$, such that $w = xyz$

and $|xy| \leq P$

and $y \neq \in$ i.e. $|y| \geq 1$

and $\forall q \geq 0$, $xy^qz \in L$


In Words, If $L$ is regular, then there’s some magic number $P$(Called Pumping length). And if I take any string $w$ that is at least as long as $P$, then I can break it up into three parts $x, y, $and $z.$ Now, the length of $xy$ is less than or equal to $P$, and also the length of $y$ is greater than or equal to $1$ and less than or equal to $P$.

In very simple words, If $L$ is a regular language then there is some positive number $P$ associated with $L$ such that for all strings $w $ of length greater than or equal to $P$, we can find some non-empty sub-string $y$ in $w$ within the first $P$ symbols of $w$  such that when we repeat $y$ Zero or more times then the produced strings also belong to $L.$


For language, $L_2' = \{ a^mb^n | m > n \}$

Let's assume that $L_2'$ is Regular. So, There must be some positive number  $P$ associated with $L_2'$ such that Pumping lemma satisfies. So, Let's say that Magic number (Pumping length) is $P.$ So, Now, For all string, $w$ with length $\geq P$ ,  We must be able to find some Non-empty substring $y$ of length at most $P$ within the first $P$ symbols of $w.$ 

So, Let's take string $w = a^Pb^{P-1},$ For this string if You take any Non-empty substring $y$ within the first $P$ symbols (i.e. $y$ must be made of $a's$ only) and if you repeat that $y$ Zero times (repeating $y$ Zero times is same as Removing $y$ from the string $w$) then the resulted string will NOT belong to $L_2'.$ So, Whatever Pumping length $P$ you take, at least One string $w = a^Pb^{P-1} $ I have shown you which Won't get Pumped.   

So, Pumping lemma is violated/Not Satisfied by $L_2'.$ So, $L_2' $ is Not Regular. 

Similar logic can be used for $L_2$ as well. 

So, $L_2$ is Not Regular.


Using Myhill-Nerode Equivalence Relation to Show that $L_2'$ is Not Regular :

I will Not be stating the Whole Myhill-Neorde Theorem here But only the Part that is required to Show that $L_2'$ is Non-Regular.

Theorem : Let $L ⊆ Σ ^∗$ be any language. Suppose there is an infinite set $S$ of strings such that $\forall x, y ∈ S (x \neq y), x \not\equiv _L y.$ That is, suppose $(∀x \neq y ∈ S)(∃z ∈ Σ ^∗ ) (Exactly \,\,\,one\,\,\, of \,\,\,the \,\,\,strings\,\,\, xz\,\,\, or\,\,\, yz\,\,\, belongs\,\,\, to\,\,\, L).$ Then $L$ is not a regular language. Here such set $S$ is called Distinctive set for $L.$

http://www.cse.buffalo.edu/~regan/cse396/CSE396MNT.pdf

For given language $L_2', $ Consider the set $S = \{a^* \}.$ This set will work as a distinctive set for $L_2'.$  i.e. If you take any Two  different arbitrary string $x,y$ from $S$ then You will definitely find some $z \in \Sigma^*$ such that Exactly one of the Strings $xz$ or $yz$ will belong to $L_2'.$ Let any pair $x, y ∈ S$ with $x \neq y $ be given. By definition of S, there are numbers $m, n ≥ 0$ with $m \neq  n$ such that $x = 0^m$ and $y = 0^n$ . Take $z = 1^m.$ Then $xz$ will belong to $L$ But  $yz$ will Not belong to $L.$ Since $xz = 0^m1^ m ∈ L$ and $yz = 0^n1^ m \notin L.$ Since $x, y ∈ S$ were arbitrary, $S$ is an “infinite distinctive set” for $L_2'$, so $L_2'$ is non-regular. (Here the boldface take goes with the $∃$ quantifer, while all the other boldface words go with the $∀$ quantifier.)

selected by