TIFR CSE 2015 | Part B | Question: 10

Question

Consider the languages 

$L_{1}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \geq 10\right\}$

$L_{2}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \leq 10\right\}$

State which of the following is true?

• A. $L_{1}$ and $L_{2}$ are both regular.
• B. Neither $L_{1}$ nor $L_{2}$ is regular.
• C. $L_{1}$ is regular and $L_{2}$ is not regular.
• D. $L_{1}$ is not regular and $L_{2}$ is regular.
• E. Both $L_{1}$ and $L_{2}$ are infinite.

Comments

Let some language L={a^mbⁿc^p |m=n or n=p} 

L is CFL , not DCFL because either m=n or n=p would create ambiguity so we have to make choices and DCFL can't then handle this.

L₂ is finite so regular language //

now here L₁is almost L-L₂  and CFL-Regular would be CFL by closure property.

---

Hey @Satbir Can you please help me understand $\mathbf{L_1}$?

---

@ankitgupta.1729

Can you see this one?

Answer 1

$L_2$ is finite, so regular.

$L_1$ is non-regular.

(It seems CFL to me as I think it can be implement with the help of PDA , as stack can ensure $(m=n \vee n = p)$ and we can also ensure $(m+n+p \geq 10)$ with minimum states changes along with transitions).

$L_2$ is actually {$c^p$ | $p \leq 10$} $\cup$ {$abc^p$ | $p \leq 8$} $\cup$ {$a^2b^2c^p$ | $p \leq 6$}$\cup$ {$a^3b^3c^p$ | $p \leq 4$} $\cup${$a^4b^4c^p$ | $p \leq 2 $} $\cup${$a^5b^5$}$\cup$ {$a^p$ | $p\leq 10$} $\cup$ {$a^pbc$ | $p\leq 8$} $\cup$ {$a^pb^2c^2$ | $p\leq 6$} $\cup$ {$a^pb^3c^3$ | $p\leq 4$} $\cup$ {$a^pb^4c^4$ | $p\leq 2$} $\cup$ {$b^5c^5$ | $p\leq 10$}

Correct Answer: $D$

Comments

Thanks @pritishc

Following a similar logic $\mathbf{L_1}$ is infinite. $\therefore$ Not regular, right or is it like we won't be able to compare the two states?

---

If a language is finite, it is definitely regular. However, if a language is infinite, it may or may not be regular. $(0 + 1)^*$ is regular, yet infinite. $0^n1^n$ is also infinite, but non-regular.

If there is a pattern in the language that you can exploit, there likely is a DFA/NFA for it. If the language looks like it is non-regular but actually is finite, it is definitely regular and you can make a DFA/NFA for it.

$L_1$ is non-regular because we have to keep track of how many $a$'s vs $b$'s, or $b$'s vs $c$'s, and the language is infinite as well, so we can't create a DFA for it (finite memory of a DFA not equipped to track the counts, would need a stack).

---

Thanks.

Well, this sums up everything.

Answer 2

L1 is CFL

L₁={a^mbⁿc^p | (m=n v n=p) ⋀ m+n+p>=10}

Let us say m=n

then L₁={aⁿbⁿc^p | p>=10-2n}

It cannot be represent in 1 stack . So, it could be CSL

L₂₌{aⁿbⁿc^p | p<=10-2n}

it has a finite memory. So it must be regular

Answer will be (D)

Comments

should not L1 be csl   not cfl plz correct if i am wrong here

---

Hmmm L1 seems to be CSL because the first part m=n or n=p can be performed by NPDA but this additional counting of m n p cannot be performed in parallel  with one stack..

---

Dear @Praveen Saini @srestha and @KISHALAY DAS

In my view also L1 is CSL

as 

L₁={a^mbⁿc^p | (m=n v n=p) ⋀ m+n+p>=10}

Let us say m=n

then L₁={aⁿbⁿc^p | p>=10-2n}

we can't have value of n after popping out b corresponding to a's so, how we will compare that whether p>=10-2n is right or wrong.

Also, How could we count n using state transition as the core inside CFL also we have finite number of states but here n is not finite.

Please correct me if i am wrong.