Let x be a string, and let M be a Finite Automaton with just one Final State that accepts the strings x and xx.

(a) Prove, by induction on n,  that M accepts the string $x^n$ for every  n ≥ 1.

(b) Would the same statement hold if M is a Nondeterministic Finite Automaton, also with just one Final State, instead?  Why or why not?

Let the start state of $M$ be $q_0$ and the single final state be $q_f$.

---

(a) Proof for a Deterministic Finite Automaton (FA)

Yes, this statement is true. We can prove it by induction on $n$.

Let $\delta^*(q, w)$ be the extended transition function, representing the state the machine is in after starting at state $q$ and processing the entire string $w$.

1. Deriving the Crucial Premise:

Before starting the induction, we must use the given information.

• Premise 1: $M$ accepts $x$. Since $M$ is a DFA and has only one final state ($q_f$), this means processing $x$ from the start state $q_0$ must lead to $q_f$.
  • Formally: $\delta^*(q_0, x) = q_f$.
• Premise 2: $M$ accepts $xx$. This means processing $xx$ from $q_0$ must also lead to $q_f$.
  • Formally: $\delta^*(q_0, xx) = q_f$.
• Connecting the Premises: By the definition of the extended transition function, processing $xx$ is the same as processing $x$ from the state reached after processing the first $x$.
  • $\delta^*(q_0, xx) = \delta^*(\delta^*(q_0, x), x)$
• Substitution: We can now substitute our findings from Premise 1 into this equation:
  • $\delta^*(q_0, xx) = \delta^*(q_f, x)$
• Conclusion: Since we know $\delta^*(q_0, xx) = q_f$ (from Premise 2), we can conclude:
  • $\delta^*(q_f, x) = q_f$

This is the critical fact: processing the string $x$ from the final state leads back to that same final state. This creates a "loop" on the string $x$.

2. The Inductive Proof:

We will prove the proposition $P(n)$: "$M$ accepts $x^n$", which means $\delta^*(q_0, x^n) = q_f$.

• Base Case (n=1): We must show $P(1)$ is true. $P(1)$ states that $M$ accepts $x^1$, or just $x$. This is given explicitly in the problem statement (Premise 1). Thus, the base case holds.

• Inductive Hypothesis (IH): Assume $P(k)$ is true for some arbitrary integer $k \geq 1$. That is, assume $\delta^*(q_0, x^k) = q_f$.

• Inductive Step: We must prove that $P(k+1)$ is true, meaning we must show that $\delta^*(q_0, x^{k+1}) = q_f$.

  1. Start by definition: The string $x^{k+1}$ is just the string $x^k$ followed by the string $x$.
  2. Using the definition of the extended transition function: $\delta^*(q_0, x^{k+1}) = \delta^*(q_0, x^k \cdot x) = \delta^*(\delta^*(q_0, x^k), x)$
  3. By our Inductive Hypothesis, we know $\delta^*(q_0, x^k) = q_f$. We substitute this into the equation: $\delta^*(q_0, x^{k+1}) = \delta^*(q_f, x)$
  4. From our initial derivation (Connecting the Premises), we proved that $\delta^*(q_f, x) = q_f$.
  5. Therefore: $\delta^*(q_0, x^{k+1}) = q_f$.

• Conclusion: This is exactly the statement $P(k+1)$. Since we have established the base case and shown that $P(k) \implies P(k+1)$, by the principle of mathematical induction, the statement $P(n)$ is true for all $n \geq 1$.

---

(b) Case for a Nondeterministic Finite Automaton (NFA)

No, the same statement would not hold if $M$ is an NFA.

Why:

The critical step in the proof for part (a) was concluding that $\delta^*(q_f, x) = q_f$. This was possible because a DFA has exactly one computation path.

In an NFA, "acceptance" means at least one computation path ends in a final state. The accepting path for $x$ and the accepting path for $xx$ do not have to be related in the same way.

The NFA accepting $x$ only guarantees that $q_f \in \delta^*(q_0, x)$ (where $\delta^*$ now returns a set of states). The NFA accepting $xx$ only guarantees that $q_f \in \delta^*(q_0, xx)$.

This second fact means there exists some state $q_i$ such that:

1. $q_i \in \delta^*(q_0, x)$
2. $q_f \in \delta^*(q_i, x)$

The problem is that this $q_i$ does not have to be $q_f$. The machine could have two paths for $x$: one that goes to $q_f$ (to accept $x$) and another that goes to some intermediate state $q_i$, which then goes to $q_f$ on another $x$ (to accept $xx$). In this scenario, the final state $q_f$ itself can lead to no state at all on input $x$.

Counterexample:

Let $x = a$ and let $M$ be an NFA with:

• States: $\{q_0, q_1, q_f\}$
• Start State: $q_0$
• Final State (singular): $\{q_f\}$
• Transitions:
  • $\delta(q_0, a) = \{q_1, q_f\}$ (On 'a', the NFA can go to $q_1$ OR $q_f$)
  • $\delta(q_1, a) = \{q_f\}$ (From $q_1$, an 'a' goes to $q_f$)
  • $\delta(q_f, a) = \emptyset$ (From $q_f$, an 'a' goes nowhere/crashes)

Let's check this counterexample against the problem's conditions:

1. Is there only one Final State? Yes, $\{q_f\}$.
2. Does it accept $x$ (which is $a$)? Yes. On input 'a', one computation path is $q_0 \rightarrow q_f$. Since this path ends in the final state, $a$ is accepted.
3. Does it accept $xx$ (which is $aa$)? Yes. One computation path is $q_0 \xrightarrow{a} q_1 \xrightarrow{a} q_f$. This path consumes all input ($aa$) and ends in the final state, so $aa$ is accepted. (Note: the path $q_0 \xrightarrow{a} q_f \xrightarrow{a} ...$ crashes, but that doesn't matter since another path succeeded).

Now, check the conclusion:

• Does it accept $x^3$ (which is $aaa$)?
  • Path 1: $q_0 \xrightarrow{a} q_f \xrightarrow{a} ...$ (This path crashes after one 'a').
  • Path 2: $q_0 \xrightarrow{a} q_1 \xrightarrow{a} q_f \xrightarrow{a} ...$ (This path crashes after two 'a's, because $\delta(q_f, a)$ is empty).

Since all possible computation paths for $aaa$ fail to consume the string while ending in a final state, the string $aaa$ ($x^3$) is rejected. This disproves the statement for NFAs.

Changelog

9/7/25, 2:50 AM

View All Changelog

• f50a2-docs: exam prep FAon 9/7/25

Copyright

Copyright Ownership:WARREN Y.F. LONG

License under:Attribution-NonCommercial-NoDerivatives 4.0 International (CC-BY-NC-ND-4.0)