---
title: "Define FSM; design FSA with two consecutive a's"
subject: "Discrete Structure"
chapter: 2
key: "semester_4/discrete_structure:fsa-two-consecutive-a"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/fsa-two-consecutive-a
site: BCT Engineering
---

# Define FSM; design FSA with two consecutive a's

Discrete Structure · Chapter 2: Finite State Automata

- Asked in: 2070 Magh, 2+6 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-two-consecutive-a
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-2

## Question

Define Finite State Machines. Design a Finite State Automata that accepts precisely those strings over {a, b} that contain two consecutive a's. Your design should include the proper definition of the finite-state automaton, transition table and the transition diagram.

## Short answer

DFA with states q0 (no a seen), q1 (last symbol a), q2 (has aa, final trap). On a: q0→q1, q1→q2, q2 loops. On b: q1→q0, q0 loops, q2 loops. Accepts strings with aa.

## Answer

#### Definition
A **finite-state machine (FSM)** is a 6-tuple M = (S, I, O, f, g, s₀): S a finite set of states, I the input alphabet, O the output alphabet, f : S × I → S the next-state function, g : S × I → O the output function and s₀ the initial state. When no output is needed and we only decide acceptance, it is a **finite-state automaton (FSA)** M = (S, I, f, s₀, F), where F ⊆ S is the set of final states. A string is accepted if it takes the machine from s₀ to a state in F.

#### Design
The machine remembers how much of "aa" it has seen:
- q₀: no useful a seen (start, last symbol was b or nothing).
- q₁: the last symbol was a (one a seen).
- q₂: two consecutive a's have been seen (final, a trap: once found, always accepted).

**Formal definition:** M = ({q₀, q₁, q₂}, {a, b}, f, q₀, {q₂})

**Transition table**

| State | a | b |
|---|---|---|
| → q₀ | q₁ | q₀ |
| q₁ | q₂ | q₀ |
| *q₂ (final) | q₂ | q₂ |

**Transition diagram**

```text
   b (loop)                              a,b (loop)
  +--+                                    +--+
  v  |                                    v  |
->(q0)------a------>(q1)------a------>((q2))-+
   ^                  |
   +--------b---------+
```
(q₀ loops on b; q₁ returns to q₀ on b; q₂ loops on a and b.)

#### Check
- *baab*: q₀ → q₀ → q₁ → q₂ → q₂. Accepted.
- *abab*: q₀ → q₁ → q₀ → q₁ → q₀. Rejected (no aa).
- Brute-force test on all strings up to length 10 confirmed the machine accepts exactly the strings containing *aa*.

## Check yourself

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

1. How does an FSM differ from an FSA?
   A. An FSM has an output alphabet and output function; an FSA only decides acceptance using final states
   B. An FSA has output, an FSM has none
   C. An FSM has no start state
   D. An FSA has an infinite set of states
   Answer: A. FSM = (S, I, O, f, g, s0) while the FSA drops outputs and adds F. (Key point: FSM versus FSA)

2. What does q1 remember?
   A. Two a's have been seen
   B. The last symbol was a (one a seen)
   C. The string started with b
   D. The last symbol was b
   Answer: B. From q1 another a completes aa. (Key point: State q1 meaning)

3. Why does q2 loop on both a and b?
   A. Because aa must be at the end
   B. To count more a's
   C. Once aa has been found, the string is always accepted
   D. Because q2 is a dead state
   Answer: C. The condition 'contains aa' cannot be undone. (Key point: Trap state q2)

4. Where does q1 go on b?
   A. To q2
   B. Stays in q1
   C. To a dead state
   D. Back to q0, since the a's are no longer consecutive
   Answer: D. A b breaks the run of a's, so progress restarts. (Key point: Move on b from q1)

## Close variants set in other exams

- [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×
- [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×

## 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 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
- [Regular expression and FSA: at least three b's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-at-least-three-b) — Discrete Structure, chapter 2
- [Differentiate Finite State Machine and Automata](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsm-vs-fsa-difference) — Discrete Structure, chapter 2, asked 2×