edited by
1,756 views
15 votes
15 votes

Consider the following languages over the alphabet $\{0, 1\}$.

       $L1=\left \{ x.x^{R}\mid  x\in \left \{ 0, 1 \right \}^* \right \}$

       $L2=\left \{ x.x\mid  x\in \left \{ 0, 1 \right \}^* \right \}$

Where $x^{R}$ is the reverse of string x; e.g. $011^{R}=110$. Which of the following is true?

  1. Both $L1$ and $L2$ are regular.
  2. $L1$ is context-free but not regular where as $L2$ is regualr.
  3. Both $L1$ and $L2$ are context free and neither is regular.
  4. $L1$ is context free but $L2$ is not context free.
  5. Both $L1$ and $L2$ are not context free.
edited by

2 Answers

Best answer
18 votes
18 votes
$\mathbf{L1=\{x.x^R \mid x \in \{0,1\}^∗\}}$  Its even palindrome so it is CFL
$\mathbf{L2=\{x.x \mid x \in \{0,1\}^∗\}}$ Its string matching so it is CSL but not CFL

Option (D) $\mathbf{L1}$ is context free but $\mathbf{L2}$ is not context free.
edited by
8 votes
8 votes

D) L1 is CFL but L2 is not CFL.

L1=>

L1 can be accepted by a PDA and hence is CFL. But we need a NPDA for this as there is no deterministic way to identify where x ends and xR starts. So L1 is accepted by a NPDA and hence is NCFL.

L2=>

The set of strings in L2 are {aa,bb,aaaa,abab,baba,bbbb,aaaaaa...........}. We cannot accept these strings using an NFA. Now, even a PDA is not possible as once we store x on stack, it can only be read back in reverse order. Thus, we require 2 stacks to recognize L2. Now, L2 can be accepted by a TM in linear space and hence L2 is CSL.

edited by
Answer:

Related questions

21 votes
21 votes
3 answers
3
makhdoom ghaya asked Oct 10, 2015
2,580 views
Let $r, s, t$ be regular expressions. Which of the following identities is correct?$(r + s)^* = r^*s^*$$r(s + t) = rs + t$$(r + s)^* = r^* + s^*$$(rs + r)^* r = r (sr + r...