Regular Language - Equivalence To Other Formalisms

Equivalence To Other Formalisms

A regular language satisfies the following equivalent properties:

• it can be accepted by a (nondeterministic) finite automaton, but also by the restricted deterministic finite automaton, or the more general alternating finite automaton
• it can be generated by a regular grammar
• it can be generated by a prefix grammar
• it can be accepted by a read-only Turing machine
• it can be defined in monadic second-order logic (Büchi-Elgot-Trakhtenbrot theorem)
• it is recognized by some finite monoid, meaning it is the preimage of a subset of a finite monoid under a homomorphism from the free monoid on its alphabet (see Myhill–Nerode theorem).

The above properties are sometimes used as alternative definition of regular languages.