DFA for {00}*{11}* language

Reading of the question. The scan is unclear; we take the language L = {00}{11} = (00)(11), i.e. an even number of 0's followed by an even number of 1's (the blocks are 00 and 11). The method is the same for similar expressions.

Idea. Phase 1 reads pairs of 0's; phase 2 reads pairs of 1's; after any 1 is read, a 0 is not allowed.

States:

• q0: even number of 0's read, no 1 yet (start, final)
• q1: odd number of 0's read
• q3: in the 1-phase with an odd number of 1's read
• q2: in the 1-phase with an even number (≥ 2) of 1's read (final)
• d: dead state

M = ({q0, q1, q2, q3, d}, {0,1}, δ, q0, {q0, q2})

 Phase 1 (pairs of 0):   ((q0)) <--0--> (q1)    q1 --1--> d
 Phase 2 (pairs of 1):   q0 --1--> (q3) <--1--> ((q2))
                         q3, q2 --0--> d
 d loops on 0,1.   Start: q0.   Finals: q0, q2.

Edges: q0 –0→ q1, q1 –0→ q0, q0 –1→ q3, q3 –1→ q2, q2 –1→ q3. All other moves go to d (e.g. q1 –1→ d, q2 –0→ d, q3 –0→ d).

Test

• "0011": q0 → q1 → q0 → q3 → q2, final. Accepted.
• "00": q0 → q1 → q0 final, accepted. ε is accepted too.
• "011": q0 → q1 → d. Rejected (odd 0's).
• "1100": q0 → q3 → q2 → d → d. Rejected (0 after 1).