74 views

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

0
It is dcfl

+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
edited
0
why do u think it is DCFL?
0
@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.
0
and which will pop is not fixed
0
@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
0
@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 ,
edited by
+1
here both are not only CFL but DCFL
0

Do let me know if there is anything wrong in my logic.
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
0
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

1