Editing Regular language (section)

== Closure properties ==
The regular languages are [[closure (mathematics)|closed]] under various operations, that is, if the languages ''K'' and ''L'' are regular, so is the result of the following operations:
* the [[set-theoretic operations|set-theoretic Boolean operations]]: [[Union (set theory)|union]] {{math|''K'' ∪ ''L''}}, [[intersection (set theory)|intersection]] {{math|''K'' ∩ ''L''}}, and [[complement (set theory)|complement]] {{overline|''L''}}, hence also [[relative complement]] {{math|''K'' &minus; ''L''}}.<ref name=Sal28>Salomaa (1981) p.28</ref>
* the regular operations: {{math|''K'' ∪ ''L''}}, [[concatenation]] {{tmath|K \circ L}}, and [[Kleene star]] {{math|''L''<sup>*</sup>}}.<ref name=Sal27>Salomaa (1981) p.27</ref>
* the [[abstract family of languages|trio]] operations: [[string homomorphism]], inverse string homomorphism, and intersection with regular languages. As a consequence they are closed under arbitrary [[finite state transducer|finite state transductions]], like [[right quotient|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''.<ref>{{cite conference
 | last1 = Fellows | first1 = Michael R. | author1-link = Michael Fellows
 | last2 = Langston | first2 = Michael A. | author2-link = Michael Langston
 | editor1-last = Myers | editor1-first = J. Paul Jr.
 | editor2-last = O'Donnell | editor2-first = Michael J.
 | contribution = Constructivity issues in graph algorithms
 | pages = 150–158
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Constructivity in Computer Science, Summer Symposium, San Antonio, Texas, USA, June 19-22, Proceedings
 | volume = 613
 | year = 1991
 | doi = 10.1007/BFB0021088 | isbn = 978-3-540-55631-2
}}</ref>
* the reverse (or mirror image) ''L''<sup>R</sup>.<ref>Hopcroft, Ullman (1979), Chapter 3, Exercise 3.4g, p. 72</ref> Given a nondeterministic finite automaton to recognize ''L'', an automaton for ''L''<sup>R</sup> 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.