The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+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
asked in Theory of Computation by Loyal (8.5k points) | 60 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)
Your PDA is accepting aabccc. This isn't part of the language. BTW the language is CSK and not CFL.

Related questions

+3 votes
1 answer
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
47,881 questions
52,233 answers
67,653 users