Google Answers Logo
View Question
 
Q: Pumping Lemma to get context free language from pda ( No Answer,   0 Comments )
Question  
Subject: Pumping Lemma to get context free language from pda
Category: Computers > Algorithms
Asked by: zoom618-ga
List Price: $50.00
Posted: 16 Mar 2005 13:28 PST
Expires: 17 Mar 2005 12:06 PST
Question ID: 495752
Say there exists a PDA such that:
The PDA is deterministic, and has no epsilon transitions.
Every transition either pushes a symbol on the stack, or pops a
symbol from the stack.
The PDA?s computation always proceeds with a sequence of pushes
followed by a sequence of pops. If the PDA ever attempts to push
a symbol onto the stack after it has already popped a symbol, it
immediately halts and rejects the input string.
The PDA accepts whenever its stack is empty.
Follows the pumping lemma: Let L be the language of a
Silly PDA M. There exists an integer p such that for all x existing in L
such that |x| > p, we can decompose x = abcde such that:
(i) |bcd| <= p
(ii) |b| = |d| and |b| >= 1
(iii) a b^i c d^i e existing in L for all i existing in {0, 1, 2, ...}
Is there a context-free language L where every string has even
length, such that L is not accepted by any PDA of this sort and can be
proved by the pumping lemma above?
Answer  
There is no answer at this time.

Comments  
There are no comments at this time.

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 answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


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