Skip to main content

Define FSM; design FSA with two consecutive a's

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.

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.

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

Stateab
→ q₀q₁q₀
q₁q₂q₀
*q₂ (final)q₂q₂

Transition diagram

   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.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 2 questions →