Editing Regular language (section)

== Decidability properties ==
Given two deterministic finite automata ''A'' and ''B'', it is decidable whether they accept the same language.<ref>Hopcroft, Ullman (1979), Theorem 3.8, p.64; see also Theorem 3.10, p.67</ref>
As a consequence, using the [[#Closure properties|above]] closure properties, the following problems are also decidable for arbitrarily given deterministic finite automata ''A'' and ''B'', with accepted languages ''L''<sub>''A''</sub> and ''L''<sub>''B''</sub>, respectively:<!---avoiding "L(A)" that has not been defined so far, and might be confused with the language variable "L" above--->
* Containment: is ''L''<sub>''A''</sub> ⊆ ''L''<sub>''B''</sub> ?<ref group=note>Check if ''L''<sub>''A''</sub> ∩ ''L''<sub>''B''</sub> = ''L''<sub>''A''</sub>. Deciding this property is [[NP-hard]] in general; see [[:File:RegSubsetNP.pdf]] for an illustration of the proof idea.</ref>
* Disjointness: is ''L''<sub>''A''</sub> ∩ ''L''<sub>''B''</sub> = {{mset}} ?
* Emptiness: is ''L''<sub>''A''</sub> = {{mset}} ?
* Universality: is ''L''<sub>''A''</sub> = Σ<sup>*</sup> ?
* Membership: given ''a'' ∈ Σ<sup>*</sup>, is ''a'' ∈ ''L''<sub>''B''</sub> ?
<!---todo: give complexity for each problem, discuss other formalisms than just DFA--->

For regular expressions, the universality problem is [[NP-complete]] already for a singleton alphabet.<ref>Aho, Hopcroft, Ullman (1974), Exercise 10.14, p.401</ref>
For larger alphabets, that problem is [[PSPACE-complete#Regular expressions and automata|PSPACE-complete]].<ref>Aho, Hopcroft, Ullman (1974), Theorem 10.14, p399</ref> If regular expressions are extended to allow also a ''squaring operator'', with "''A''<sup>2</sup>" denoting the same as "''AA''", still just regular languages can be described, but the universality problem has an exponential space lower bound,<ref>Hopcroft, Ullman (1979), Theorem 13.15, p.351</ref><ref>{{cite book | url=https://people.csail.mit.edu/meyer/rsq.pdf |author1=A.R. Meyer  |author2=L.J. Stockmeyer  |name-list-style=amp | title=The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space | publisher=13th Annual IEEE Symp. on Switching and Automata Theory | pages=125–129 | date=Oct 1972 }}</ref><ref>{{cite book | url=https://esp.mit.edu/download/827dcf47cbc9cf4a3b04dbf773ea54fb/M3175_meyer-stockmeyer-word-probs.pdf |author1=L. J. Stockmeyer  |author2=A. R. Meyer |contribution=Word Problems Requiring Exponential Time | title=Proc. 5th ann. symp. on Theory of computing (STOC) | publisher=ACM | pages=1–9 | year=1973 }}</ref> and is in fact complete for exponential space with respect to polynomial-time reduction.<ref>Hopcroft, Ullman (1979), Corollary p.353</ref>

For a fixed finite alphabet, the theory of the set of all languages – together with strings, membership of a string in a language, and for each character, a function to append the character to a string (and no other operations) – is decidable, and its minimal [[elementary equivalence|elementary substructure]] consists precisely of regular languages.  For a binary alphabet, the theory is called [[S2S (mathematics)|S2S]].<ref>{{cite book | last=Weyer | first=Mark | date=2002 | title=Automata, Logics, and Infinite Games |chapter=Decidability of S1S and S2S | series=Lecture Notes in Computer Science | volume=2500 | pages=207–230 |chapter-url=https://link.springer.com/chapter/10.1007/3-540-36387-4_12 | doi=10.1007/3-540-36387-4_12 | publisher=Springer| isbn=978-3-540-00388-5 }}</ref>