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

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 (2.3k points) | 93 views

@srestha mam if we take the production


Then how it will derive c 

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


why r u telling it is not DCFL

u mean different path to follow in OR case?

why r u telling it is not DCFL

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


and for NPDA?

and for NPDA?

yes i can,thats why i concluded it is CFL 

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

@ 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 (2.3k points)
0 votes
Answer should be c)
answered by (371 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

38,203 questions
45,703 answers
49,750 users