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

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 (249 points)
+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

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

37,103 questions
44,682 answers
127,199 comments
43,741 users