It is dcfl

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+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

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

+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 ,

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 ,

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

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

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.9k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,009 questions

45,506 answers

131,660 comments

48,691 users