The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+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 \}$$
asked in Theory of Computation by Veteran (18k points)
retagged by | 336 views

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 .$

answered by Veteran (20.7k points)
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.

answered by (245 points)
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

33,687 questions
40,230 answers
38,793 users