The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+4 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 **ℕ**.

- Both L1 and L2 are Regular
- L1 is Regular L2 is Not
- Neither L1 nor L2 Regular
- L2 is Regular L1 is not

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.

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={a^{p}b^{q }| p+q ≥ 1} we can construct the DFA and you will notice that you can extend the range{3,4....till 10^{6}}.L1 is regular.

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

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

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.

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

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2k
- Databases 4.1k
- CO & Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.4k
- Admissions 596
- Exam Queries 577
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

49,532 questions

54,126 answers

187,326 comments

71,046 users