Editing Regular language (section)

{{Short description|Formal language that can be expressed using a regular expression}}
{{For|natural language that is regulated|List of language regulators}}
{{Redirect|Kleene's theorem|his theorems for recursive functions|Kleene's recursion theorem}}

In [[theoretical computer science]] and [[formal language theory]], a '''regular language''' (also called a '''rational language''')<ref name="Mitkov2003"/><ref name="Lawson2003"/> is a [[formal language]] that can be defined by a [[regular expression]], in the strict sense in theoretical computer science (as opposed to many modern regular expression engines, which are [[Regular expression#Patterns for non-regular languages|augmented with features]] that allow the recognition of non-regular languages).

Alternatively, a regular language can be defined as a language recognised by a [[finite automaton]]. The equivalence of regular expressions and finite automata is known as '''Kleene's theorem'''<ref name="RozenbergSalomaa1997">{{cite book|editor1=Grzegorz Rozenberg |editor2=Arto Salomaa |title=Handbook of Formal Languages: Volume 1. Word, Language, Grammar|chapter-url=https://books.google.com/books?id=yQ59ojndUt4C&pg=PA41|year=1997|publisher=Springer|isbn=978-3-540-60420-4|page=41|author=Sheng Yu|chapter=Regular languages}}</ref> (after American mathematician [[Stephen Cole Kleene]]). In the [[Chomsky hierarchy]], regular languages are the languages generated by [[regular grammar|Type-3 grammars]].