The Gateway to Computer Science Excellence
+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 \}$$
in Theory of Computation by
retagged by | 536 views

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


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

finally we want L1.L2,

cfl's are closed under concatenation.

5th page of

2 Answers

+10 votes
Best answer

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
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?

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 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 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...
idea for pda of first one?
–1 vote

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.

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
oh yes ,, yeah it will be CFL ,, i just overlooked it .Thanx For Correction :)
@Abhishek: Your idea for the PDA for $L_1$ is wrong too. $L_1$ is NCFL.
@Pragy how can we make pda for L1

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,497 answers
95,318 users