177 views
L= { $a^{n}b^{m}$ | $n<=m<=2n$ }

a) DCFL

b) CFL but not DCFL

c) Not CFL
0
I am still unclear with the solution.

Can anyone elaborate it ?

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

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.

selected
+1 vote
Option b) cfl but not dcfl
0
grammar will be

$S\rightarrow aSb|aSbb|\epsilon$

why not DCFL?
0
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 .
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
L=$a^{n}b^{n}\cup a^{n}b^{2n}$.so we can easily say that above language is CFL  not DCFL.

1
2
3
4
5