5.12. Irodalmi megjegyzések

A reguláris kifejezéseket [Kleene 1956]-ban vezette be és bizonyította ekvivalenciájukat a véges elfogadó automatákkal. A reguláris műveletekre való zártsági tulajdonságok bizonyítása ugyancsak itt jelent meg. A pumpáló lemma a [Bar-Hillel et al. 1961]-ben közölt eredmény speciális esete. A szóprobléma megoldása megtalálható [Moore 1956]-ban. A minimális automata előállítására az első algoritmus [Huffman 1954]-ben jelent meg. Habár a reguláris nyelvek elmélete és alkalmazása (pl. Unix operációs rendszereknél) is nagy múltra tekint vissza, a témakör ma is aktív kutatási terület. A reguláris kifejezések unió-normálformája [Nagy 2004] munkában került bevezetésre, néhány ezzel kapcsolatos eredmény [Nagy 2010d]-ben is található; [Afonin, Golomazov 2009]-ben bizonyították, hogy a reguláris nyelvek unióbonyolultságának meghatározása, mint feladat megoldható. Az uniómentes nyelvek és speciális véges automaták kapcsolatát a [Nagy 2006a] cikk tárgyalja.