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.
Read more about this topic: Regular Language
Main Site Subjects
Related Subjects
Related Phrases
Related Words