438 views
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 | 438 views
0

@Shaik Masthan Brother can you explain L1 in term of the stack. Thankyou

0

we can think like, n ≤ m as L1 and m ≤ 2n as L2

finally we want L1.L2,

cfl's are closed under concatenation.

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
can you please tell me the idea of stack? i.e if i want to check if they are cfl with STACK ,then how should we approach?
0
@Uddlpto

to check with stack we need to check how many conditions we have to check in the given language

like for L2 here u need to check i=2j or j=2k....but u dont need to check them simultaneously so we can use one stack at a time to check the conditions...suppose instead of this u were given to check i=2j"and" j=2k..this would not have been possible with one stack...these two checking have to be done together..so u need two stacks here...
overall concept is as we know when we put a stack with FA it works like a memory to remeber things...as u keep on increasing the no of stacks...u start moving up the language hierarchy...and when this memory becomes infinte ..we enter into TM...hope it helps...
0
idea for pda of first one?
–1 vote

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.

+5
in second case there is OR condition between two comparision,, so need not to  check both the conditions at once,,,a NPDA can accept it....

correct me if m wrong
+1
oh yes ,, yeah it will be CFL ,, i just overlooked it .Thanx For Correction :)
+1
@Abhishek: Your idea for the PDA for $L_1$ is wrong too. $L_1$ is NCFL.
0
@Pragy how can we make pda for L1

1
+1 vote