Understanding Pushdown Automata and Language Acceptance
Pushdown Automata (PDA) provide a theoretical framework for recognizing context-free languages. In PDA, the acceptance of a language depends on reaching a final state or having an empty stack. This concept is illustrated through examples and the distinction between deterministic and non-deterministic PDAs is explored. Explore PDA transitions and determine if a given language is deterministic.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
PUSHDOWN AUTOMATA -Mrs.Harini S Assistant Professor, Dept. of ISE,BMSCE
Acceptance of a Language by PDA There are two cases wherein a string w is accepted by a PDA: Get the final state from the start state Get an empty stack from the start state
Acceptance of a Language by PDA Get the final state from the start state Let M=(Q, , , , q0, Z, F) be a PDA. The language L(M) accepted by a final state is defined as L(M)={w | (q0,w,Z0) |-* (p, , ) } For some * , p F and w *. Note: when all the symbols in string w have been read and when the machine is in the final state, the final contents of the stack are irrelevant Get an empty stack from the start state L(M)={w | (q0,w,Z0) |-* (p, , ) } For some q0, p Q and w *. It means when the string w is accepted by an empty stack, the final state is irrelevant, the input should be completely read and the stack should be empty.
Example : wCwR Show whether the string aabCbaa is accepted by the PDA or not. (q0, aabCbaa, Z0) |- (q0, abCbaa, aZ0) |- (q0, bCbaa, aaZ0) |- (q0, Cbaa, baaZ0) |- (q1, baa, baaZ0) |- (q1, aa, aaZ0) |- (q1, a, aZ0) |- (q1, , ) In this method, finally stack should not contain anything including Z0. Note that q1 is not a final state and there is no final state.
Deterministic and Non-deterministic PDA Let M=(Q, , , , q0, Z, F) be a PDA. The PDA is deterministic if 1. (q, a ,Z) has only one element 2. If (q, ,Z) is not empty, then (q, a, Z) should be empty. Both the conditions should be satisfied for a DPDA. Let s check all our PDAs that we have designed are Deterministic or non-deterministic.
Deterministic and Non-deterministic PDA Is L ={wCwR| w (a+b)*} deterministic??
Deterministic and Non-deterministic PDA Transitions are: (q0, a ,Z0) = (q0, aZ0) (q0, a ,a) = (q0, aa) (q0, b ,a) = (q1, ) (q1, b ,a) = (q1, ) (q1, , Z0) = (q2, Z0)
Deterministic and Non-deterministic PDA Transitions: (q0, a ,Z0) = (q0, aZ0) (q0, b ,Z0) = (q0, bZ0) (q0, a ,a) = (q0, aa) (q0, b ,b) = (q0, bb) (q0, a ,b) = (q0, ) (q0, b ,a) = (q0, ) (q0, , Z0) = (q1, Z0)
