Google Answers Logo
View Question
Q: Push Down Automata ( No Answer,   6 Comments )
Subject: Push Down Automata
Category: Computers
Asked by: alienmax-ga
List Price: $10.00
Posted: 25 Oct 2006 10:30 PDT
Expires: 27 Oct 2006 08:17 PDT
Question ID: 776787
I'm trying to construct the Non-deterministic Push Down Automata that
accepts the following language on {a,b}:
L={a^n b^m | n<m<2n}
At first I thought this was rather trivial, however, can't seem to
find a way to do this with a single stack (only one stack can be
There is no answer at this time.

Subject: Re: Push Down Automata
From: frankcorrao-ga on 25 Oct 2006 12:11 PDT
Are you sure this is context free?  What is the context free grammer
that describes it?
Subject: Re: Push Down Automata
From: alienmax-ga on 25 Oct 2006 12:30 PDT
It's a regular language, so yes, it is context free (a regular
language is a subset of context-free languages from what I
Subject: Re: Push Down Automata
From: frankcorrao-ga on 25 Oct 2006 13:42 PDT
You are right that regular languages are a subset of context free
languages,  but this is most definately NOT a regular language. 
Regular languages cannot count.  a^n b^n is the canonical example of a
non-regular language, and this is a variation on that.
Subject: Re: Push Down Automata
From: alienmax-ga on 25 Oct 2006 15:15 PDT
Hmmm, it might not be regular then...if it isn't regular, is there any
way to come up with a PDA for it?  I'm almost positive there is a
solution, I'm just note quite sure how to approach it.
Subject: Re: Push Down Automata
From: harrysnet-ga on 25 Oct 2006 16:28 PDT
As frankcorrao said the language is not regular, but
it does have a (probably nondeterministic) PDA. In this 
case it is much easier to derive a CFG, which is the 

s-> aTbb
T-> aTb
T-> aTbb
T-> ab

For the PDA the following strategy should work: For each a 
that you read push two a's in the stack. When you reach the 
first b pop two a's. For each following b nondeterministically 
pop either one a or two a's. If in the last b you manage to 
pop exactly one a you have an valid string.

At the same time you also have to check that your input is 
a series of a's only, followed by a series of b's only, but 
that is very easy to integrate with the previous paragraph.

I cannot see how you can produce a deterministic PDA to do 
the job, but that is not necessarily the case. I have not 
proved it, but I suspect no such DPDA exists, since m does 
not deterministically depend on n, so using the above to 
produce a NPDA is probably your best bet.

I hope this helps.
Subject: Re: Push Down Automata
From: alienmax-ga on 25 Oct 2006 17:31 PDT
harrysnet - thanks very much!  I think that works - as stated in the
original problem, I was looking for a non-deterministic solution so
that's great.  I'm not sure how to draw your solution as state diagram
(it is much easier to state in english) - how can I combine the two
parts together in a state diagram?

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

Google Home - Answers FAQ - Terms of Service - Privacy Policy