Skip to main content

Construct FSA accepting reverse language

Short answer

To reverse, reverse all transitions, make the old final state the new start, and old start the final state, obtaining an NFA for L^R. For the given DFA accepting strings ending in bb, L^R accepts strings beginning with bb.

Let L be the set of strings accepted by the FSA shown below. Now construct a FSA that accepts the strings L^R = {x_n ... x_1 | x_1 ... x_n ∈ L}. [Figure: FSA with states σ1 (start, with a self-loop on a), σ2, and σ3 (accepting, double circle, with a self-loop on b); transitions labelled b between σ1 and σ2, b from σ2 to σ3, and arcs labelled a below the states, one running back from σ3 and one near σ2 [exact arrow directions unclear in scan]]

Reading of the figure (assumed): σ₁ is the start state with a loop on a; σ₃ is the final state with a loop on b. Transitions: σ₁ -b→ σ₂, σ₂ -b→ σ₃, σ₂ -a→ σ₁ and σ₃ -a→ σ₁.

Stateab
→ σ₁σ₁σ₂
σ₂σ₁σ₃
*σ₃σ₁σ₃

This machine accepts L = strings over {a, b} that end in bb.

Method to build an FSA for Lᴿ

  1. Reverse the direction of every arrow (keep the labels).
  2. Make the old final state(s) the new start state.
  3. Make the old start state the new final state.
  4. If there are several old final states, add a new start state with ε-moves to them. (Here there is just one.)

The result is an NFA for Lᴿ, because a string x₁…xₙ is accepted by the original exactly when xₙ…x₁ is accepted by the reversed machine (reading the same path backwards).

Reversed machine (start σ₃, final σ₁)

Stateab
→ σ₃∅{σ₂, σ₃}
σ₂∅{σ₁}
*σ₁{σ₁, σ₂, σ₃}∅
       b                               a
      ┌─┐                             ┌─┐
      ↓ │                             ↓ │
 ──→ ( σ3 ) ──b──→ ( σ2 ) ──b──→ (( σ1 ))

(σ₃ loops on b and σ₁ loops on a. Also σ₁ -a→ σ₂ and σ₁ -a→ σ₃, which are the reversed arcs of σ₂ -a→ σ₁ and σ₃ -a→ σ₁.)

Equivalent DFA (subset construction)

Start {σ₃}. On b: {σ₂, σ₃}. On b again: {σ₁, σ₂, σ₃} (contains σ₁, so final). From that set both a and b stay in it; from the first two sets an a leads to the empty set (dead).

Stateab
→ {σ₃}∅{σ₂,σ₃}
{σ₂,σ₃}∅{σ₁,σ₂,σ₃}
*{σ₁,σ₂,σ₃}{σ₁,σ₂,σ₃}{σ₁,σ₂,σ₃}
∅∅∅

So Lᴿ = strings that begin with bb, which is the reverse of "end with bb". This was confirmed by testing all strings up to length 10.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 2 questions →