- (15pts) Show the sequence of instantaneous descriptions for the acceptance of aabbbb by the following PDA.
- (15pts) What language is accepted by the PDA M = ({, , , , , }, {a, b}, {0, 1, $}, , $,), with
- (20pts) Construct a PDA that accepts the language defined by the grammar S abSb | .
- (20pts) Show that the PDA constructed in Example 7.6 (attached file) accepts the strings aabb and aaabbbb, and that both strings are in the language generated by the given gramar.
- (20pts) Show that is not a context-free language.
- (10pts) Construct a Turning machine that accepts the languageon {a, b}.
(, b, $) = {(, 1$)},
(, b, 1) = {(, 11)},
(, a, 1) = {(, )},
(, a, 1) = {(, )},
(, a, $) = {(, $), (, $)}?
0 comments