The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes

$\text{Is the language L is DCFL or CFL ?}$


asked in Theory of Computation by Active (1.7k points) | 54 views
It is dcfl

3 Answers

+1 vote
ACCORDING to me it should be cfl but i am facing difficulty in drawing the pda for it , i don't know it's correct answer.

My approach -for every a we can push 2 a's and if c comes then pop 2a's for every b and if d comes pop single a for every b
answered by Active (1.7k points)
edited by
why do u think it is DCFL?
@srestha mam we can push a as per the given string.. than if  c comes pop one b for each a.. and if d comes pop one b for two a's.
and which will pop is not fixed
@srestha mam i think it is DCFL because after pushing a if c come then we pop one a .if d come then we will pop two a's
@Prince Sindhiya : ya, i think your approach is correct, but it should be dcfl with ur approach, not cfl.
+1 vote
Union of 2 cfl is always cfl and here both the languages given is CFL .So, L is a CFL but...


But we need to check wether L is DCFL or not . Union of 2 DCFL may or may not be DCFL but here the langauage generated after union is DCFL .

Reason :

L : Lanaguages having equal no of a and b or no of a is twice the no of b

push 2 a for each a and after all a's are over then see if next symbole is c or d. It will go to 2 different statet based on this. if next symbole is c then delete 2 a for each b otherwise delete one a for each b. No non-determ required ,
answered by Active (2.3k points)
edited by
here both are not only CFL but DCFL
@srestha I didn't read the question properly and answered edited

Do let me know if there is anything wrong in my logic.
0 votes
It think it is CFL because on starting state we will go to two states by seeing the a

On one state we will push a's and when c will come then we will pop the a for every single b and on other state  we will push two a's for every single a  and and when d will come then after that we will pop b's for every single a
answered by (265 points)
you mean to say we need NPDA to accept this language?

but a DPDA can be made which will go to 2 directions on inputs c or d, if it go to direction of d then will pop 2 a's for one b  or  if it takes direction of c will pop one a for one b

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,009 questions
45,506 answers
48,691 users