The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
46 views
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
asked in Theory of Computation by Active (4.6k points) | 46 views

1 Answer

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

answered by (39 points)
0
Your PDA is accepting aabccc. This isn't part of the language. BTW the language is CSK and not CFL.


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

38,187 questions
45,688 answers
132,723 comments
49,654 users