

Subject:
Push Down Automata
Category: Computers Asked by: alienmaxga 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 Nondeterministic 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 used.) 

There is no answer at this time. 

Subject:
Re: Push Down Automata
From: frankcorraoga 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: alienmaxga 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 contextfree languages from what I understand.) 
Subject:
Re: Push Down Automata
From: frankcorraoga 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 nonregular language, and this is a variation on that. 
Subject:
Re: Push Down Automata
From: alienmaxga 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: harrysnetga 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 following 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: alienmaxga 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 nondeterministic 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? 
If you feel that you have found inappropriate content, please let us know by emailing us at answerssupport@google.com with the question ID listed above. Thank you. 
Search Google Answers for 
Google Home  Answers FAQ  Terms of Service  Privacy Policy 