The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
97 views

Which of the following is CFL ?

a) L1 is CFL

b)L1 is CFL but L2 is not CFL

c)Both L1 and L2 are CFL

d) None

asked in Theory of Computation by Active (3.6k points) | 97 views
0

@srestha mam if we take the production

$S$->$S_3S_4$

Then how it will derive c 
0

Prince Sindhiya,mam

By using S4, it will generate c

@srestha, mam,

I agree it is CFL, every CFL has a CFG but my doubt is how it is DCFL, i am not getting it

0
@Shaik

why r u telling it is not DCFL

u mean different path to follow in OR case?
0

why r u telling it is not DCFL

mam, i am not able to draw DPDA​​​​​​​

 

0
and for NPDA?
0

and for NPDA?

yes i can,thats why i concluded it is CFL 

0
+1
yes... Finally concluded that L1 is CFL and L2 is DCFL
0
Shaik sir , please explain the second one how it is dcfl ?
0

@ prince mam,

push x on getting a,
pop x on getting b on x, otherwise push y on getting b on ( empty stack or y )
pop y on getting c on y, otherwise push x on getting c on ( empty stack or x )
pop x on getting d on x,
if stack is empty, accepted

in this process did you find any ambiguity?? 

2 Answers

+2 votes

This should be npda for first one

 

answered by Active (3.6k points)
0 votes
Answer should be c)
answered by Junior (533 points)


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

40,927 questions
47,580 answers
146,425 comments
62,311 users