Editing Regular language (section)

== Location in the Chomsky hierarchy <span class="anchor" id="Subclasses"></span> ==
[[Image:Chomsky-hierarchy.svg|thumb|250px|Regular language in classes of Chomsky hierarchy]]
To locate the regular languages in the [[Chomsky hierarchy]], one notices that every regular language is [[Context free language|context-free]]. The converse is not true: for example, the language consisting of all strings having the same number of ''a''s as ''b''s is context-free but not regular. To prove that a language is not regular, one often uses the [[Myhill–Nerode theorem]] and the [[Pumping lemma for regular languages|pumping lemma]]. Other approaches include using the [[Regular language#Closure properties|closure properties]] of regular languages<ref>{{cite web|title=How to prove that a language is not regular?|url=https://cs.stackexchange.com/q/1031|access-date=10 April 2018|website=cs.stackexchange.com}}</ref> or quantifying [[Kolmogorov complexity]].<ref>{{Cite book|last=Hromkovič|first=Juraj|url=https://www.worldcat.org/oclc/53007120|title=Theoretical computer science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography|date=2004|publisher=Springer|isbn=3-540-14015-8|pages=76–77|oclc=53007120}}</ref>

Important subclasses of regular languages include:
* Finite languages, those containing only a finite number of words.<ref>A finite language should not be confused with a (usually infinite) language generated by a finite automaton.</ref> These are regular languages, as one can create a [[regular expression]] that is the [[Union (set theory)|union]] of every word in the language.
* [[Star-free language]]s, 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 [[Complement (set theory)|complementation]] but not the [[Kleene star]]: this class includes all finite languages.<ref>{{cite book|editor1=Jörg Flum |editor2=Erich Grädel |editor3=Thomas Wilke |title=Logic and automata: history and perspectives|year=2008|publisher=Amsterdam University Press|isbn=978-90-5356-576-6|chapter-url=http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/DG-WT08.pdf|chapter=First-order definable languages|author1=Volker Diekert |author2=Paul Gastin }}</ref>