Skip to main content

Design FSA for strings beginning with baa

Short answer

DFA with states q0 (start), q1, q2, q3 (final), and dead state d. Transitions: b to q1, then a to q2, a to q3; any other input goes to d. q3 loops on a,b. Only prefixes baa accepted.

Design a finite-state automata that accepts only those set of strings over {a, b} which starts with baa. Precisely, only those strings which begin with baa should be accepted and other strings over {a, b} should be rejected. Your design should include the proper definition of the finite-state automata, transition table and the transition diagram.

Definition

A finite-state automaton is a 5-tuple M = (S, I, f, s₀, F): S a finite set of states, I the input alphabet, f : S × I → S the transition function, s₀ ∈ S the start state and F ⊆ S the set of final states. A string is accepted when it drives M from s₀ into a state of F. (For a DFA, f gives exactly one next state.)

Design

The machine checks the first three symbols b, a, a one by one. Any wrong symbol sends it to a dead (trap) state d. After baa is read, whatever follows is allowed, so the final state loops on both symbols.

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

Transition table

Stateab
→ q₀dq₁
q₁q₂d
q₂q₃d
*q₃ (final)q₃q₃
d (dead)dd

Transition diagram

 ->(q0)--b-->(q1)--a-->(q2)--a-->((q3))  a,b loop
    |          |         |
    a          b         b
    v          v         v
    +--------->(d)<------+     d loops on a,b

Check

  • baab: q₀ → q₁ → q₂ → q₃ → q₃. Accepted.
  • bab: q₀ → q₁ → q₂ → d. Rejected. abaa: q₀ → d. Rejected.
  • baa itself is accepted, since q₃ is reached at the end.
  • Brute-force test (all strings up to length 10) confirmed the language is exactly the set of strings that begin with baa.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 2 questions →