Κανονική γλώσσα: Διαφορά μεταξύ των αναθεωρήσεων

Στη [[θεωρία πολυπλοκότητας]], η κλάση πολυπλοκότητας όλων των κανονικών γλωσσών αναφέρεται μερικές φορές ως REGULAR ή REG και ισοδυναμεί με [[DSPACE]](O(1)), δηλαδή τα [[Πρόβλημα απόφασης|προβλήματα απόφασης]] που μπορούν να επιλυθούν σε σταθερό χώρο (ο χώρος που χρησιμοποιείται είναι ανεξάρτητος του μεγέθους της εισόδου). Ισχύει ότι '''REGULAR''' ≠ '''[[:en:AC0|'''AC]]'''^[[AC0|0]]]], αφού εμπεριέχει το πρόβλημα της ισοτιμίας κατά το οποίο πρέπει να αποφανθούμε αν το πλήθος των 1 ψηφίων στην είσοδο είναι άρτιο ή περιττό, και αυτό το πρόβλημα δεν ανήκει στο '''AC'''⁰.<ref>{{Πρότυπο:Cite journal|url=|title=Parity, circuits, and the polynomial-time hierarchy|last2=Saxe|first2=J. B.|journal=Math. Systems Theory|issue=|doi=10.1007/bf01744431|year=1984|volume=17|pages=13–27|last3=Sipser|first3=M.|last1=Furst|first1=M.}}</ref> Από την άλλη πλευρά, η '''REGULAR''' δεν περιλαμβάνει την '''AC'''⁰, διότι η μη κανονική γλώσσα των [[Καρκινική γραφή|παλίνδρομων]] ή η μη κανονική γλώσσα <math>\{0^n 1^n : n \in \mathbb N\}</math> μπορούν αμφότερες να αναγνωριστούν στην '''AC'''⁰.<ref>{{Πρότυπο:Cite book|title=Logical foundations of proof complexity|last2=Nguyen|first2=Phuong|publisher=Association for Symbolic Logic|year=2010|isbn=0-521-51729-X|edition=1. publ.|location=Ithaca, NY|pages=75|last1=Cook|first1=Stephen}}</ref>