---
title: "Design FSA for strings beginning with baa"
subject: "Discrete Structure"
chapter: 2
key: "semester_4/discrete_structure:fsa-strings-beginning-baa"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/fsa-strings-beginning-baa
site: BCT Engineering
---

# Design FSA for strings beginning with baa

Discrete Structure · Chapter 2: Finite State Automata

- Asked in: 2068 Bhadra, 3+2+3 marks
- Video: [DFA Examples 1 & 2 || Set of all strings Begins with "a" || Starts with "ab" || FLAT||TOC](https://www.youtube.com/watch?v=EgeFoVHA-A4) — Sudhakar Atchala
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/fsa-strings-beginning-baa
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-2

## Question

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.

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

## Answer

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

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

**Transition diagram**

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

## Check yourself

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

1. What is the dead state d used for?
   A. Counting extra symbols after baa
   B. Any wrong symbol among the first three sends the string there; it can never accept
   C. Marking the start of the string
   D. Accepting strings that end in baa
   Answer: B. Strings not starting with baa must be rejected permanently. (Key point: Role of dead state)

2. Why does the final state q3 loop on a and b?
   A. To check the string ends with baa
   B. To count symbols
   C. Anything may follow baa, so acceptance stays
   D. To return to q0
   Answer: C. The requirement is only about the beginning. (Key point: Final state loops)

3. What does q0 do on a?
   A. Goes to q1
   B. Stays in q0
   C. Goes to q3
   D. Goes to the dead state d, because the string must start with b
   Answer: D. The first symbol must be b. (Key point: Start state)

4. What happens for bab?
   A. q0→q1→q2→d, rejected
   B. It is accepted in q3
   C. It ends in q1
   D. It ends in q2 and is accepted
   Answer: A. After ba the next symbol must be a, but b sends it to d. (Key point: Trace of bab)

## Related in Discrete Structure

- [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
- [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×
- [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×
- [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
- [Construct FSA accepting reverse language](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-reverse-language-construction) — Discrete Structure, chapter 2

## Related in other subjects

- [DFA starts or ends with 01](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Adfa-starts-or-ends-01) — Theory of Computation, chapter 2