538 views
2 votes
2 votes
My doubt may be silly but plz help.

Given a particular language how to know whether a grammar is CFL or CSL sometimes it really creates me a problem

Language like {a^n b^n c^2n |n > 0}   is a CSL but if suppose it was a new random question than our instinct says that we can easily create its PDA so it should be CFL.

SO  How to tackle such question in first attempt if before hand we don't know anything about the language

1 Answer

0 votes
0 votes

Here is the language L={a^nb^nc^2n|n>0} can be easily solved from CFL as for every a and b we can push it into the stack and for every c pop off them. So it is CFL.

But as we know that CSL is more powerful than CFL so we can also solve it from LBA as well as PDA

Related questions

2 votes
2 votes
1 answer
1
Tuhin Dutta asked Dec 4, 2017
682 views
$a) \{\ 0^i\ 1^j\ 2^k\ \ | where\ i\ \neq j\ or\ j\ \neq k\ \}$$b) \{\ 0^i\ 1^j\ 2^k\ \ | where\ i\ \neq j\ and\ j\ \neq k\ \}$a) CFL(union of two OR-ed compa...
2 votes
2 votes
0 answers
4