---
title: "Construct FSA accepting reverse language"
subject: "Discrete Structure"
chapter: 2
key: "semester_4/discrete_structure:fsa-reverse-language-construction"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/fsa-reverse-language-construction
site: BCT Engineering
---

# Construct FSA accepting reverse language

Discrete Structure · Chapter 2: Finite State Automata

- Asked in: 2075 Bhadra, 5 marks
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/fsa-reverse-language-construction
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-2

## Question

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]]

## 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.

## Answer

**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→ σ₁.

| State | a | b |
|---|---|---|
| → σ₁ | σ₁ | σ₂ |
| σ₂ | σ₁ | σ₃ |
| *σ₃ | σ₁ | σ₃ |

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 σ₁)

| State | a | b |
|---|---|---|
| → σ₃ | ∅ | {σ₂, σ₃} |
| σ₂ | ∅ | {σ₁} |
| *σ₁ | {σ₁, σ₂, σ₃} | ∅ |

```text
       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).

| State | a | b |
|---|---|---|
| → {σ₃} | ∅ | {σ₂,σ₃} |
| {σ₂,σ₃} | ∅ | {σ₁,σ₂,σ₃} |
| *{σ₁,σ₂,σ₃} | {σ₁,σ₂,σ₃} | {σ₁,σ₂,σ₃} |
| ∅ | ∅ | ∅ |

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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is the first step in building an FSA for Lᴿ?
   A. Swap the labels a and b
   B. Delete the dead states
   C. Complement the machine
   D. Reverse the direction of every arrow, keeping labels
   Answer: D. A path read backwards in the reversed machine matches the original path. (Key point: Reversal method)

2. How are start and final states treated?
   A. Old final becomes new start; old start becomes new final
   B. Both stay the same
   C. Old start becomes new start and final
   D. Only final states are swapped with non-final states
   Answer: A. The reversed string starts where the original ended. (Key point: Start and final)

3. If the original has several final states, what is added?
   A. A dead state
   B. A new start state with ε-moves to the old finals
   C. Extra loops on the start
   D. A second start state with no moves
   Answer: B. An NFA has just one start state. (Key point: Several finals)

4. If L = strings ending in bb, what is Lᴿ?
   A. Strings ending in bb
   B. Strings containing bb
   C. Strings that begin with bb
   D. Strings that begin with ab
   Answer: C. Reversing the strings turns a suffix bb into a prefix bb. (Key point: Resulting language)

## Related in Discrete Structure

- [Design FSA for strings beginning with baa](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-strings-beginning-baa) — Discrete Structure, chapter 2
- [Design FSA accepting even number of a's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-even-number-of-a) — Discrete Structure, chapter 2, asked 4×
- [Design FSA accepting odd number of b's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-odd-number-of-b) — Discrete Structure, chapter 2, asked 4×
- [Language of grammar; grammar for strings not ending in ab](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Alanguage-of-grammar-and-grammar-not-ending-ab) — Discrete Structure, chapter 2
- [Design NFA for strings ending with aba](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Anfa-strings-ending-aba) — Discrete Structure, chapter 2
- [Define FSM; design FSA with two consecutive a's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-two-consecutive-a) — Discrete Structure, chapter 2, asked 4×

## Related in other subjects

- [Boussinesq stress below circle center](https://www.bctengineer.com/question.md?key=semester_4%2Fsoil_mechanics%3Aboussinesq-circle-center-stress) — Soil Mechanics, chapter 8
- [Double field theory; not self-starting](https://www.bctengineer.com/question.md?key=semester_4%2Felectrical_machine%3Adfrt-not-self-starting-proof) — Electrical Machine, chapter 7, asked 2×
- [Area of one loop of r = a sin 3θ](https://www.bctengineer.com/question.md?key=semester_1%2Fmathematics_i%3Aarea-one-loop-sin-3theta) — Mathematics I, chapter 2
- [Stability after tripping one circuit](https://www.bctengineer.com/question.md?key=semester_5%2Fpower_system_analysis_ii%3Aone-line-tripped-stability) — Power System Analysis II, chapter 6