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 Junior (643 points) | 124 views
I am still unclear with the solution.

Can anyone elaborate it ?

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

3 Answers

+1 vote
Option b) cfl but not dcfl
answered by Boss (22.5k 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 (5.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 Junior (717 points)

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

37,964 questions
45,466 answers
48,379 users