Each of the first five problems describes a language and asks you to present an NFA —with a specified maximum number of states and/or transitions— that accepts that language. In counting states and transitions, you need not include the dead state or any transitions directed to it. Nor do you need to show that state or those transitions, as it is understood that if, in a transition graph, a state q has no outgoing transition on a symbol a, it is as though there were such a transition and it went to the dead state.
1.
Present an NFA having at most five states and eight transitions
that accepts the language
In words, L1 contains precisely those strings over the alphabet {0,1} having 010 as a substring and 1 as a suffix.
Note that a transition labeled by both 0 and 1 counts as two transitions.
Solution:
|
|
2. Present an NFA having at most six states and at most nine transitions that accepts the language
In words, L2 contains precisely those strings over the alphabet {0,1} having either 000 as a suffix or 0011 as a substring.
Note that a transition labeled by both 0 and 1 counts as two transitions.
Solution:
|
3. Present an NFA having at most seven states that accepts the language
In words, L3 contains precisely those strings over the alphabet {a,b,c} in which at least one among the three symbols appears exactly once.
Solution: Here, the machine initially "guesses" which of the three symbols will occur exactly once and follows the corresponding λ-transition.
|
4. Present an NFA having at most eight states (only one final state is necessary) that accepts the language
In words, L4 contains precisely those strings over {0,1} that end either exactly two symbols after an occurrence of 0011 or at least three symbols after an occurrence of 00.
Solution: The "intended" solution, and one that many students provided, was this one:
|
Upon close examination, one notices that any string by which the machine can get to the final state via a path involving states 001 and 0011 also allows for a path to the final state involving the states -2 and -1 instead. Hence, the states 001 and 0011 (and all incident transitions, of course) can be omitted.
This is consistent with the observation that the set of bit strings that end with 0011v, where v is of length two, is a subset of the set of bit strings that end with 00v, where v has length three or more. Of course, if A ⊆ B, then A ∪ B = B. Which means that the description of L4 could have been simplified to
5. Present an NFA having four states and only five non-λ transitions that accepts the language
In words, L5 contains precisely those strings over {a,b,c} that can be "factored" into a sequence of zero or more substrings, where each factor is either aa, aba, ac, or acc. An example of such a string (in which vertical bars have been inserted in order to show the boundaries between adjacent factors) is
You will find it helpful to use at least one λ transition, and maybe more.
Solution:
|
A few students included a transition from state a back to state λ on symbol a, making the λ transition from state a to state a/ab unecessary. However, this tradeoff resulted in the number of non-λ transitions being six, one over the stated limit!
An appropriate algorithm for removing λ-transitions is described in the section titled Step 1 in the web page that describes the Subset Construction algorithm (by which to obtain a DFA equivalent to a given NFA).
| Transition Graph | Table | |||||
|---|---|---|---|---|---|---|
 |
Init? | Final? | State | δ(_,a) | δ(_,b) | δ(_,λ) |
| ✓ | q0 | ∅ | {q1} | ∅ | ||
| q1 | {q0} | ∅ | {q2} | |||
| q2 | {q2} | {q3} | {q3} | |||
| ✓ | q3 | ∅ | {q4} | ∅ | ||
| q4 | ∅ | {q0} | {q1} | |||
Solution: Note that, in the resulting NFA, the final/accepting states are all those that, in the given NFA, can reach a final/accepting state via a sequence of zero or more λ-transitions.
| Init? | Final? | State | δ(_,a) | δ(_,b) |
|---|---|---|---|---|
| ✓ | q0 | ∅ | {q1,q2,q3} | |
| ✓ | q1 | {q0,q2,q3} | {q1,q2,q3,q4} | |
| ✓ | q2 | {q2,q3} | {q1,q2,q3,q4} | |
| ✓ | q3 | ∅ | {q1,q2,q3,q4} | |
| ✓ | q4 | {q0,q2,q3} | {q0,q1,q2,q3,q4} |
7. Present the DFA obtained by applying the Subset Construction algorithm to the NFA shown below. It should have six states.
Present your answer in tabular form (as on the right side of the figure below) rather than as (or in addition to, if you want) a transition graph. Don't forget to identify the initial state and the final states.
Your DFA's state names should make obvious which subset of the NFA's state set each one corresponds to. For example, q{0,2} (or simply {0,2}, if you prefer) could be the name of the state corresponding to the set of states {q0, q2} in the given NFA.
| Transition Graph | Table | ||||
|---|---|---|---|---|---|
 |
Init? | Final? | State | δ(_,a) | δ(_,b) |
| ✓ | q0 | {q1,q2} | {q2} | ||
| q1 | {q1} | {q3} | |||
| q2 | {q0} | {q2,q3} | |||
| ✓ | q3 | {q1} | {q1} | ||
Solution:
| Transition Graph | Table | ||||
|---|---|---|---|---|---|
 |
|||||
| Init? | Final? | State | δ(_,a) | δ(_,b) | |
| ✓ | {0} | {1,2} | {2} | ||
| {1,2} | {0,1} | {2,3} | |||
| {2} | {0} | {2,3} | |||
| {0,1} | {1,2} | {2,3} | |||
| ✓ | {2,3} | {0,1} | {1,2,3} | ||
| ✓ | {1,2,3} | {0,1} | {1,2,3} | ||
8.
 |
(b) Your DFA can be altered easily so that it accepts L(M1) ∪ L(M2). Describe that slight alteration.
(c) Your DFA can be altered easily so that it accepts L(M1) − L(M2) (equivalently, L(M1) ∩ (L(M2))c). (Here we are using the superscript 'c' to mean complement.) Describe that slight alteration.
Solution:
(a)
| Init? | Final? | State | δ(_,a) | δ(_,b) |
|---|---|---|---|---|
| ✓ | [p0,q0] | [p1,q0] | [p2,q1] | |
| [p0,q2] | [p1,q2] | [p2,q2] | ||
| [p1,q0] | [p0,q0] | [p1,q1] | ||
| [p1,q1] | [p0,q0] | [p1,q2] | ||
| [p1,q2] | [p0,q2] | [p1,q2] | ||
| [p2,q1] | [p3,q0] | [p3,q2] | ||
| ✓ | [p2,q2] | [p3,q2] | [p3,q2] | |
| [p3,q0] | [p3,q0] | [p3,q1] | ||
| [p3,q1] | [p3,q0] | [p3,q2] | ||
| [p3,q2] | [p3,q2] | [p3,q2] |
For the resultant DFA to accept the intersection of L(M1) and L(M2), the state [pi,qj] is final/accepting iff pi and qj are final in their respective DFAs. This is why [p2,q2] is the lone final state in the resultant DFA.
(b) To make the resultant DFA accept the union of L(M1) and L(M2), you need not change the transition function at all. Rather, you simply alter which states are classified as being final/accepting. Specifically, you make [pi,qj] final iff either pi or qj is final in its DFA. Here, that means the final states are any that has p2 as its first component or q2 as its second component. Which is to say that the set of final states would be { [p0,q2], [p1,q2], [p2,q1], [p2,q2], [p3,q2] }.
(c) The problem statement was deficient in that it did not make clear which of the two given DFAs was M1 and which was M2. The instructor's intent was for the DFA with p-named states be M1 (which explains why in the resultant DFA the states are named [pi,qj] rather than [qi,pj]), but the diagram came out (unintentionally) with the opposite DFA on top, leading most students to interpret the latter to be M1.
In any case, for the resultant DFA to accept L(M1) − L(M2), all that needs to be changed is the choice of final states. Specifically, a state should be classified as final iff its M1 component is a final state but its M2 component is not.
Taking the DFA with the q-named states to be M1, that would mean that the final states should be any whose q-component is q2 and whose p-component is not p2. Which is to say that the set of final states would be { [p0,q2], [p1,q2], [p3,q2] }
Taking the DFA with p-named states to be M1, the set of final states would include any whose p-component is p2 and whose q-component is not q2. The only such state is [p2,q1]. (State [p2,q0] would be a final state, except that it is not reachable from the initial state and hence need not be considered to be a state in the resultant DFA.)