Skip to main content

Illustration DFA - xw words, where w contains substring x²

<span>DFA - xw words, where w contains substring x²</span>
DFA - xw words, where w contains substring x squared
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 (DFA) for the following regular language (type 3):$$ L ~=~ \{ x\,w ~:~ x\in \{a,b\}, ~~ w\in\{a,b\}^*, ~~ w~\text{contains}~x^2 \} $$

This is an infinite language with, for example, the following words \(w\):$$ L ~=~ \{aaa, bbb, abaaa, babbb,~.... \} $$

This automaton accepts all words \(w\) where the first letter is an \(a\) or \(b\), followed by the substring \(w\) containing \(aa\) (if first letter is an \(a\)) or \(bb\) (if first letter is an \(b\)).