1
$\begingroup$

A regular expression $r$ is said to be in disjunctive normal form if it can be written in the form $r = r_1 +r_2 +\dots+r_n$ for some $n ≥ 1$, where none of the regular expressions $r_1, r_2, \dots, r_n$ contains the symbol $+$ (union).

For example, the regular expression $a^*b^* + (ab)^* + (c(acb)^*)^*$ is in disjunctive normal form.

The task is to prove that every regular language can be specified by a regular expression in disjunctive normal form. Considering that every regular language by default can be represented by a regular expression, the question now seems to simplify to proving that any regular expression can be converted to or expressed in disjunctive normal form. Any idea on how that is possible?

$\endgroup$
  • 1
    $\begingroup$ Note that $+$ and $\cdot$ in linear expressions are distributive and that you can express any regular subexpression of the form $(\sum_i r_i)^\ast$ also as $(\prod_i r_i^\ast)^\ast$. These equivalence should suffice to show what you want to show. $\endgroup$ – ttnick Feb 27 '18 at 17:39
3
$\begingroup$

The proof is by structural induction. I will define an operator $T$ that takes an arbitrary regular expression, and outputs an equivalent regular expression in disjunctive normal form:

  • Base cases: $T[\epsilon] = \epsilon$, $T[\sigma] = \sigma$, $T[\emptyset] = \emptyset$.
  • If $r = s + t$, then we define $T[r] = T[s] + T[t]$.
  • If $r = st$, by induction we know that $T[s] = s_1 + \cdots + s_n$ and $T[t] = t_1 + \cdots + t_m$, where $+$ doesn't appear in any of the $s_i$ or $t_j$. We define $T[r] = \sum_{1 \leq i \leq n} \sum_{1 \leq j \leq m} s_i t_j$.
  • If $r = s^*$, by induction we know that $T[s] = s_1 + \cdots + s_n$. We define $T[r] = (s_1^* \cdots s_n^*)^*$.

It is routine to prove by structural induction that $T[r]$ is a regular expression in disjunctive normal form which is equivalent to $r$.

$\endgroup$

Your Answer

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