Proof for formal languages

Question

Prove that for all languages $M,N \subseteq \Sigma^*$ applies: $(M+N)^* = (M^*N^*)^*$

Hi!

I do'nt really understand why this applies: The first term uses the Kleene star on the union of M and N and therefore contains the empty word $\lambda$ and all possible string concatenations of the union. The second term contains all possible concatenations of M plus the empty word concatenated to the possible concatenations of N plus the empty word. Let $m \in M, n \in N, n \not\in M$. The word $nm$ can be expressed by the first, but not the second term $(M^*N^*)^*$. Where is my mistake?

How can I write the proof the correct way?

Thanks in advance

Answer 1

Another approach: identities in Kleene algebra...

(a) $M \subseteq M^* \subseteq M^*N^* \text{ and } N \subseteq N^* \subseteq M^*N^* \\\text{ so } (M+N) \subseteq M^*N^* \\\text{ so } (M+N)^* \subseteq (M^*N^*)^* \\\text{QED one way} $

(b) $ M^* \subseteq (M+N)^* \text{ and } N^* \subseteq (M+N)^* \\\text { so } M^*N^* \subseteq (M+N)^*(M+N)^* \subseteq (M+N)^* \\\text { so } (M^*N^*)^* \subseteq ((M+N)^*)^* = (M+N)^* \\\text{QED other way} $

Answer 2

The word $nm$ can be expressed by the first, but not the second term $(M^∗N^∗)^∗$. Where is my mistake?

There's your mistake.

$m\in M^*N^*$ because it is one word from $M$ followed by zero words from $N$.

$n\in M^*N^*$ too because it is zero words from $M$ followed by one word from $N$.

Thus $mn\in (M^∗N^∗)^∗$ because it consists of two words from $M^*N^*$.

In general, $M+N\subseteq M^*N^*$ for all languages $M,N$.

Answer 3

Your word $nm$ can be written as $\lambda nm\lambda$, where $\lambda$ is the empty word. Clearly $\lambda\in M^*$, $n\in N^*$, $m \in M^*$, and $\lambda\in N^*$, so $nm=(\lambda n)(m\lambda)\in(M^*N^*)(M^*N^*)\subseteq(M^*N^*)^*$.

Answer 4

Regex/Automata-based Approaches

Informally

The regular expression (M|N)* matches the same thing as (M*N*)*. This is obvious by inspection: both of them denote a completely arbitrary (and potentially empty) mixture of M's and N's.

By Finite State Machine Equivalence

We can show the expressions are equivalent by constructing the equivalent deterministic finite automata (DFA's) and showing that these are equivalent: same number of states, same transitions.

In constructing these automata, we are justified in treating M and N as simple input alphabet symbols, because if two automata are both shown to consume arbitrary mixtures of the symbols M and N, the contents generated by M and N are irrelevant to the equivalence.

M and N can be regarded as possible "super tokens" recognized by some subordinate automata which we need not consider.

You will find that both automata just have one state, which is their acceptance state, and transitions back to that state on either M and N. So they accept the initial empty prefix when no input is given, and thereafter accept either M or N as it occurs.

You can construct a DFA formally. Start by making an NFA graph, and then do the subset construction. It's a 15 minute pencil-and-paper exercise for these trivial expressions.

By Regex Derivatives

See this 1964 paper Derivatives of Regular Expressions by Janusz A. Brzozowski.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.98.4378

The idea is that we can compute a derivative of an expression with respect to an input alphabet symbol, such that the result of the derivation is a new regular expression which expresses a match for the remaining input.

The most basic derviative is that of the regular expression $a$ with respect to the symbol $a$, the result of which is empty: $D_a a = \lambda$.

Another example is the derivative $D_a M*, M$ is $(D_a M)M*$. That is to say, the derivative of the $M*$ regular expression with respect to any symbol $a$ is the same as the derivative of just $M$ with respect to $a$, catenated with $M*$. This says that if we get a match for $M$, we are left, once again, with $M*$ facing the remaining input.

Thus suppose take $a$ to be $M$. Then we have $(D_M M)M*$, in which $(D_M M)$ disappears by the first derivative rule, namely $D_a a = \lambda$ leaving us with $\lambda M*$ which is just $M*$. That tells us that that since after consuming $M$, the rest of the input faces the original regular expression, the regular expression must be consuming an arbitrary number of $M$.

We can use regex derivatives to show that two different regexes both accept an arbitrary mixture of two symbols, which shows that the two expressions denote equivalent languages.