edited by
11,743 views
40 votes
40 votes

Consider the languages

$L1=\{0^i1^j\ \mid i \neq j\}, $

$L2=\{0^i1^j\mid i=j\},$

$L3=\{0^i1^j \mid i=2j+1\},$

$L4=\{0^i1^j \mid i\neq2j\}$

  1. Only $L2$ is context free.
  2. Only $L2$ and $L3$ are context free.
  3. Only $L1$ and $L2$ are context free.
  4. All are context free
edited by

1 Answer

Best answer
53 votes
53 votes
Correct Answer: $D.$ All are context free.
$L1 \rightarrow$ Push $0$ on stack and when $1$ comes, start popping. If stack becomes empty and $1$'s are remaining start pushing $1$. At end of string accept if stack is non- empty.

$L2 \rightarrow$ Do the same as for $L1$, but accept if stack is empty at end of string.

$L3 \rightarrow$ Do, the same as for $L2$, but for each $0$, push two $0$'s on stack and start the stack with a $0$.

$L4 \rightarrow$ Do the same as for $L1$, but for each $0$, push two $0$'s on stack

All are in fact DCFL. Pushing two $0$'s on stack might sound non-trivial but we can do this by pushing one symbol and going to a new state. Then on this new state on empty symbol, push one more symbol on stack and come back.
edited by
Answer:

Related questions

62 votes
62 votes
9 answers
1
go_editor asked Sep 30, 2014
23,721 views
Let $w$ be any string of length $n$ in $\{0,1\}^*$. Let $L$ be the set of all substrings of $w$. What is the minimum number of states in non-deterministic finite automati...
68 votes
68 votes
10 answers
2