Log In
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
in Theory of Computation
edited by

L1={apbq|p+q≥106} is regular

L2={ambn|m−n≥106} is non regular

explanation please
lets i give u idea p+q=>5
now tell me how many number needed such that equation satisfy.
(0,5)(1,4)(2,3),(4,1)(3,2)(5,0)...these many are restriction after that every posibility accepted.
Means finite states are needed.

Try to construct FA for smaller range since we have $\geq$ finite number.

I took set N as {1,2,3,........}

Let L1={apbq  |  p+q ≥ 1} we can construct the DFA and you will notice that you can extend the range{3,4....till 106}.L1 is regular.

Let L2={amb| m−n ≥ 106} we won't be able to construct the DFA for this small range. So L2 is not regular.

Why we can't create finite states for L2?
L2 is CFL . So we cant create DFA .
Why L2 is cfl?

Why L2 is cfl?

Because we have CFG that generates  $L_2 :$



1 Answer

3 votes
Best answer

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.$

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
Great explanantion sir. Thankyou

Related questions

4 votes
2 answers
Consider the following statements: $S_1:\{(a^n)^m|n\leq m\geq0\}$ $S_2:\{a^nb^n|n\geq 1\} \cup \{a^nb^m|n \geq1,m \geq 1\} $ Which of the following is regular? $S_1$ only $S_2$ only Both Neither of the above
asked May 26, 2019 in Theory of Computation Hirak 496 views
0 votes
1 answer
Consider the following language: L = {w| w $\epsilon$ {0,1}* ; w has equal number of occurances of 001' and 010' } The solution they provided: The absolute difference between the number of occurrences of 001' and 010' is at most 1. Hence a DFA can be found. I ... going to find an occurrence of 010' (and vice-versa)). But, since such info is not given, so how this can be a regular language?
asked Jan 29, 2019 in Theory of Computation Harsh Kumar 108 views