in Theory of Computation
166 views
1 vote
1 vote

}

in Theory of Computation
166 views

1 comment

  1. L1 and L2
1
1

1 Answer

0 votes
0 votes

Answer : 2

Reason : only $L_1$ and $L_2$ is DCFL.

Solution :

  1. For $L_1$ { $0^l1^m0^{l+m}|l,$ $m\geq0$ } push for $0$, push for $1$, pop for $0$ empty stack accept. when $m=0$, string would be $0^l0^l$ and DPDA can not understand when we reach mid of string to stop pushing , start popping. But we can have two states, one for odd and one final state for even number of initial $0$ so all such $0^l0^l$ strings would be accepted  $L_1$ is DCFL.
  2. For $L_2$ { $0^l1^{2l}0^n| l\geq0 , n\geq0$ } since $n$ is independent DPDA needs to handle only $0^l1^{2l}0^*$ . This can be done by pushing two symbols for every $0$ at start , then when we see $1$ pop one symbol for each $1$. stack is empty go to final state which can have self loop for $0$. $L_2$ is DCFL. 
  3. For $L_3$ { $0^l1^{2l}0^{l+n}| l\geq0 , n\geq0$ } since $n$ is independent DPDA needs to handle only $0^l1^{2l}0^l0^*$ . This can be reduced to canonical context-sensitive languages $a^n b^n c^n.$  $L_3$ is CSL.
  4.  For $L_4$ { $0^m1^n2^m3^n| m, n\geq0$ } . $L_4$ is CSL.