Consider the following PDA that accepts the language {x/x = wwʼand w in {0,1}*} . M={{q1, 92}, {0,1}, {R, B, G}, 8, 91/R
Posted: Sat Feb 19, 2022 3:20 pm
- Consider The Following Pda That Accepts The Language X X Wwand W In 0 1 M Q1 92 0 1 R B G 8 91 R 1 (70.46 KiB) Viewed 32 times
Consider the following PDA that accepts the language {x/x = wwʼand w in {0,1}*} . M={{q1, 92}, {0,1}, {R, B, G}, 8, 91/R.0) 8: (1) 8(91, 0, R) = (q1, BR)} (2) 8(91, 1, R)= {{qi, GR)} (3) 8(91, 0, B) = {(91, BB), (42, E)} (4) 8(91, 0, G) = {(91, BG)} (5) 8(q1, 1, B) = {(91, GB)} (6) 8(91, 1, G)= {(qi, GG), (92, €)} (7) 8(92, 0, B) = {(q2, )} (8) 8(92, 1, G)= {(92, ε)} (9) 8(91, £, R) = {(92, £)} (10) 8(92, E, R) = {(42, E)} (a) (10 points) Show an accepting computation of M on the string 011110. (b) (5 points) Suppose &(q2, 0, G) = {(92, c)} was added to the above list of rules. Would the PDA still accept the same language (yes or no)? Be sure to explain your answer (hint: give an example string).