Push Down Automata
Configuration
It contains finite control , input tape and a stack and Finite control contains finite number of states.
Read head or read pointer is used to read the input symbol from the input tape.
The symbols can be pushed or popped from stack , which is used to keep track of previous symbols.
For every string finite control starts from the initial state.If the string valid finite control reaches to the final state at end of input.
Acceptance Mechanisms
Acceptance by final state (universal mechanism)
Acceptance by empty stack (local mechanism)
Acceptance by empty stack and final state.
CFL =~ PDA by empty stack =~ PDA by final state =~ PDA by empty stack and final state =~ CFG.
Operations
The operations on push down automata are as follows:
PUSH : Some finite sequence of symbols is pushed into the stack.
POP : One symbol at the top of the stack is popped.
BIPASS : i.e do nothing stack contents unchanged while state may be changed
REPLACE : Replace one symbol at the top of the stack.
Specification
PDA = ( Q , ⅀ , Ꞇ , ẟ ,q0 , Z0 , F ) is a 7 tuple notation
Where,
Q is a set of finite states.
⅀ is the input alphabet which contains finite number of input symbols.
Ꞇ is the stack alphabet which contains a finite number of stack symbols.
ẟ is a transition function.
(i) ( DPDA ) ẟ : Q ⤫ ( ⅀ ⋃ { ∈ } ) ⤫ Ꞇ → Q ⤫ Ꞇ
(ii) ( NPDA ) ẟ : Q ⤫ ( ⅀ ⋃ { ∈ } ) ⤫ Ꞇ → 2Q⤬ Ꞇ (only finite sub – sets ).
q0 is a single start state q0 ∈ Q.
Z0 is the start symbol Z0 ∈ Ꞇ.
F is the set of final states F ⊆ Q. If acceptance is by empty stack method then F is not specified.
Read head or read pointer is used to read the input symbol from the input tape.
The symbols can be pushed or popped from stack , which is used to keep track of previous symbols.
For every string finite control starts from the initial state.If the string valid finite control reaches to the final state at end of input.
Acceptance Mechanisms
Acceptance by final state (universal mechanism)
Acceptance by empty stack (local mechanism)
Acceptance by empty stack and final state.
CFL =~ PDA by empty stack =~ PDA by final state =~ PDA by empty stack and final state =~ CFG.
Operations
The operations on push down automata are as follows:
PUSH : Some finite sequence of symbols is pushed into the stack.
POP : One symbol at the top of the stack is popped.
BIPASS : i.e do nothing stack contents unchanged while state may be changed
REPLACE : Replace one symbol at the top of the stack.
Specification
PDA = ( Q , ⅀ , Ꞇ , ẟ ,q0 , Z0 , F ) is a 7 tuple notation
Where,
Q is a set of finite states.
⅀ is the input alphabet which contains finite number of input symbols.
Ꞇ is the stack alphabet which contains a finite number of stack symbols.
ẟ is a transition function.
(i) ( DPDA ) ẟ : Q ⤫ ( ⅀ ⋃ { ∈ } ) ⤫ Ꞇ → Q ⤫ Ꞇ
(ii) ( NPDA ) ẟ : Q ⤫ ( ⅀ ⋃ { ∈ } ) ⤫ Ꞇ → 2Q⤬ Ꞇ (only finite sub – sets ).
q0 is a single start state q0 ∈ Q.
Z0 is the start symbol Z0 ∈ Ꞇ.
F is the set of final states F ⊆ Q. If acceptance is by empty stack method then F is not specified.
No comments