Pushdown Automata
A pushdown automata (PDA) recognize CFL it is essentially like NDFA but have an extra component called stack. This extra component allows the automaton to have memory(in principle, infinite amount of memory), and to recognize some no regular languages.
A PDA can write (push) a symbol on the top of stack or remove (pop) a symbol from the top the stack. The stack is unlimited and works as LIFO storage device.
A “move” of a PDA will depend on
1-Current state of machine
2- Current symbol in input tape
3- Current symbol on the top of stack
With each “move”, the machine can
-Move into a new state
-Push symbol to the stack, remove or no any thing.
The stack
- The stack has its own alphabet(?)
- Included in this alphabet is a special symbol used to indicate an empty stack (Z0)
- This special symbol should not be removed from the stack
To formalize:
–A pushdown automata (PDA) is a 7-tuple:
M = (Q, ?, ?, q0, z0, A, d) where
– Q = finite set of states
– ??= tape alphabet
– ? = stack alphabet
–q0I?Q = start state
– Z0I ? ?= initial stack symbol
–A ? ?Q = set of accepting states
transition function
• The transition function d:
– During a move of a PDA:
• At most one character is read from the input tape
L transitions are okay (don’t move the reading head)
• The topmost character is popped from the stack
Unless it is Z0
• The machine will move to a new state based on:
- The character read from the tape
- The character on the top of stack
- The current state of the machine
• Zero or more symbols from the stack alphabet are pushed onto the stack.
Transition function continued:
– d: Q x (S E {L}) x G (finite subsets of Q x G*)
Domain:
• Q = state
• ? E {L} = current symbol read from the tape
• ? = current symbol on the top of stack
Range
• Q = new state
• ?* = symbols pushed on the stack
When the character L is read from the TAPE, it means that we are out of input letters. The L-edge will lead to ACCEPT if the state we have stopped in is a final state and to REJECT if the Processive stops in a state that is not a final state.
Example
? (q,a,a)=(p,aa)
. Meaning:
- when in state q,
- reading in an ‘a’ from the tape
- with an ‘a’ on the top of stack
The machine will
- go into state p
- push an ‘a’ on the top of stack
Configuration of a PDA
– (p, x, ?) where
• p is the current state
• x is a string indicating what remains to be read on the tape
• ? is the current contents of the stack.
The language accepted by a PDA:
There are two natural ways to define this language:
1- Define the language accepted to be the set of all inputs for which some of sequence of moves cause the PDA to empty stack. This language called “language accepted by empty stack”
2- Define the language accepted to be the set of all inputs for which some choice of moves causes the PDA to enter a final state.
First example
L={aibi, i>=1}
Basic idea for building a PDA:
- read chars “a” from the tape until you reah the “b”.
- as you read chars “a” push them on the stack.
- when you read “b”, check the top stack if “a” then pop it and move to the new state
- read chars “b” from the tape and check the top stack, if “a” then pop and stay at the same state, until the tape is empty and on the stack “z0” goto final state
Continuing first Example
L={aibi, i>=1}
|
Describe transition function:
Transition for aabb
push a
push a
pop a
pop a
accept
Transition for abb
push a
pop a
Reject
Second example:
L = { xcxr | x I { a,b }* }
-Basic idea for building a PDA:
- read chars from the tape until you reah the “c” (marker).
- as you read chars push them on the stack.
- after reading the “c”, match the chars read with the chars on the stack, if match then pop char from stack, until all chars read.
-if at any point the char read does not match the char popped, the machine “fails”.
Continuing our example:
– L = { xcxr | x I { a,b }* }
– The PDA will have 4 states
• State 0 (initial) : reading before the ‘c’
• State 1: read the ‘c’
• State 2 :read after ‘c’, comparing chars
• State 3: (accepting): move only after all chars read and stack empty
Describe transition function:
Transition for abcba
(q0,abcba,z0) ® (q0, bcba,az0) push a
® (q0, cba, ba) push b
® (q1, ba, ba) goto 2
® (q2, ba, a)
® (q2, a, z0) pop b
® (q2, e, z0) pop a
Accept
Transition for abcb
(q0, abcba,z0) ®? (q0,bcb,az0) push a
®? (q0, cb,ba) push b
®? (q1, b,ba) goto 2
® ??(q2, b,ba)
® (q2, e,a) pop b
reject!
Another Example:
– L = { xxr | x { a,b }* }
Basic idea for building a PDA
Much like last example, except
- this time we don’t know when to start popping and comparing
- since PDAs are non-deterministic, this is not a problem
– The PDA will have 3 states
• State 0 (initial) : reading before the center of string
• State 1: read after center of string, comparing chars
• State 2 (accepting): after all chars read, stack should be empty
– The machine can choose to go from state 0 to state 1 at any time:
• Will result in many “wrong” set of moves
• All you need is one “right” set of moves for a string to be accepted.
Describe transition function:
Let’s see a bad transition set for abba
– (q0, abba, Z) a (q0, bba, a) // push a
– a (q0, ba, ba) // push b
– a (q0, a, bba) // push b
– a (q1, a, bba) // L transition
– Nowhere to go // Reject!
Let’s see a good transition set for abba
– (q0, abba, Z) a (q0, bba, a) // push a
– a (q0, ba, ba) // push b
– a (q1, ba, ba) // Ltransition
a (q1, a, a) // pop b
– a (q1, e, Z) // pop a
– a (q2, e, Z) // Accept!
H.W
1-Build the PDAs that accept these languages:
a- L={ x I {a, b}* | na(x)>nb(x)}
b- L={0n1m, n,m 1,m=2n}
2- Formalize the PDA that accept the language
L={aibj, i>j 1}
My Best Wishes
Mohamed U. Mahdi
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .