State diagram for the PDA M_1 that recognizes {0^n 1^n | n greaterthanorequalto 0} State diagram for PDA M_2 that recognizes {a^i b^j | i, j, k greaterthanorequalto 0 and i = j or i = k} The following is the formal description of the PDA (page 112) that recognizes the language {0^n 1^n greaterthanorequalto 0}. Let M_1 be (Q, sigma, gamma, delta, q_1 F), where Q = {q_1, q_2, q_3, q_4}, sigma = {1, 0}, gamma = {0, $), F = {q_1, q_4}, and delta is given by the following table, wherein blank entries signify theta. We can also use a state diagram to describe a PDA, as in Figures 2.15, 2.17, and 2.19. Such diagrams are similar to the state diagrams used to describe finite automata, modified to show how the PDA uses its stack when going from state to state. We write "a, b rightarrow c" to signify that when the machine is reading an a from the input, it may replace the symbol b on the top of the stack with a c. Any of a, b, and c may be epsilon. If a is epsilon, the machine may make this transition without reading any symbol from the input. If b is Epsilon, the machine may make this transition without reading and popping any symbol from the stack. If c is epsilon, the machine does not write any symbol on the stack when going along this transition. Describe a PDA that recognizes the language L = {w sum {a, b} | w = w^R} = {w sum {a, b} | w is a palindrome}. Use the conventions explained at the bottom of page l14 of our text and illustrated by Figures 2.15 and 2.17 to draw the state diagram for your PDA