The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
L= { $a^{n}b^{m}$ | $n<=m<=2n$ }


b) CFL but not DCFL

c) Not CFL
asked in Theory of Computation by Active (1k points) | 177 views
I am still unclear with the solution.

Can anyone elaborate it ?

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

4 Answers

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 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.

answered by Active (3.4k points)
selected by
+1 vote
Option b) cfl but not dcfl
answered by Boss (25k points)
grammar will be

$S\rightarrow aSb|aSbb|\epsilon$

why not DCFL?
Here push and pop are not cleare.i.e if a comes then push into the stack and b comes then we pop with b or bb. So we need to create two copy .
0 votes
you have to keep two copy of m one is m=n and other is m=2n which can't do dpda but npda can do ,so it will be cfl not dcfl
answered by Loyal (9.2k points)
0 votes
L=$a^{n}b^{n}\cup a^{n}b^{2n}$.so we can easily say that above language is CFL  not DCFL.
answered by Active (2.3k points)

Related questions

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

46,770 questions
51,221 answers
66,582 users