I'm trying to create a formal algorithm in order to determine whether two given regular expressions $a$, $a'$ define identical/equal or unequal languages and if those languages are subsets of each other?

(I'm not sure if following thoughts are correct and formal enough and I'm glad if you spot mistakes and improve my algorithm.)

Let $a$,$a'$ be regular expressions. Now, we want to determine: $$\bigg(L(a)=L(a') \text{ or } L(a)\neq L(a') \text{ and } \Big((L(a)\subset L(a') \text{ or } (L(a')\subset L(a)\Big)\bigg)$$

In order to do that, we will "convert" the regular expressions $a$ and $a'$ into DFA's $M$ and $M'$. Those automatons have minimal and non-redundant states $K=\{q_1, \cdots ,q_n\}$ and $K'=\{q_1, \cdots ,q_m\}$ with $n,m \in \mathbb{N}$.

Now, we can simply determine, whether $K=K'$ with showing $K\subseteq K'$ and $K' \subseteq K \implies K=K' \implies L(a) = L(a')$. If the above equation is not true, then we can imply that $K\neq K' \implies L(a) \neq L(a')$. Furthermore, with $K\neq K'$ and $K \nsubseteq K'$ and $K'\subseteq K \implies K' \subset K \implies L(a')\subset L(a)$.
Analogue: $K\neq K'$ and $K' \nsubseteq K$ and $K\subseteq K' \implies K \subset K' \implies L(a) \subset L(a')$ .

Is this enough or do I need to compare final states, transfer function and the alphabet in order to be sure $L(a)=L(a')$ etc.?

  • $\begingroup$ Hint: Consider the following two DFAs $(\{q_0\}, \{a\}, (q_0, a) \mapsto q_0, q_0, \{q_0\})$ and $(\{q_0\}, \{a\}, (q_0, a) \mapsto q_0, q_0, \varnothing)$ (with (state set, alphabet, transition function, initial stat, accepting states)). Obviously the automata are minimal for $\{a\}^\ast$ and $\varnothing$ but have the same state set. $\endgroup$ – ttnick Nov 4 '18 at 22:16

If behaviour of the automaton didn't depend on the final states, transition function and alphabet, why would we define automata to have those useless things?

  • $\begingroup$ Alright, but how do we compare transition functions? $\endgroup$ – Doesbaddel Nov 5 '18 at 7:28
  • $\begingroup$ @Doesbaddel They're just tables of data. However, the difficulty is that the states might be ordered differently in the two tables and I don't think we know a polynomial-time algorithm to determine whether one table is a reordering of the other (it's probably as hard as graph isomorphism). $\endgroup$ – David Richerby Nov 5 '18 at 10:40

Assuming (as you do) that we can take the problem of turning a regular expression into a DFA as a solved problem and ignore its complexity,(*) then there's a relatively simple algorithm for comparing the languages generated by two regular expressions:

Add to your alphabet two new symbols $\$_1$ and $\$_2$, and form a DFA for the regular expression

$$ ((a)\$_1 + (a')\$_2) $$

All accepting nodes of this DFA will have no outgoing edges, and so may be merged (if you form the minimal DFA, you'll only have a single accepting node, but except for merging all the accepting nodes you don't need to perform further minimization). Furthermore, all incoming edges to this merged accepting node will be labeled with $\$_1$, with $\$_2$, or both.

Examining the edges into this accepting node will tell you everything you wanted to know about the relationship between $L(a)$ and $L(a')$.

If every edge leading into the accepting node is labeled with both $\$_1$ and $\$_2$, then you have equal languages. If every edge is labeled with $\$_1$ but only some are labeled with $\$_2$, then $L(a) \supset L(a')$ (and vice versa). If there are some with $\$_1$ only and others with $\$_2$ only, then neither inclusion relationship holds.

(*) I believe that the DFA for a regular expression with $n$ symbols can have a state space that is $O(2^n)$, or at least is some exponential function of $n$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.