The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
103 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 (5.2k points) | 103 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 (5.2k points)
0 votes
Answer should be c)
answered by Junior (743 points)

Related questions

0 votes
0 answers
1
0 votes
1 answer
4


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

44,071 questions
49,594 answers
162,952 comments
65,786 users