Scribd
Upload
33 views7 pages

PDA1

Pushdown automata are automata that use a stack as memory to recognize context-free languages. A pushdown automaton is defined by a 7-tuple that includes a finite set of states, input and stack alphabets, transition function, start state, start stack symbol, and set of accepting states. The transition function maps combinations of current state, input symbol, and top stack symbol to a set of next states and stack operations like push or pop. The automaton accepts if it reaches an accepting state with an empty stack after reading the entire input string.

Uploaded by

علي عبد الحمزه
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
33 views7 pages

PDA1

Pushdown automata are automata that use a stack as memory to recognize context-free languages. A pushdown automaton is defined by a 7-tuple that includes a finite set of states, input and stack alphabets, transition function, start state, start stack symbol, and set of accepting states. The transition function maps combinations of current state, input symbol, and top stack symbol to a set of next states and stack operations like push or pop. The automaton accepts if it reaches an accepting state with an empty stack after reading the entire input string.

Uploaded by

علي عبد الحمزه
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 7

Pushdown Automata

Automata for Context-Free Languages


Language class Syntax/Grammar Automata
Regular regular expressions, DFA, NFA, NFAλ
regular grammar
Context-free context-free grammar ?

• DFA, NFA, NFAλ: finite states = finite memory, e.g.


– even or odd number of a’s read: two states even, odd
– the last 2 letters read: four states for aa, ab, ba, bb.
• Problem: languages like {anb n | n ≥ 0} need unbounded memory. A DFA with k
states can only “count to k”.
• Solution: extend FSA by adding memory
• Automata for Context-Free Languages

• Various simple memory models are possible:

• Queue: First in, first out (like waiting in line)


• Stack: Last in, first out (like a laundry basket)
Stack Memory
A stack can be described as a word over the stack alphabet Γ:

• Empty stack is λ.

• push(X, YZZY ) = XYZZY , push a new element on top (note top=left).

• pop(YZZY ) = ZZY , remove the top element.

• top(YZZY ) = Y , look at the top element.

Note: the empty stack has no top.

 In PDA the stack holds a special symbol Z0 that indicates the bottom of the stack.
Pushdown Automaton
Formally, a pushdown automaton is a nondeterministic machine defined
by the 7-tuple (Q, Σ, Γ, δ, q0, Z0, F), where
,Q is a finite set of states -
- Σ is an input alphabet ,
- Γ is the stack alphabet of symbols that can be pushed on the stack,
δ : Q × Σε × Γε → P(Q × Γ*) is the transition function, where no tuple is -
,mapped to an infinite set
- q0 ∈ Q is the start state,
- Z0 ∈ Γ is the stack start symbol, and
- F ⊆ Q is the set of accepting states.
NOTES
● The automaton accepts if it ends in an accepting state with no
input remaining.
● The language of a PDA is the set of strings that the PDA accepts:
L(P) = { w ∈ Σ* | P accepts w }
● If P is a PDA where L(P) = L, we say that P recognizes L.
Input symbol Top of stack Stack operations
Push or Pop

(a , Z0 ̸ a Z0 )

You might also like