retagged by
1,872 views
5 votes
5 votes
Which of the following languages are CFL?
$$L_1= \left \{ 0^n 1^m \mid n \leq m \leq 2n \right \} \\[1em] L_2 =\left \{ a^i b^j c^k \mid i=2j \text{ or } j=2k \right \}$$
retagged by

2 Answers

Best answer
12 votes
12 votes

Both are CFL.

CFG for $L_1: \quad \left \{ S \to 0S1 \mid 0S11 \mid \varepsilon \right .$



CFG for $L_2 :\quad \left \{ \begin{align} S &\to X \mid Y \\[1em] X &\to Xc \mid P \\ P & \to aaPb\mid \varepsilon\\[1em] Y &\to aY \mid Q \\ Q & \to bbPc\mid \varepsilon \end{align}\right .$

selected by
–1 votes
–1 votes

Answer is 1)

 1) To accept the input we will push "X" for "0" and when we  will encounter "1" sim ply pop it.

In case M=N  it will be same as 0^N 1^N or M>N then pop every "1" after "0".

2) here we required two memory comparison 1st for i=2j and j =2k , so this is not CFL.

Related questions

4 votes
4 votes
1 answer
3
Rajesh R asked Oct 23, 2017
1,867 views
$L1 = a^i b^i c^j$ such that i>=1 and j>=1$L2 = a^i b^i c^j$ such that j>=1$L3 = a^i b^i c^j$ such that i>=1 Answer is only L1. I think all 3 are CFL's.