Skip to main content

Illustration DFA - Length difference divisible by 4 with remainder 3

<span>DFA - Length difference divisible by 4 with remainder 3</span>
DFA - Length difference modulo 4 is equal to 3
Download

Share โ€” copy and redistribute the material in any medium or format

Adapt โ€” remix, transform, and build upon the material for any purpose, even commercially.

Sharing and adapting of the illustration is allowed with indication of the link to the illustration.

Sketch of a deterministic finite automaton (DEA) for the following regular language (type 3):$$ L ~=~ \{ w \in \{a,b\}^* ~:~ (|w|_a - |w|_b) ~\text{mod}~ 4 = 3 \} $$

This is an infinite language with, for example, the following words \(w\):\[ L ~=~ \{b, aaa, abb, bab, bba,~... \}\]

This automaton accepts all words \(w\) where the length difference \( |w|_a - |w|_b\) of the \(a\) and \(b\) characters is divisible by four with remainder three.