Lec 18 : Computation Theory Examples of PDA
1
Continuing first Example
L={aibi, i>=1}
a,z0 / az0
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” go to final state
Describe transition function:
? ( q0 , a , Zo ) ( q0 , aZo ) ?
?(q0 , a ,a ) ( q0 , a0 ) ?
? ( q ,b , a ) ( q , ) 0 1 ? ?
a,a / aa b,a / ?
b,a / ?
q ?,z0 / z0 0
q0
q1 q2
Lec 18 : Computation Theory Examples of PDA
2
? ( q , b , a ) ( q , ) 1 1 ? ?
?(q1, ,Zo) (q2 ,Zo) ? ?
Transition function for aabb
(q0,aabb,z0 )?(q0,abb,az0 ) push a
?(q0,bb,aa) push a
?(q1,b,a) pop a
?(q1,?,z0 ) pop a
?(q2,?,z0 ) accept
Transition function for abb
(q0,aab,z0 )?(q0,bb,az0 ) push a
?(q1,b,z0 ) pop a
?(q1,b,z0 ) Reject
Second example:
L = { xcx
r
| x ??{ a,b }
*
}
-Basic idea for building a PDA:
- read chars from the tape until you reach 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”.
Lec 18 : Computation Theory Examples of PDA
3
Continuing our example:
L = { xcx
r
| x ??{ 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:
?(q0,a,z0 )?(q0,az0 )
?(q0,b,z0 )?(q0,bz0 )
?(q0,a,a)?(q0,aa)
?(q0,b,b)?(q0,bb)
?(q0,a,b)?(q0,ab)
?(q0,b,a)?(q0,ba)
?
?
?
Lec 18 : Computation Theory Examples of PDA
4
?(q0,c,z0 )?(q1,z0 )
?(q1,c,a)?(q1,a)
?(q0,c,b)?(q1,b)
?(q1,?,z0 )?(q2,z0 )
?(q1,?,a)?(q2,a)
?(q1,?,b)?(q2,b)
?(q2,b,b)?(q2,?)
?(q2,a,a)?(q2,?)
?(q2,?,z0 )?(q3, z0 )
Transition for abcba
(q0,abcba, z0) ? (q0, bcba,az0) push a
? (q0, cba, ba) push b
? (q1, ba, ba) goto 2
? (q2, ba, a) pop b
? (q2, a, z0) pop a
? (q2, ?, z0) 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, ?,a) pop b
reject!
Lec 18 : Computation Theory Examples of PDA
5
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.
Lec 18 : Computation Theory Examples of PDA
6
Describe transition function:
?(q0,a,z0 )?(q0,az0 )
?(q0,b,z0 )?(q0,bz0 )
?(q0,a,a)?(q0,aa)
?(q0,b,b)?(q0,bb)
?(q0,a,b)?(q0,ab)
?(q0,b,a)?(q0,ba)
?(q0,?,z0 )?(q1,z0 )
?(q1,?,a)?(q1,a)
?(q0,?,b)?(q1,b)
?(q1,b,b)?(q1,?)
?(q1,a,a)?(q1,?)
?
?
?
Lec 18 : Computation Theory Examples of PDA
7
?(q1,?,z0 )?(q2, z0 )
Let’s see a bad transition set for abba
– (q
0
, abba, Z) ??(q
0
, bba, a) // push a
– ??(q
0
, ba, ba) // push b
– ??(q
0
, a, bba) // push b
– ??(q
1
, a, bba) // ??transition
– Nowhere to go // Reject!
Let’s see a good transition set for abba
– (q
0
, abba, Z) ??(q
0
, bba, a) // push a
– ??(q
0
, ba, ba) // push b
– ??(q
1
, ba, ba) // ?transition
??????????????????????(q
1
, a, a) // pop b
– ??(q
1
, ?, Z) // pop a
– ??????????????(q
2
, ?, Z) // Accept!
H.W
1-Build the PDAs that accept these languages:
a- L={ x ? {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}