Sample Midterm Questions for CSC 8510

Dave Matuszek, Fall 199

For an NFA, explain in plain English what this means:

Delta (the transition function) takes two arguments, a state and an input symbol (or the empty string), and produces as output a set of states.

Describe the language {vwv: v, w 0 {a, b}*, |v|=2} in plain English.

The language consists of strings of a's and b's. Each string is at least four characters long, and the first two characters are the same as the last two characters.

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.

Q = {q0, q1, q2}
Sigma = {a, b, c}
delta =

	a	b	c
q0	q0	q1	q2
q1	q1	q1	q1
q2	q2	q2	q2

Initial state = q0
Final states = {q0, q1} (Thanks to Mike Iaquinto for pointing out that I left out q0.)

---

Give a grammar for the language L. Specify all four parts of the language in detail. No explanations, just symbols.

V = {Q0, Q1, Q2}
T = {a, b, c}
S = Q0
P = { Q0 -> aQ0 | bQ1 | empty,
      Q1 -> aQ1 | bQ1 | cQ1 | empty }

(Thanks to Amrit Singh for pointing out an error in the earlier version.)

---

Is the grammar you just wrote right linear, left linear, or neither?

Right linear.

---

Using the grammar you just wrote, give a derivation for the string abac.

Q0 => aQ0 => abQ1 => abaQ1 => abacQ1 => abac

Using the grammar you just wrote, draw a derivation tree for the string abac.

         Q0
        /  \
       a    Q0
           /  \
          b    Q1
              /  \
             a    Q1
                 /  \
                c    e

Write a regular expression for the above language L.

a* + a*b(a+b+c)*

---

Draw a PDA for the language over {(, )}consisting of balanced strings of parentheses, for example (()(()(())))(). Be sure your PDA accepts the empty string.

 

Here's a revised version (Thanks to Mike Iaquinto for pointing out mistakes in the earlier version.) I'm using a notation that I think is slightly clearer: A, B->C means "If input character is A and top of stack is B, replace top of stack with C. The " z (or 0) is the initial stack symbol.

Comments (not a required part of the answer):

delta (q0, "(", "z") = {(q1, "z")}
    -- if read "(", just go to q1, leave just z on stack
delta (q1, "(", "(") = {(q1, "((")}
delta (q1, "(", "z") = {(q1, "(")}
    -- if read "(", with "(" or z on stack, add "(" to stack
delta (q1, ")", "(") = {(q1, "")}
    -- if read ")", pop matching "(" from stack
delta (q1, "(", "z") = {(q0, "z")}
    -- if read final ")" (z on stack), we're done

---

Convert the following NFA to a DFA. (Hint: each state in the DFA could be labeled with a set of states of the NFA.)