Regular language
In
Alternatively, a regular language can be defined as a language recognised by a
Formal definition
The collection of regular languages over an alphabet Σ is defined recursively as follows:
- The empty language Ø is a regular language.
- For each a ∈ Σ (a belongs to Σ), the singleton language {a } is a regular language.
- If A is a regular language, A* (Kleene star) is a regular language. Due to this, the empty string language {ε} is also regular.
- If A and B are regular languages, then A ∪ B (union) and A • B (concatenation) are regular languages.
- No other languages over Σ are regular.
See regular expression for syntax and semantics of regular expressions.
Examples
All finite languages are regular; in particular the empty string language {ε} = Ø* is regular. Other typical examples include the language consisting of all strings over the alphabet {a, b} which contain an even number of a's, or the language consisting of all strings of the form: several a's followed by several b's.
A simple example of a language that is not regular is the set of strings {anbn | n ≥ 0}.[4] Intuitively, it cannot be recognized with a finite automaton, since a finite automaton has finite memory and it cannot remember the exact number of a's. Techniques to prove this fact rigorously are given below.
Equivalent formalisms
A regular language satisfies the following equivalent properties:
- it is the language of a regular expression (by the above definition)
- it is the language accepted by a nondeterministic finite automaton (NFA)[note 1][note 2]
- it is the language accepted by a deterministic finite automaton (DFA)[note 3][note 4]
- it can be generated by a regular grammar[note 5][note 6]
- it is the language accepted by an alternating finite automaton
- it is the language accepted by a two-way finite automaton
- it can be generated by a prefix grammar
- it can be accepted by a read-only Turing machine
- it can be defined in Büchi–Elgot–Trakhtenbrot theorem)[5]
- it is monoid homomorphism f: Σ* → M from the free monoid on its alphabet[note 7]
- the number of equivalence classes of its syntactic congruence is finite.[note 8][note 9] (This number equals the number of states of the minimal deterministic finite automatonaccepting L.)
Properties 10. and 11. are purely algebraic approaches to define regular languages; a similar set of statements can be formulated for a monoid M ⊆ Σ*. In this case, equivalence over M leads to the concept of a recognizable language.
Some authors use one of the above properties different from "1." as an alternative definition of regular languages.
Some of the equivalences above, particularly those among the first four formalisms, are called Kleene's theorem in textbooks. Precisely which one (or which subset) is called such varies between authors. One textbook calls the equivalence of regular expressions and NFAs ("1." and "2." above) "Kleene's theorem".[6] Another textbook calls the equivalence of regular expressions and DFAs ("1." and "3." above) "Kleene's theorem".[7] Two other textbooks first prove the expressive equivalence of NFAs and DFAs ("2." and "3.") and then state "Kleene's theorem" as the equivalence between regular expressions and finite automata (the latter said to describe "recognizable languages").[2][8] A linguistically oriented text first equates regular grammars ("4." above) with DFAs and NFAs, calls the languages generated by (any of) these "regular", after which it introduces regular expressions which it terms to describe "rational languages", and finally states "Kleene's theorem" as the coincidence of regular and rational languages.[9] Other authors simply define "rational expression" and "regular expressions" as synonymous and do the same with "rational languages" and "regular languages".[1][2]
Apparently, the term "regular" originates from a 1951 technical report where Kleene introduced "regular events" and explicitly welcomed "any suggestions as to a more descriptive term".[10] Noam Chomsky, in his 1959 seminal article, used the term "regular" in a different meaning at first (referring to what is called "Chomsky normal form" today),[11] but noticed that his "finite state languages" were equivalent to Kleene's "regular events".[12]
Closure properties
The regular languages are closed under various operations, that is, if the languages K and L are regular, so is the result of the following operations:
- the relative complement K − L.[13]
- the regular operations: K ∪ L, concatenation , and Kleene star L*.[14]
- the quotient K / L with a regular language. Even more, regular languages are closed under quotients with arbitrary languages: If L is regular then L / K is regular for any K.[15]
- the reverse (or mirror image) LR.[16] Given a nondeterministic finite automaton to recognize L, an automaton for LR can be obtained by reversing all transitions and interchanging starting and finishing states. This may result in multiple starting states; ε-transitions can be used to join them.
Decidability properties
Given two deterministic finite automata A and B, it is decidable whether they accept the same language.[17] As a consequence, using the above closure properties, the following problems are also decidable for arbitrarily given deterministic finite automata A and B, with accepted languages LA and LB, respectively:
- Containment: is LA ⊆ LB ?[note 10]
- Disjointness: is LA ∩ LB = {} ?
- Emptiness: is LA = {} ?
- Universality: is LA = Σ* ?
- Membership: given a ∈ Σ*, is a ∈ LB ?
For regular expressions, the universality problem is
For a fixed finite alphabet, the theory of the set of all languages — together with strings, membership of a string in a language, and for each character, a function to append the character to a string (and no other operations) — is decidable, and its minimal elementary substructure consists precisely of regular languages. For a binary alphabet, the theory is called S2S.[24]
Complexity results
In computational complexity theory, the complexity class of all regular languages is sometimes referred to as REGULAR or REG and equals DSPACE(O(1)), the decision problems that can be solved in constant space (the space used is independent of the input size). REGULAR ≠ AC0, since it (trivially) contains the parity problem of determining whether the number of 1 bits in the input is even or odd and this problem is not in AC0.[25] On the other hand, REGULAR does not contain AC0, because the nonregular language of palindromes, or the nonregular language can both be recognized in AC0.[26]
If a language is not regular, it requires a machine with at least
Location in the Chomsky hierarchy
To locate the regular languages in the
Important subclasses of regular languages include
- Finite languages, those containing only a finite number of words.[30] These are regular languages, as one can create a regular expression that is the union of every word in the language.
- Star-free languages, those that can be described by a regular expression constructed from the empty symbol, letters, concatenation and all boolean operators (see algebra of sets) including complementation but not the Kleene star: this class includes all finite languages.[31]
The number of words in a regular language
Let denote the number of words of length in . The
The generating function of a language L is a rational function if L is regular.[32] Hence for every regular language the sequence is constant-recursive; that is, there exist an integer constant , complex constants and complex polynomials such that for every the number of words of length in is .[33][34][35][36]
Thus, non-regularity of certain languages can be proved by counting the words of a given length in . Consider, for example, the Dyck language of strings of balanced parentheses. The number of words of length in the Dyck language is equal to the Catalan number , which is not of the form , witnessing the non-regularity of the Dyck language. Care must be taken since some of the eigenvalues could have the same magnitude. For example, the number of words of length in the language of all even binary words is not of the form , but the number of words of even or odd length are of this form; the corresponding eigenvalues are . In general, for every regular language there exists a constant such that for all , the number of words of length is asymptotically .[37]
The zeta function of a language L is[32]
The zeta function of a regular language is not in general rational, but that of an arbitrary cyclic language is.[38][39]
Generalizations
The notion of a regular language has been generalized to infinite words (see ω-automata) and to trees (see tree automaton).
Rational set generalizes the notion (of regular/rational language) to monoids that are not necessarily free. Likewise, the notion of a recognizable language (by a finite automaton) has namesake as recognizable set over a monoid that is not necessarily free. Howard Straubing notes in relation to these facts that “The term "regular language" is a bit unfortunate. Papers influenced by Eilenberg's monograph[40] often use either the term "recognizable language", which refers to the behavior of automata, or "rational language", which refers to important analogies between regular expressions and rational power series. (In fact, Eilenberg defines rational and recognizable subsets of arbitrary monoids; the two notions do not, in general, coincide.) This terminology, while better motivated, never really caught on, and "regular language" is used almost universally.”[41]
Learning from examples
Notes
- Thompson's construction algorithm
- Arden's lemma
- ^ 2. ⇒ 3. by the powerset construction
- ^ 3. ⇒ 2. since the former definition is stronger than the latter
- ^ 2. ⇒ 4. see Hopcroft, Ullman (1979), Theorem 9.2, p.219
- ^ 4. ⇒ 2. see Hopcroft, Ullman (1979), Theorem 9.1, p.218
- ^ 3. ⇔ 10. by the Myhill–Nerode theorem
- ^ u~v is defined as: uw∈L if and only if vw∈L for all w∈Σ*
- Zbl 0489.68046.
- NP-hard in general; see File:RegSubsetNP.pdffor an illustration of the proof idea.
References
- Zbl 1250.68007.
- Zbl 0317.94045.
- Zbl 0487.68064.
- Zbl 1169.68300. Chapter 1: Regular Languages, pp. 31–90. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp. 152–155.
- Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics: Symbolic Combinatorics. Online book, 2002.
- John E. Hopcroft; Jeffrey D. Ullman (1979). ISBN 0-201-02988-X.
- Alfred V. Aho and John E. Hopcroft and Jeffrey D. Ullman (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. ISBN 9780201000290.
- ^ ISBN 978-0-19-927634-9.
- ^ ISBN 978-1-58488-255-8.
- ISBN 978-3-540-60420-4.
- ^ Eilenberg (1974), p. 16 (Example II, 2.8) and p. 25 (Example II, 5.2).
- ^ M. Weyer: Chapter 12 - Decidability of S1S and S2S, p. 219, Theorem 12.26. In: Erich Grädel, Wolfgang Thomas, Thomas Wilke (Eds.): Automata, Logics, and Infinite Games: A Guide to Current Research. Lecture Notes in Computer Science 2500, Springer 2002.
- ISBN 978-0-321-57351-3.
- ISBN 978-0-521-82332-6.
- ^ Kenneth Rosen (2011). Discrete Mathematics and Its Applications 7th edition. McGraw-Hill Science. pp. 873–880.
- ISBN 978-9971-5-0566-0.
- ^ Stephen Cole Kleene (Dec 1951). Representation of Events in Nerve Nets and Finite Automate (PDF) (Research Memorandum). U.S. Air Force / RAND Corporation. Here: p.46
- . Here: Definition 8, p.149
- ^ Chomsky 1959, Footnote 10, p.150
- ^ Salomaa (1981) p.28
- ^ Salomaa (1981) p.27
- .
- ^ Hopcroft, Ullman (1979), Chapter 3, Exercise 3.4g, p. 72
- ^ Hopcroft, Ullman (1979), Theorem 3.8, p.64; see also Theorem 3.10, p.67
- ^ Aho, Hopcroft, Ullman (1974), Exercise 10.14, p.401
- ^ Aho, Hopcroft, Ullman (1974), Theorem 10.14, p399
- ^ Hopcroft, Ullman (1979), Theorem 13.15, p.351
- ^ A.R. Meyer & L.J. Stockmeyer (Oct 1972). The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space (PDF). 13th Annual IEEE Symp. on Switching and Automata Theory. pp. 125–129.
- ^ L. J. Stockmeyer; A. R. Meyer (1973). "Word Problems Requiring Exponential Time". Proc. 5th ann. symp. on Theory of computing (STOC) (PDF). ACM. pp. 1–9.
- ^ Hopcroft, Ullman (1979), Corollary p.353
- ISBN 978-3-540-00388-5.
- S2CID 14677270.
- ISBN 978-0-521-51729-4.
- ^ J. Hartmanis, P. L. Lewis II, and R. E. Stearns. Hierarchies of memory-limited computations. Proceedings of the 6th Annual IEEE Symposium on Switching Circuit Theory and Logic Design, pp. 179–190. 1965.
- ^ "How to prove that a language is not regular?". cs.stackexchange.com. Retrieved 10 April 2018.
- OCLC 53007120.
- ^ A finite language shouldn't be confused with a (usually infinite) language generated by a finite automaton.
- ISBN 978-90-5356-576-6.
- ^ Zbl 0675.68034.
- ^ Flajolet & Sedgweick, section V.3.1, equation (13).
- ^ "Number of words in the regular language $(00)^*$". cs.stackexchange.com. Retrieved 10 April 2018.
- ^ "Proof of theorem for arbitrary DFAs".
- ^ "Number of words of a given length in a regular language". cs.stackexchange.com. Retrieved 10 April 2018.
- ^ Flajolet & Sedgewick (2002) Theorem V.3
- Zbl 0797.68092.
- ^ Berstel & Reutenauer (2011) p.222
- ISBN 9780080873756), the latter with two chapters by Bret Tilson.
- Zbl 0816.68086.
- ^ Berstel & Reutenauer (2011) p.47
- Zbl 1188.68177.
Further reading
- Kleene, S.C.: Representation of events in nerve nets and finite automata. In: Shannon, C.E., McCarthy, J. (eds.) Automata Studies, pp. 3–41. Princeton University Press, Princeton (1956); it is a slightly modified version of his 1951 RAND Corporation report of the same title, RM704.
- Sakarovitch, J (1987). "Kleene's theorem revisited". Trends, Techniques, and Problems in Theoretical Computer Science. Lecture Notes in Computer Science. Vol. 1987. pp. 39–50. ISBN 978-3-540-18535-2.
External links
- Complexity Zoo: Class REG