edited by
2,896 views
21 votes
21 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.
edited by

2 Answers

Best answer
24 votes
24 votes
$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
11 votes
11 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
Answer:

Related questions

18 votes
18 votes
4 answers
4
makhdoom ghaya asked Dec 7, 2015
2,321 views
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)^{*}...