Dave Matuszek, Fall 199
For an NFA, explain in plain English what this means:
Describe the language {vwv: v, w 0 {a, b}*, |v|=2} in plain English.
Consider a language L over the alphabet {a, b, c} for
which the only restriction is that c may not occur until after at least one b has
occurred. For example, some strings belonging to this language are e, a, b, aa, ab, ba, bb, aaa,
aab, aba, abb, abc, baa, bab, bac, bcc, abac, …. The following questions refer
to this language.
Draw a complete DFA for this language (don’t omit any states).
Completely define the DFA for this language without a drawing: specify values for each of the five parts of a DFA (use a table to show the transition function). I don’t want sentences or explanations, just symbols.
Give a grammar for the language L. Specify all four parts of the language in detail. No explanations, just symbols.
Is the grammar you just wrote right linear, left linear, or neither?
Using the grammar you just wrote, give a derivation for the string abac.
Using the grammar you just wrote, draw a derivation tree for the string abac.
Write a regular expression for the above language L.
Draw a PDA for the language over {(, )}consisting of balanced strings of parentheses, for example (()(()(())))(). Be sure your PDA accepts the empty string.
Convert the following NFA to a DFA. (Hint: each state in the DFA could be labeled with a set of states of the NFA.)
