737 views
1 votes
1 votes
L= { $a^{n}b^{m}$ | $n<=m<=2n$ }

a) DCFL

b) CFL but not DCFL

c) Not CFL

4 Answers

Best answer
0 votes
0 votes

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 by
1 votes
1 votes
Option b) cfl but not dcfl
0 votes
0 votes
L=$a^{n}b^{n}\cup a^{n}b^{2n}$.so we can easily say that above language is CFL  not DCFL.

Related questions

0 votes
0 votes
1 answer
2
0 votes
0 votes
1 answer
3
Rahul_Rathod_ asked Dec 24, 2018
563 views
consider following grammerS → aSb / aSbb / aSbbb / …..is language generated by above grammer is DCFL?
1 votes
1 votes
1 answer
4
practicalmetal asked Mar 20, 2023
358 views
The complement of the languages:i) {ww | w in (0+1)*}ii) {$a^n b^nc^n$ | n>1} area) Context Free b) Not Context Free c)are DCFL’s d)None