Can anyone elaborate it ?

We are doing two comparisons here n<=m and m<=2n.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

0 votes

Best answer

Because the question doesn't have a best answer selected, I will give it a try.

We know that the number of **b**'s is somewhere between number of **a**'s and twice the number of **a**'s.

Now let's design a PDA for this,

Push all the **a**'s into the stack and when the **b**'s start to come,

At this point you have to make a copy of this machine, one copy will pop 1 **a** for 1 **b** and the other will pop 1 **a** for the 2 **b**'s.

As another **b** comes, make 2 copies of the each of the earlier 2 machines, one would pop 1 **a** for 1 **b **and the other would pop 1 **'a'** for 2 **b**'s.

Similarly, we keep on making 2 copies of machine at each occurrence of **b. **And the same would continue until any one of the machines accept the string or all of them reject the string after the end of the input.** **

if you're able to imagine, we would get a binary tree like structure.

Since here we're creating copies of the PDA, it can't be a DPDA, so not a DCFL but just CFL.

+1 vote

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.3k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,904 questions

47,561 answers

146,300 comments

62,306 users