What do the two states of the odd-b automaton remember?

The parity (even or odd) of the number of b's read so far

Whether the string started with b

Which transitions does the machine use?

Reading b switches between E and O; reading a stays in the same state

Reading a switches state; b stays

Both a and b stay in the same state

Which state is final, and why?

O, because it means an odd number of b's

E, because it is the start state

Neither; the machine uses a dead state

What happens for the input aabbb?

It ends in O and is accepted (3 b's)

Asked 4/9
2071 Bhadra · 6 marks

Design FSA accepting odd number of b's

Short answer

The DFA has states E (even, start) and O (odd, final). On a, stay in current state; on b, switch state. It accepts exactly strings with an odd number of b's.

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

Idea

Track the parity of the number of b's read. State E: even number of b's (start). State O: odd number of b's (final). Reading b switches state; reading a keeps it.

Formal definition

M = (Q, Σ, δ, q₀, F) where Q = {E, O}, Σ = {a, b}, q₀ = E, F = {O}, and δ is:

Transition table

State	a	b
→ E	E	O
*O	O	E

Transition diagram

        a                       a
       ┌─┐                     ┌─┐
       ↓ │                     ↓ │
 ──→ ( E ) ────────b─────────→ (( O ))
         ↑                         │
         └───────────b─────────────┘

Trace

"abb": E –a→ E –b→ O –b→ E. Rejected (2 b's).
"bab": E –b→ O –a→ O –b→ E. Rejected.
"aabbb": E –a→ E –a→ E –b→ O –b→ E –b→ O. Accepted (3 b's).

The language is L = {w ∈ {a, b}* : number of b's is odd} = ab a(b ab a)*. I verified the machine against the b-count for all strings up to length 8.

✓ Answer checked by Claude Opus 5.5 (high effort)

Design FSA accepting even number of a's · Discrete Structure, chapter 2 · asked 4×
Define FSM; design FSA with two consecutive a's · Discrete Structure, chapter 2 · asked 4×
Design FSA for strings beginning with baa · Discrete Structure, chapter 2
Design NFA for strings ending with aba · Discrete Structure, chapter 2
Regular expression and FSA: at least three b's · Discrete Structure, chapter 2
Construct FSA accepting reverse language · Discrete Structure, chapter 2

All Discrete Structure chapter 2 questions →