Problem der Äquivalenz zweier Regulärer Ausdrücke

Einfache Sprache

Def. Problem der Äquivalenz zweier Regulärer Ausdrücke

Die Sprache $\mathrm{EQ_{REX}}$ enthält Paare Reguläre Ausdrücke die die gleiche Sprache erkennen. Also

$$\mathrm{EQ_{REX}} = \{\langle R,S\rangle\mid R \text{ und } S \text{ sind äquivalente Reguläre Ausdrücke}\}$$

Sätze

• Satz EQ-REX ist in PSPACE