CSharp  Java  Python  Swift  GO  WPF  Ruby  Scala  F#  JavaScript  SQL  PHP  Angular  HTML
PDA AcceptanceA language can be accepted by Pushdown automata using two approaches: 1. Acceptance by Final State: The PDA is said to accept its input by the final state if it enters any final state in zero or more moves after reading the entire input. Let P =(Q, ∑, Γ, δ, q0, Z, F) be a PDA. The language acceptable by the final state can be defined as: L(PDA) = {w  (q0, w, Z) ⊢* (p, ε, ε), q ∈ F} 2. Acceptance by Empty Stack: On reading the input string from the initial configuration for some PDA, the stack of PDA gets empty. Let P =(Q, ∑, Γ, δ, q0, Z, F) be a PDA. The language acceptable by empty stack can be defined as: N(PDA) = {w  (q0, w, Z) ⊢* (p, ε, ε), q ∈ Q} Equivalence of Acceptance by Final State and Empty Stack
Example:Construct a PDA that accepts the language L over {0, 1} by empty stack which accepts all the string of 0's and 1's in which a number of 0's are twice of number of 1's. Solution: There are two parts for designing this PDA:
We are going to design the first part i.e. 1 comes before 0's. The logic is that read single 1 and push two 1's onto the stack. Thereafter on reading two 0's, POP two 1's from the stack. The δ can be δ(q0, 1, Z) = (q0, 11, Z) Here Z represents that stack is empty δ(q0, 0, 1) = (q0, ε) Now, consider the second part i.e. if 0 comes before 1's. The logic is that read first 0, push it onto the stack and change state from q0 to q1. [Note that state q1 indicates that first 0 is read and still second 0 has yet to read]. Being in q1, if 1 is encountered then POP 0. Being in q1, if 0 is read then simply read that second 0 and move ahead. The δ will be: δ(q0, 0, Z) = (q1, 0Z) δ(q1, 0, 0) = (q1, 0) δ(q1, 0, Z) = (q0, ε) (indicate that one 0 and one 1 is already read, so simply read the second 0) δ(q1, 1, 0) = (q1, ε) Now, summarize the complete PDA for given L is: δ(q0, 1, Z) = (q0, 11Z) δ(q0, 0, 1) = (q1, ε) δ(q0, 0, Z) = (q1, 0Z) δ(q1, 0, 0) = (q1, 0) δ(q1, 0, Z) = (q0, ε) δ(q0, ε, Z) = (q0, ε) ACCEPT state
Next TopicNondeterministic Pushdown Automata
