Push down Automata Acceptance
Acceptance of Language by Push down Automata
Push down Automata accepts the language, which is called context free language.
Push down Automata = Finite Automata + Auxiliary Memory (Stack)
Auxiliary Memory helps Push down Automata to behave more powerful than finite state machine.
Push down automata with two stacks is much more powerful than push down automata with one stack, which means:
Push down automata = Finite Automata + 2 Stack // equivalent to a Turing machine.
Ways of Acceptance
The Push down Automata indicates its acceptance in following two ways:
- Acceptance by final state
- Acceptance by empty stack
These two methods are equivalent and we will prove it in this topic. They do not affect the language accepted by Push down Automata.
Acceptance by final state
Push down Automata P contains 7 elements (Q, ?, ?, ?, q0, Z0, F).
Q: It contains finite states of Push down Automata.
?: It contains set of input Symbols.
?: It contains stack alphabet that are allowed to add element push into the stack.
q0: It contains the initial state of the Push down automata. i.e. q0 ? Q.
Z: It is called the start symbol.
F: It contains final states of Push down automata.
?: It represents transition function.
A string w is accepted by the final state defined as:
L (P) = { w ? ?* | (q0, w, Z0 ) |-* (qf , ? , ? ) }
For some qf ? F and ? ? ?*.
Let L (P) is the language accepted by final state.
Example:
Construct a Push down Automata that accepts the following language by final state.
L = { 0n12n | n > 0 }
Solution:
The strings that can be derived from given language are of the form:
011, 001111, 000111111,……………..
Let PDA P = (Q, ?, ?, ?, q0, Z0, F) which recognize above given language.
Q = { q0, q1, q2, qf } represents finite states.
? = { 0, 1 } represents finite input symbols.
? = { 0, Z0 } represents tape states.
F = { qf } represents final state.
q0 is the initial state of Push down Automata.
? can be defined as:
R1: ? (q0, 0, Z0) = {(q0, 0Z0)}
R2: ? (q0, 0, 0) = {(q0, 00)}
R3: ? (q0, 1, 0) = {(q1, 0)}
R4: ? (q1, 1, 0) = {(q2, ?)}
R5: ? (q2, 1, 0) = {(q1, 0 )}
R6: ? (q2, ?, 0) = {(qf, Z0)}
Acceptance by Empty stack
Push down Automata P contains 7 elements (Q, ?, ?, ?, q0, Z0, F).
Q: It contains finite states of Push down Automata.
?: It contains set of input Symbols.
?: It contains stack alphabet that are allowed to add element push into the stack.
q0: It contains the initial state of the Push down automata. i.e. q0 ? Q.
Z: It is called the start symbol.
F: It contains final states of Push down automata.
?: It represents transition function.
A string w is accepted by the empty stack or null stack is defined as:
N (P) = { w ? ?* | (q0, w, Z0 ) |-* (qf , ? , ? ) }
For some q ? Q.
N (P) is the language accepted by Push down Automata by empty stack.
Example:
Construct a Push down Automata that accepts the following language by empty stack.
L = { 0n12n | n > 0 }
Solution:
The strings that can be derived from given language are of the form:
011, 001111, 000111111, ……………..
Let PDA P = (Q, ?, ?, ?, q0, Z0, F) which recognize above given language
Q = { q0, q1, q2, qf } represents finite states.
? = { 0, 1 } represents finite input symbols.
? = { 0, Z0 } represents tape states.
F = { ? } represents tape state.
q0 is the initial state of Push down Automata.
? can be defined as:
R1: ? (q0, 0, Z0) = {(q0, 0Z0)}
R2: ? (q0, 0, 0) = {(q0, 00)}
R3: ? (q0, 1, 0) = {(q1, 0)}
R4: ? (q1, 1, 0) = {(q2, ?)}
R5: ? (q2, 1, 0) = {(q1, 0 )}
R6: ? (q2, ?, 0) = {(qf, Z0)}
R7: ? (qf, ?, Z0) = {(qf, ?)}