Regular languages can be studied not just for finite words, but also for finite trees, infinite words and infinite trees. Almost all of the theory of regular languages, such as closure under boolean operations, works also for these extensions, but the constructions are significantly more challenging and mathematically interesting. For instance, automata for infinite words can be determinised under a suitable choice of acceptance condition, but, the proof requires an intricate combinatorial construction.
展开▼
