Editing Regular language (section)

== Generalizations ==
The notion of a regular language has been generalized to infinite words (see [[ω-automaton|ω-automata]]) and to trees (see [[tree automaton]]).

[[Rational set]] generalizes the notion (of regular/rational language) to monoids that are not necessarily [[free monoid|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 [[Samuel Eilenberg|Eilenberg]]'s monograph<ref name="Eilenberg1974">{{cite book|author=Samuel Eilenberg|title=Automata, languages, and machines|publisher=Academic Press}} in two volumes "A" (1974, {{isbn|9780080873749}}) and "B" (1976, {{isbn|9780080873756}}), the latter with two chapters by Bret Tilson.</ref> 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.”<ref>{{cite book | last=Straubing | first=Howard | title=Finite automata, formal logic, and circuit complexity | url=https://archive.org/details/finiteautomatafo0000stra | url-access=registration | series=Progress in Theoretical Computer Science | location=Basel | publisher=Birkhäuser | year=1994 | isbn=3-7643-3719-2 | zbl=0816.68086 | page= [https://archive.org/details/finiteautomatafo0000stra/page/8 8] }}</ref>

[[Rational series]] is another generalization, this time in the context of a [[formal power series over a semiring]]. This approach gives rise to [[weighted rational expression]]s and [[weighted automata]]. In this algebraic context, the regular languages (corresponding to [[Boolean semiring|Boolean]]-weighted rational expressions) are usually called ''rational languages''.<ref>Berstel & Reutenauer (2011) p.47</ref><ref>{{cite book | last=Sakarovitch | first=Jacques | title=Elements of automata theory | others=Translated from the French by Reuben Thomas | location=Cambridge | publisher=[[Cambridge University Press]] | year=2009 | isbn=978-0-521-84425-3 | zbl=1188.68177 | page = 86 }}</ref> Also in this context, Kleene's theorem finds a generalization called the [[Kleene–Schützenberger theorem]].