Revision #280 → #1533 · back to history
addedRegular language (via regular expression)832d6fb1cd43
addedRegular language (via finite automaton)7a7b284e1297
addedKleene's theoremd14ee53639c2
addedRecursive definition of regular languages242a264c4084
addedFinite languages are regulara4760ea7938d
addedEven number of a's / a's then b's3a3a6362e557
addeda^n b^n is not regular7e95dc6b6674
addedEquivalent characterizations of regular languages6910c01ed017
addedClosure under Boolean, regular, and trio operations1b6a193ffc7b
addedClosure under quotient with arbitrary languageffee83dc0962
addedReverse automaton construction56a02c486e66
addedEquivalence of two DFAs is decidablea279c2ccb905
addedContainment, disjointness, emptiness, universality, membership decidablef4ba7bf9b07e
addedUniversality NP-complete for singleton alphabetd16e823d743d
addedUniversality PSPACE-complete for larger alphabetsaa880d71490b
addedUniversality with squaring has exponential space lower bound49c67fda264f
addedRegular languages as minimal elementary substructurefb02eb40253b
addedREGULAR equals DSPACE(O(1))f212b8f7bc64
addedREGULAR ≠ AC^0a51c969f0e8f
addedREGULAR does not contain AC^086ff8429b7bc
addedSpace lower bound for non-regular languagesb6fe79e17363
addedDSPACE(o(log log n)) equals regular languages05ae70176e4c
addedEvery regular language is context-freed035c43ede4d
addedEqual number of a's and b's is context-free but not regulara604be4bbd43
addedFinite languages subclassf072ac6bd368
addedStar-free languages772c8d9d3461
addedOrdinary generating function of a language7a09cb96262c
addedGenerating function of a regular language is rational2ba4eba7298e
addedWord-count sequence is constant-recursive2bc2c4237331
addedDyck language non-regularity via Catalan numbers078d41f9a19e
addedAsymptotic word count for regular languages0749351ad6e5
addedZeta function of a language989df7e51e85
addedZeta function of regular language not generally rationaledbf3d8f0771