Skip to main content

Illustration DFA - for every 0 there must be a 1 somewhere behind

DFA - for every 0 there must be a 1 somewhere behind
Get illustration

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 (DFA) for the following regular language (type 3):$$L ~=~ \{ w \in \{0,1\}^* ~:~ \text{ for every 0 there must be a 1 somewhere behind (multiple 0s may share the same 1)} \} $$

This is an infinite language, with, for example, the following words:$$ L ~=~ \{ \varepsilon, 1, 01, 101, 10001, ~... \} $$