First example

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:






Transition function for aabb
push a
push a
pop a
pop a
accept

Transition function 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 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”.



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) pop b
® (q2, a, z0) pop a
® (q2, e, 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, 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) ??(q0, bba, a) // push a
– ??(q0, ba, ba) // push b
– ??(q0, a, bba) // push b
– ??(q1, a, bba) // ??transition
– Nowhere to go // Reject!

Let’s see a good transition set for abba
– (q0, abba, Z) ??(q0, bba, a) // push a
– ??(q0, ba, ba) // push b
– ??(q1, ba, ba) // ?transition
??????????????????????(q1, a, a) // pop b
– ??(q1, e, Z) // pop 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}