Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Regular language

From Wikipedia, the free encyclopedia
Formal language that can be expressed using a regular expression
For natural language that is regulated, seeList of language regulators.
"Kleene's theorem" redirects here. For his theorems for recursive functions, seeKleene's recursion theorem.

Intheoretical computer science andformal language theory, aregular language (also called arational language)[1][2] is aformal language that can be defined by aregular expression, in the strict sense in theoretical computer science (as opposed to many modern regular expression engines, which areaugmented with features that allow the recognition of non-regular languages).

Alternatively, a regular language can be defined as a language recognised by afinite automaton. The equivalence of regular expressions and finite automata is known asKleene's theorem[3] (after American mathematicianStephen Cole Kleene). In theChomsky hierarchy, regular languages are the languages generated byType-3 grammars.

Formal definition

[edit]

The collection of regular languages over analphabet Σ is defined recursively as follows:

  • The empty language ∅ is a regular language.
  • For eacha ∈ Σ (a belongs to Σ), thesingleton language {a} is a regular language.
  • IfA is a regular language,A* (Kleene star) is a regular language. Due to this, the empty string language {ε} is also regular.
  • IfA andB are regular languages, thenA ∪B (union) andA •B (concatenation) are regular languages.
  • No other languages over Σ are regular.

SeeRegular expression § Formal language theory for syntax and semantics of regular expressions.

Examples

[edit]

All finite languages are regular; in particular theempty string language{ε} = ∅* is regular. Other typical examples include the language consisting of all strings over the alphabet {a,b} which contain an even number ofas, or the language consisting of all strings of the form: severalas followed by severalbs.

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 givenbelow.

Equivalent formalisms

[edit]

A regular language satisfies the following equivalent properties:

  1. it is the language of a regular expression (by the above definition)
  2. it is the language accepted by anondeterministic finite automaton (NFA)[note 1][note 2]
  3. it is the language accepted by adeterministic finite automaton (DFA)[note 3][note 4]
  4. it can be generated by aregular grammar[note 5][note 6]
  5. it is the language accepted by analternating finite automaton
  6. it is the language accepted by atwo-way finite automaton
  7. it can be generated by aprefix grammar
  8. it can be accepted by a read-onlyTuring machine
  9. it can be defined inmonadic second-order logic (Büchi–Elgot–Trakhtenbrot theorem)[5]
  10. it isrecognized by some finitesyntactic monoidM, meaning it is thepreimage {w ∈ Σ* |f(w) ∈S} of a subsetS of a finitemonoidM under amonoid homomorphismf : Σ* →M from thefree monoid on its alphabet[note 7]
  11. the number of equivalence classes of itssyntactic congruence is finite.[note 8][note 9] (This number equals the number of states of theminimal deterministic finite automaton acceptingL.)

Properties 10. and 11. are purely algebraic approaches to define regular languages; a similar set of statements can be formulated for a monoidM ⊆ Σ*. In this case, equivalence overM 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 calledKleene'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 simplydefine "rational expression" and "regular expressions" as synonymous and do the same with "rational languages" and "regular languages".[1][2]

Apparently, the termregular originates from a 1951 technical report where Kleene introducedregular events and explicitly welcomed "any suggestions as to a more descriptive term".[10]Noam Chomsky, in his 1959 seminal article, used the termregular in a different meaning at first (referring to what is calledChomsky normal form today),[11] but noticed that hisfinite state languages were equivalent to Kleene'sregular events.[12]

Closure properties

[edit]

The regular languages areclosed under various operations, that is, if the languagesK andL are regular, so is the result of the following operations:

Decidability properties

[edit]

Given two deterministic finite automataA andB, it is decidable whether they accept the same language.[17]As a consequence, using theabove closure properties, the following problems are also decidable for arbitrarily given deterministic finite automataA andB, with accepted languagesLA andLB, respectively:

  • Containment: isLA ⊆LB ?[note 10]
  • Disjointness: isLA ∩LB = {} ?
  • Emptiness: isLA = {} ?
  • Universality: isLA = Σ* ?
  • Membership: givena ∈ Σ*, isa ∈LB ?

For regular expressions, the universality problem isNP-complete already for a singleton alphabet.[18]For larger alphabets, that problem isPSPACE-complete.[19] If regular expressions are extended to allow also asquaring operator, with "A2" denoting the same as "AA", still just regular languages can be described, but the universality problem has an exponential space lower bound,[20][21][22] and is in fact complete for exponential space with respect to polynomial-time reduction.[23]

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 minimalelementary substructure consists precisely of regular languages. For a binary alphabet, the theory is calledS2S.[24]

Complexity results

[edit]

Incomputational complexity theory, thecomplexity class of all regular languages is sometimes referred to asREGULAR orREG and equalsDSPACE(O(1)), thedecision 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 inAC0.[25] On the other hand,REGULAR does not containAC0, because the nonregular language ofpalindromes, or the nonregular language{0n1n:n∈N}{\displaystyle \{0^{n}1^{n}:n\in \mathbb {N} \}} can both be recognized inAC0.[26]

If a language isnot regular, it requires a machine with at leastΩ(log logn) space to recognize (wheren is the input size).[27] In other words,DSPACE(o(log logn)) equals the class of regular languages.[27] In practice, most nonregular problems are studied in a setting with at leastlogarithmic space, as this is the amount of space required to store a pointer into the input tape.[28]

Location in the Chomsky hierarchy

[edit]
Regular language in classes of Chomsky hierarchy

To locate the regular languages in theChomsky hierarchy, one notices that every regular language iscontext-free. The converse is not true: for example, the language consisting of all strings having the same number ofas asbs is context-free but not regular. To prove that a language is not regular, one often uses theMyhill–Nerode theorem and thepumping lemma. Other approaches include using theclosure properties of regular languages[29] or quantifyingKolmogorov complexity.[30]

Important subclasses of regular languages include:

  • Finite languages, those containing only a finite number of words.[31] These are regular languages, as one can create aregular expression that is theunion 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 (seealgebra of sets) includingcomplementation but not theKleene star: this class includes all finite languages.[32]

Number of words in a regular language

[edit]

LetsL(n){\displaystyle s_{L}(n)} denote the number of words of lengthn{\displaystyle n} inL{\displaystyle L}. Theordinary generating function forL is theformal power series

SL(z)=∑n≥0sL(n)zn .{\displaystyle S_{L}(z)=\sum _{n\geq 0}s_{L}(n)z^{n}\ .}

The generating function of a languageL is arational function ifL is regular.[33] Hence for every regular languageL{\displaystyle L} the sequencesL(n)n≥0{\displaystyle s_{L}(n)_{n\geq 0}} isconstant-recursive; that is, there exist aninteger constantn0{\displaystyle n_{0}},complex constantsλ1,…,λk{\displaystyle \lambda _{1},\,\ldots ,\,\lambda _{k}} and complexpolynomialsp1(x),…,pk(x){\displaystyle p_{1}(x),\,\ldots ,\,p_{k}(x)} such that for everyn≥n0{\displaystyle n\geq n_{0}} the numbersL(n){\displaystyle s_{L}(n)} of words of lengthn{\displaystyle n} inL{\displaystyle L} issL(n)=p1(n)λ1n+⋯+pk(n)λkn{\displaystyle s_{L}(n)=p_{1}(n)\lambda _{1}^{n}+\dotsb +p_{k}(n)\lambda _{k}^{n}}.[34][35][36][37]

Thus, non-regularity of certain languagesL′{\displaystyle L'} can be proved by counting the words of a given length inL′{\displaystyle L'}. Consider, for example, theDyck language of strings of balanced parentheses. The number of words of length2n{\displaystyle 2n}in the Dyck language is equal to theCatalan numberCn∼4nn3/2π{\displaystyle C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}}, which is not of the formp(n)λn{\displaystyle p(n)\lambda ^{n}},witnessing the non-regularity of the Dyck language. Care must be taken since some of the eigenvaluesλi{\displaystyle \lambda _{i}} could have the same magnitude. For example, the number of words of lengthn{\displaystyle n} in the language of all even binary words is not of the formp(n)λn{\displaystyle p(n)\lambda ^{n}}, but the number of words of even or odd length are of this form; the corresponding eigenvalues are2,−2{\displaystyle 2,-2}. In general, for every regular language there exists a constantd{\displaystyle d} such that for alla{\displaystyle a}, the number of words of lengthdm+a{\displaystyle dm+a} is asymptoticallyCampaλam{\displaystyle C_{a}m^{p_{a}}\lambda _{a}^{m}}.[38]

Thezeta function of a languageL is[33]

ζL(z)=exp⁡(∑n≥0sL(n)znn).{\displaystyle \zeta _{L}(z)=\exp \left({\sum _{n\geq 0}s_{L}(n){\frac {z^{n}}{n}}}\right).}

The zeta function of a regular language is not in general rational, but that of an arbitrarycyclic language is.[39][40]

Generalizations

[edit]

The notion of a regular language has been generalized to infinite words (seeω-automata) and to trees (seetree automaton).

Rational set generalizes the notion (of regular/rational language) to monoids that are not necessarilyfree. Likewise, the notion of a recognizable language (by a finite automaton) has namesake asrecognizable 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 byEilenberg's monograph[41] 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 rationalpower 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.”[42]

Rational series is another generalization, this time in the context of aformal power series over a semiring. This approach gives rise toweighted rational expressions andweighted automata. In this algebraic context, the regular languages (corresponding toBoolean-weighted rational expressions) are usually calledrational languages.[43][44] Also in this context, Kleene's theorem finds a generalization called theKleene–Schützenberger theorem.

Learning from examples

[edit]
Main article:Induction of regular languages

Notes

[edit]
  1. ^1. ⇒ 2. byThompson's construction algorithm
  2. ^2. ⇒ 1. byKleene's algorithm or usingArden's lemma
  3. ^2. ⇒ 3. by thepowerset construction
  4. ^3. ⇒ 2. since theformer definition is stronger than thelatter
  5. ^2. ⇒ 4. see Hopcroft, Ullman (1979), Theorem 9.2, p.219
  6. ^4. ⇒ 2. see Hopcroft, Ullman (1979), Theorem 9.1, p.218
  7. ^3. ⇔ 10. by theMyhill–Nerode theorem
  8. ^u ~v is defined as:uw ∈L if and only ifvw ∈L for allw ∈ Σ*
  9. ^3. ⇔ 11. see the proof in theSyntactic monoid article, and see p. 160 inHolcombe, W.M.L. (1982).Algebraic automata theory. Cambridge Studies in Advanced Mathematics. Vol. 1.Cambridge University Press.ISBN 0-521-60492-3.Zbl 0489.68046.
  10. ^Check ifLA ∩LB =LA. Deciding this property isNP-hard in general; seeFile:RegSubsetNP.pdf for an illustration of the proof idea.

References

[edit]
  1. ^abRuslan Mitkov (2003).The Oxford Handbook of Computational Linguistics. Oxford University Press. p. 754.ISBN 978-0-19-927634-9.
  2. ^abcMark V. Lawson (2003).Finite Automata. CRC Press. pp. 98–103.ISBN 978-1-58488-255-8.
  3. ^Sheng Yu (1997)."Regular languages". In Grzegorz Rozenberg; Arto Salomaa (eds.).Handbook of Formal Languages: Volume 1. Word, Language, Grammar. Springer. p. 41.ISBN 978-3-540-60420-4.
  4. ^Eilenberg (1974), p. 16 (Example II, 2.8) and p. 25 (Example II, 5.2).
  5. ^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.
  6. ^Robert Sedgewick; Kevin Daniel Wayne (2011).Algorithms. Addison-Wesley Professional. p. 794.ISBN 978-0-321-57351-3.
  7. ^Jean-Paul Allouche; Jeffrey Shallit (2003).Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. p. 129.ISBN 978-0-521-82332-6.
  8. ^Kenneth Rosen (2011).Discrete Mathematics and Its Applications 7th edition. McGraw-Hill Science. pp. 873–880.
  9. ^Horst Bunke; Alberto Sanfeliu (January 1990).Syntactic and Structural Pattern Recognition: Theory and Applications. World Scientific. p. 248.ISBN 978-9971-5-0566-0.
  10. ^Stephen Cole Kleene (Dec 1951).Representation of Events in Nerve Nets and Finite Automata(PDF) (Research Memorandum). U.S. Air Force / RAND Corporation. Here: p.46
  11. ^Noam Chomsky (1959)."On Certain Formal Properties of Grammars"(PDF).Information and Control.2 (2):137–167.doi:10.1016/S0019-9958(59)90362-6. Here: Definition 8, p.149
  12. ^Chomsky 1959, Footnote 10, p.150
  13. ^Salomaa (1981) p.28
  14. ^Salomaa (1981) p.27
  15. ^Fellows, Michael R.;Langston, Michael A. (1991). "Constructivity issues in graph algorithms". In Myers, J. Paul Jr.; O'Donnell, Michael J. (eds.).Constructivity in Computer Science, Summer Symposium, San Antonio, Texas, USA, June 19-22, Proceedings. Lecture Notes in Computer Science. Vol. 613. Springer. pp. 150–158.doi:10.1007/BFB0021088.ISBN 978-3-540-55631-2.
  16. ^Hopcroft, Ullman (1979), Chapter 3, Exercise 3.4g, p. 72
  17. ^Hopcroft, Ullman (1979), Theorem 3.8, p.64; see also Theorem 3.10, p.67
  18. ^Aho, Hopcroft, Ullman (1974), Exercise 10.14, p.401
  19. ^Aho, Hopcroft, Ullman (1974), Theorem 10.14, p399
  20. ^Hopcroft, Ullman (1979), Theorem 13.15, p.351
  21. ^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.
  22. ^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.
  23. ^Hopcroft, Ullman (1979), Corollary p.353
  24. ^Weyer, Mark (2002)."Decidability of S1S and S2S".Automata, Logics, and Infinite Games. Lecture Notes in Computer Science. Vol. 2500. Springer. pp. 207–230.doi:10.1007/3-540-36387-4_12.ISBN 978-3-540-00388-5.
  25. ^Furst, Merrick;Saxe, James B.;Sipser, Michael (1984). "Parity, circuits, and the polynomial-time hierarchy".Mathematical Systems Theory.17 (1):13–27.doi:10.1007/BF01744431.MR 0738749.S2CID 14677270.
  26. ^Cook, Stephen; Nguyen, Phuong (2010).Logical foundations of proof complexity (1. publ. ed.). Ithaca, NY: Association for Symbolic Logic. p. 75.ISBN 978-0-521-51729-4.
  27. ^abJ. 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.
  28. ^Sipser (1997) p.349
  29. ^"How to prove that a language is not regular?".cs.stackexchange.com. Retrieved10 April 2018.
  30. ^Hromkovič, Juraj (2004).Theoretical computer science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography. Springer. pp. 76–77.ISBN 3-540-14015-8.OCLC 53007120.
  31. ^A finite language should not be confused with a (usually infinite) language generated by a finite automaton.
  32. ^Volker Diekert; Paul Gastin (2008)."First-order definable languages"(PDF). In Jörg Flum; Erich Grädel; Thomas Wilke (eds.).Logic and automata: history and perspectives. Amsterdam University Press.ISBN 978-90-5356-576-6.
  33. ^abHonkala, Juha (1989)."A necessary condition for the rationality of the zeta function of a regular language".Theor. Comput. Sci.66 (3):341–347.doi:10.1016/0304-3975(89)90159-x.Zbl 0675.68034.
  34. ^Flajolet & Sedgweick, section V.3.1, equation (13).
  35. ^"Number of words in the regular language $(00)^*$".cs.stackexchange.com. Retrieved10 April 2018.
  36. ^"Proof of theorem for arbitrary DFAs".
  37. ^"Number of words of a given length in a regular language".cs.stackexchange.com. Retrieved10 April 2018.
  38. ^Flajolet & Sedgewick (2002) Theorem V.3
  39. ^Berstel, Jean; Reutenauer, Christophe (1990). "Zeta functions of formal languages".Trans. Am. Math. Soc.321 (2):533–546.CiteSeerX 10.1.1.309.3005.doi:10.1090/s0002-9947-1990-0998123-x.Zbl 0797.68092.
  40. ^Berstel & Reutenauer (2011) p.222
  41. ^Samuel Eilenberg.Automata, languages, and machines. Academic Press. in two volumes "A" (1974,ISBN 9780080873749) and "B" (1976,ISBN 9780080873756), the latter with two chapters by Bret Tilson.
  42. ^Straubing, Howard (1994).Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Basel: Birkhäuser. p. 8.ISBN 3-7643-3719-2.Zbl 0816.68086.
  43. ^Berstel & Reutenauer (2011) p.47
  44. ^Sakarovitch, Jacques (2009).Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge:Cambridge University Press. p. 86.ISBN 978-0-521-84425-3.Zbl 1188.68177.

Further reading

[edit]
  • 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 1951RAND 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.doi:10.1007/3540185356_29.ISBN 978-3-540-18535-2.

External links

[edit]
Each category of languages, except those marked by a*, is aproper subset of the category directly above it.Any language in each category is generated by a grammar and by an automaton in the category in the same line.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Regular_language&oldid=1316795257"
Categories:
Hidden categories:
[8]ページ先頭
©2009-2026 Movatter.jp