Log In
20 votes

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?

  1. $L_{1}$ and $L_{2}$ are both regular.
  2. Neither $L_{1}$ nor $L_{2}$ is regular.
  3. $L_{1}$ is regular and $L_{2}$ is not regular.
  4. $L_{1}$ is not regular and $L_{2}$ is regular.
  5. Both $L_{1}$ and $L_{2}$ are infinite.
in Theory of Computation
edited by

Let some language L={ambncp |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.

L2 is finite so regular language //

now here L1is almost L-Land CFL-Regular would be CFL by closure property.


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



Can you see this one?

2 Answers

23 votes
Best answer
$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$

edited by
Sir, Added information :$L_{1}$ will not be a $DCFL$ .right?
$L_2$ is regular definitely DCFL too.
@Praven sir: sorry i asked about $L_{1}$(edited my comment) which is non-regular.

Will  $L_{1}$ be DCFL? i think its not !
You are right. $L_1$ is NCFL.
Hi Praveen Sir,

Can you please give the complement of L2.

@Praveen Saini

Is there any other method from the exam point of view?


@`JEET From exam point of view, note that $L_2$ is regular because it is finite. $m + n + p \leq 10$ makes the language finite.


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

Well, this sums up everything.
10 votes

L1 is CFL

L1={ambnc| (m=n v n=p) ⋀ m+n+p>=10}

Let us say m=n

then L1={anbncp | p>=10-2n}

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

L2={anbncp | p<=10-2n}

it has a finite memory. So it must be regular

Answer will be (D)

edited by

Praveen Saini plz check this



I think for some finite combination of n and p, p>10-2n.So we can implement that by changing state also.Do we really need another stack for that?

And more over i think L2={ambncp|m=n or n=p} intersection {ambncp|m+n+p>=10} i.e CFL intersection it would be CFL

Please correct me if i am wrong.


{ambncp|m+n+p>=10} is regular.

How r u saying this?

Can u give a DFA or Regular Expression for it?

<= means there are finite nuber of states.

But >= represents infinite number of states.

So, cannot conclude it with DFA.

yes , you could think about NFA, but m,n,p there are 3 variable also could go any number of times.

@srestha L1={ambnc| (m=n v n=p) ⋀ m+n+p>=10} is CFG but L2={ambnc| (m=n v n=p) ⋀ m+n+p<=10} is regular because  has finite length (string always less then 10) show 1 one is cfg but L2 is Regular.

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


L1={ambnc| (m=n v n=p) ⋀ m+n+p>=10}

Let us say m=n

then L1={anbncp | 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.


Related questions

13 votes
3 answers
Let $B$ consist of all binary strings beginning with a $1$ whose value when converted to decimal is divisible by $7$. $B$ can be recognized by a deterministic finite state automaton. $B$ can be recognized by a non-deterministic finite state automaton ... but not by a deterministic push-down automaton. $B$ cannot be recognized by any push down automaton, deterministic or non-deterministic.
asked Dec 7, 2015 in Theory of Computation makhdoom ghaya 1.1k views
4 votes
0 answers
Let $f(x), x\in \left[0, 1\right]$, be any positive real valued continuous function. Then $\displaystyle \lim_{n \rightarrow \infty} (n + 1) \int_{0}^{1} x^{n} f(x) \text{d}x$ equals. $\max_{x \in \left[0, 1\right]} f(x)$ $\min_{x \in \left[0, 1\right]} f(x)$ $f(0)$ $f(1)$ $\infty$
asked Dec 5, 2015 in Calculus makhdoom ghaya 268 views
23 votes
5 answers
Let $\sum_{1}= \left\{a\right\}$ be a one letter alphabet and $\sum_{2}= \left\{a, b\right\}$ be a two letter alphabet. A language over an alphabet is a set of finite length words comprising letters of the alphabet. Let $L_{1}$ and $L_{2}$ be the set of languages ... countably infinite. $L_{1}$ is countable but $L_{2}$ is not. $L_{2}$ is countable but $L_{1}$ is not. Neither of them is countable.
asked Dec 7, 2015 in Theory of Computation makhdoom ghaya 2.1k views
18 votes
4 answers
Let $a, b, c$ be regular expressions. Which of the following identities is correct? $(a + b)^{*} = a^{*}b^{*}$ $a(b + c) = ab + c$ $(a + b)^{*} = a^{*} + b^{*}$ $(ab + a)^{*}a = a(ba + a)^{*}$ None of the above.
asked Dec 7, 2015 in Theory of Computation makhdoom ghaya 1k views