Editing Regular language (section)

== Complexity results ==

In [[computational complexity theory]], the [[complexity class]] of all regular languages is sometimes referred to as '''REGULAR''' or '''REG''' and equals [[DSPACE]](O(1)), the [[decision problem]]s that can be solved in constant space (the space used is independent of the input size). '''REGULAR''' ≠ [[AC0|'''AC'''<sup>0</sup>]], since it (trivially) contains the parity problem of determining whether the number of 1 bits in the input is even or odd and this problem is not in '''AC'''<sup>0</sup>.<ref>{{cite journal | last1 = Furst | first1 = Merrick | last2 = Saxe | first2 = James B. | author2-link = James B. Saxe | last3 = Sipser | first3 = Michael | author3-link = Michael Sipser | doi = 10.1007/BF01744431 | issue = 1 | journal = Mathematical Systems Theory | mr = 738749 | pages = 13–27 | title = Parity, circuits, and the polynomial-time hierarchy | volume = 17 | year = 1984| s2cid = 14677270 }}</ref> On the other hand, '''REGULAR''' does not contain '''AC'''<sup>0</sup>, because the nonregular language of [[palindrome]]s, or the nonregular language <math>\{0^n 1^n : n \in \mathbb N\}</math> can both be recognized in '''AC'''<sup>0</sup>.<ref>{{cite book|last1=Cook|first1=Stephen|last2=Nguyen|first2=Phuong|title=Logical foundations of proof complexity|year=2010|publisher=Association for Symbolic Logic|location=Ithaca, NY|isbn=978-0-521-51729-4|pages=75|edition=1. publ.}}</ref>

If a language is ''not'' regular, it requires a machine with at least {{nowrap|[[Big O notation|Ω]](log log ''n'')}} space to recognize (where ''n'' is the input size).<ref>J. Hartmanis, P. L. Lewis II, and R. E. Stearns. Hierarchies of memory-limited computations. ''Proceedings of the 6th Annual IEEE Symposium on Switching Circuit Theory and Logic Design'', pp. 179–190. 1965.</ref> In other words, {{nowrap|DSPACE([[Big O notation|o]](log log ''n''))}} equals the class of regular languages. In practice, most nonregular problems are solved by machines taking at least [[logarithmic space]].