edited by
1,540 views
13 votes
13 votes

Let $a^{i}$ denote a sequence $a . a ... a$ with $i$ letters and let $\aleph$  be the set of natural numbers ${ 1, 2,...}$. Let $L_{1}=\left\{a^{i}b^{2i}\mid i \in \aleph\right\}$ and $L_{2}=\left\{a^{i}b^{i^{2}}\mid i \in \aleph\right\}$ be two languages. Which of the following is correct?

  1. Both $L_{1}$ and $L_{2}$ are context-free languages.
  2. $L_{1}$ is context-free and $L_{2}$ is recursive but not context-free.
  3. Both $L_{1}$ and $L_{2}$ are recursive but not context-free.
  4. $L_{1}$ is regular and $L_{2}$ is context-free.
  5. Complement of $L_{2}$ is context-free.
edited by

3 Answers

Best answer
14 votes
14 votes

$L_1$ - CFL, $S \rightarrow aSbb \mid abb$

$L_2$ - Not CFL ,we can't count $i^2$ using CFL.

  1. False because $L_2$ is not CFL.
  2. True. $L_2$ is recursive
  3. False because $L_1$ is CFL.
  4. False, $L_1$ not regular.
  5. False, as complement of $L_2$ is also not context free. It still need to computer $i^2$ for checking for inequality.

Answer is B.

edited by
3 votes
3 votes
L1={ab,aabbbb,aaabbbbbb,...........}

so, it can be written like aSbb,  It is CFL

L2={ab,aabbbb,aaabbbbbbbb............}

it cannot be a CFL

so ans is b
1 votes
1 votes

Option b

L1 have linear power and only one comparison between a and b so it is CFL. 

L2 is not in linear power so it is CSL. and hence recursive. 

Answer:

Related questions