Finite Automata

The question asks for the FALSE statements.

• (A) True statement: a smaller NFA can exist. For example, if the given NFA (with \(n \ge 2\)) accepts every string, a 1-state NFA also accepts \(L\).
• (B) True statement: in the same example a 1-state DFA accepts \(L\), so a DFA with fewer than \(n\) states is possible.
• (C) True statement: the subset construction turns any \(n\)-state NFA into an equivalent DFA with at most \(2^{n}\) states.
• (D) False: by (C), some DFA for \(L\) has at most \(2^{n}\) states, so not every DFA can have more than \(2^{n}\).

Answer: D

Label the states \(q_0\) (start), \(q_1\), \(q_2\), \(q_3\) (accepting) from left to right. \(q_0\) loops on \(a\) and goes to \(q_1\) on \(b\); \(q_1\) loops on \(b\) and goes to \(q_2\) on \(a\); \(q_2\) goes to \(q_3\) on \(b\) and back to \(q_0\) on \(a\); \(q_3\) goes to \(q_2\) on \(a\) and to \(q_1\) on \(b\).

So \(q_1\), \(q_2\) and \(q_3\) mean that the input read so far ends with \(b\), \(ba\) and \(bab\). The DFA accepts exactly the strings ending with \(bab\), so (C) is correct.

• (A) is wrong: \(bb\) has an even number of \(b\)'s but is rejected, while \(babab\) has three and is accepted.
• (B) is wrong: \(baba\) contains \(bab\) but ends in \(q_2\).
• (D) is wrong: \(b\) does not contain \(aba\) but is rejected.

Answer: C

Minimise by partition refinement. The output depends on the input (a Mealy machine), so first group the states by their output pair for \(X = 0\) and \(X = 1\).

• By outputs: {A, B, C, E} have (0, 0), {D, H} have (1, 0), {F} has (1, 1) and {G} has (0, 1).
• On \(X = 0\), A and C go to F but B and E go to D, and F, D are in different groups. So {A, B, C, E} splits into {A, C} and {B, E}. D and H have identical rows (G, A), so they stay together.
• Next pass: A goes to (F, B) and C to (F, E), with B and E now in one group; B, E and D, H still have identical rows. Nothing splits further.

The groups {A, C}, {B, E}, {D, H}, {F}, {G} give 5 states.

Answer: 5

A DFA only needs the product read so far as a residue mod 7, with residue 2 accepting. No symbol is a multiple of 7 and 7 is prime, so the product never becomes 0 and no dead state is needed. All six non-zero residues are reachable from the start state 1: 1, 2, 3, 4 directly, \(3 \times 4 \equiv 5\) and \(2 \times 3 = 6\).

The six states are pairwise distinguishable. For residues \(r \ne s\), take a string \(y\) with \(\mathit{prod}(y) \equiv 2r^{-1} \pmod{7}\) (one exists, since every non-zero residue is reachable). It takes \(r\) to 2 and accepts, but takes \(s\) to \(2sr^{-1} \not\equiv 2\) and rejects.

So the minimum DFA has 6 states.

Answer: 6

Each state records \(n_{0} - n_{1} \bmod 3\) for the input read so far: a 0 adds 1 and a 1 subtracts 1. State 1 is residue 0, states 2 and 5 are residue 1, and states 3 and 4 are residue 2; every arrow fits (for example, 3 goes to 2 on a 1, and 5 goes to 4 on a 0). So \(L(M)\) is the set of strings with \(n_{0}(w) - n_{1}(w) \equiv 0 \pmod{3}\).

• (A) is true: the input 1 takes state 2 to the accepting state 1 but takes state 4 to state 5.
• (B) and (C) are false: 3 and 4 have the same residue, as do 2 and 5, so every suffix leads both states of a pair to the same verdict. They are equivalent, not distinguishable.
• (D) is true: equal counts give a difference of 0.

Answer: B, C