The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+4 votes
80 views

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 by (399 points)
edited by | 80 views
0

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

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

0
explanation please
0
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.
+2

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.

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

Why L2 is cfl?

Because we have CFG that generates  $L_2 :$

$S→aSb|A$

$A→aA|a$

1 Answer

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

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

by Boss (25.7k points)
selected by
0
Great explanantion sir. Thankyou

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,376 questions
55,836 answers
192,559 comments
91,336 users