Finite Automata Practice Questions

Let the states be $q_0$ (initial), $q_1$, and $q_2$ (final).

1. From $q_0$, if a '1' is read, it stays at $q_0$. If a '0' is read, it moves to $q_1$. $q_0$ represents having not seen a '0' recently, or ending with '1'.
2. From $q_1$, if a '0' is read, it moves to the final state $q_2$. This means the string ended with '00'. If a '1' is read, it returns to $q_0$, as the previous '0' is no longer the penultimate character. $q_1$ represents having just seen a '0' (potential start of '00' suffix).
3. From the final state $q_2$, if a '0' is read, it remains in $q_2$ (e.g., $...000$ still ends with '00'). If a '1' is read, it goes back to $q_0$, as the '00' suffix is broken.
   Therefore, the DFA accepts all strings that have '00' as their suffix.

A. There is a unique minimal DFA for every regular language (up to isomorphism), as guaranteed by the Myhill-Nerode theorem. This statement is true.
B. Every NFA recognizes a regular language. Every regular language is also context-free, and thus can be recognized by a PDA (which can simulate an NFA by simply not using its stack). This statement is true.
C. Every context-free language is a recursive language. Recursive languages are closed under complementation. Thus, the complement of every context-free language is also recursive. This statement is true.
D. Nondeterministic Pushdown Automata (NPDAs) are strictly more powerful than Deterministic Pushdown Automata (DPDAs). There exist context-free languages (e.g., the language of palindromes $\{ww^R \mid w \in \{a,b\}^*\}$) that can be recognized by an NPDA but not by any DPDA. This statement is false.

The automaton starts at $q_0$.

1. From $q_0$, any number of 'b's can be processed via the self-loop: $b^*$.
2. To reach any final state, an 'a' must be processed to transition from $q_0$ to $q_1$. Thus, all accepted strings must start with $b^*a$.

Now, consider the behavior from $q_1$ onwards. Both $q_1$ and $q_2$ are final states.

• From $q_1$:
  • On input 'b', it stays in $q_1$ (a final state).
  • On input 'a', it can go to $q_2$ (a final state) or $q_3$ (a non-final state).
• From $q_2$:
  • On input 'b', it stays in $q_2$ (a final state).
  • On input 'a', it goes to $q_1$ (a final state).
• From $q_3$: (This state is only reachable from $q_1$ on 'a'.)
  • On input 'a', it goes to $q_1$ (a final state).
  • On input 'b', it goes to $q_2$ (a final state).

Since $q_1$ and $q_2$ are final states, and from either $q_1$ or $q_2$, any input 'a' or 'b' either keeps the automaton in a final state or leads to $q_3$ from which any subsequent input immediately leads back to a final state ($q_1$ or $q_2$), it means that once $q_1$ is reached, any subsequent sequence of 'a's and 'b's will be accepted. This pattern is represented by $(a+b)^*$.

Combining these parts, the language accepted by the automaton is $b^*a(a+b)^*$.

To accept strings $w$ where the number of 0s is divisible by 3 and the number of 1s is divisible by 5, a deterministic finite automaton (DFA) must keep track of two independent counts:

1. The remainder of the number of 0s modulo 3. Let this be $q_0$. The possible values for $q_0$ are $\{0, 1, 2\}$.
2. The remainder of the number of 1s modulo 5. Let this be $q_1$. The possible values for $q_1$ are $\{0, 1, 2, 3, 4\}$.

Each state of the DFA can be represented as an ordered pair $(q_0, q_1)$.
The number of possible values for $q_0$ is 3.
The number of possible values for $q_1$ is 5.
The total number of unique states required is the product of the number of possibilities for each independent count:
$\text{Number of states} = (\text{number of remainders for 0s}) \times (\text{number of remainders for 1s})$
$\text{Number of states} = 3 \times 5 = 15$
All these states are reachable and distinct, making it a minimum state DFA. The initial state is $(0,0)$ and the only final state is also $(0,0)$.

The transitions are as follows:

• From state $(q_0, q_1)$ on input '0': the new state is $((q_0+1) \pmod 3, q_1)$.
• From state $(q_0, q_1)$ on input '1': the new state is $(q_0, (q_1+1) \pmod 5)$.

The first step in minimizing a Finite State Automaton (FSA) is to remove any unreachable states.

1. Identify Reachable States: Starting from the initial state $q_0$:

   • From $q_0$: $q_0 \xrightarrow{b} q_0$, $q_0 \xrightarrow{a} q_1$. States $q_0, q_1$ are reachable.
   • From $q_1$: $q_1 \xrightarrow{b} q_1$, $q_1 \xrightarrow{a} q_2$. State $q_2$ is reachable.
   • From $q_2$: $q_2 \xrightarrow{b} q_2$, $q_2 \xrightarrow{a} q_1$. No new states.
   • State $q_3$ has no incoming transitions from $q_0, q_1, q_2$. Therefore, $q_3$ is unreachable from the start state $q_0$ and can be removed.
     The set of reachable states is $\{q_0, q_1, q_2\}$.

2. Apply the Partition Method (or Table-Filling):

   • Initial Partition $P_0$: Group states into non-accepting and accepting sets.
     $F = \{q_1, q_2\}$ (Accepting states)
     $N = \{q_0\}$ (Non-accepting states)
     $P_0 = \{\{q_0\}, \{q_1, q_2\}\}$
   • Refine Partition $P_1$: Check if any block needs to be split.
     • Consider the block $\{q_1, q_2\}$:
       • For input 'a': $\delta(q_1, a) = q_2$ and $\delta(q_2, a) = q_1$. Both $q_1, q_2$ transition to states within the same block $\{q_1, q_2\}$.
       • For input 'b': $\delta(q_1, b) = q_1$ and $\delta(q_2, b) = q_2$. Both $q_1, q_2$ transition to states within the same block $\{q_1, q_2\}$.
         Since $q_1$ and $q_2$ behave identically with respect to the blocks in $P_0$ for all inputs, they remain in the same block. The block $\{q_0\}$ has only one state, so it cannot be split.
         $P_1 = \{\{q_0\}, \{q_1, q_2\}\}$
   • Since $P_1 = P_0$, the algorithm terminates.

The minimal FSA has 2 states, corresponding to the blocks $[q_0]$ and $[q_1, q_2]$.

The final answer is $\boxed{B}$