- Make A Push Down Automata For Each Language A E X Y Z L 0 X Y Z Where 0 X 0 Strings That Do No 1 (268.86 KiB) Viewed 11 times
Make a Push Down Automata for each language: a. E = { x y z }, L = { 0 € {x,y,z}* where |0|x # |0|₂} (Strings that do not have the same number of x's as they do z's). Example: yyyzyyzyyyyxxx b. Σ = {xyz }, L = { 0 € {x,y,z}* where lolx +10ly = |o|₂} (Strings where the number of x's plus the number of y's equals the number of z's). Example: zzxyxzyyxzxzzz See the following example: Σ = { a b c }, L = { a¹biciti, 0 ≤ i, 0 ≤ j}. 91 92 93 91 94 95 Input: Stack: X €, € → $ $ a, ex a 92 E E, E → E {(92, x)} b, ε → x For every a and b read in the first part of the string, the PDA pushes an x onto the stack. Then it must read a c for each x popped off the stack. We formally express the PDA as a 6-tuple (Q, Σ, 5, 8, 9₁, F), where • Q = {91, 92, ..., 95} • Σ = {a,b,c} •[= {x, $} (use $ to mark bottom of stack) • transition function 8 : Q × × [ɛ → P(Q × ¯e) is defined by b X $ Blank entries are Ø. • q₁ is the start state • F = {95} 93 E ɛ, € → E {(93,x)} C, x→ E X с 94 {(94, e)] €, $ → e $ E X 95 $ E {(95, €) } € {(92, $) } {(93, €) } {(94, €) }