I'm new to Theoretical Computer Science, and my textbook says that it is easy to verify that the following language

\begin{array}{l} L_{1}=A^{*} \cdot\{b\}-\left(A^{*} \cdot(A-\{a\}) \cdot A^{*} \cdot\{b\}\right) \\ L_{2}=A^{*}-\left(A^{*} \cdot(A-\{b\}) \cdot A^{*}\right) \\ L_{3}=L_{1} \cdot L_{2} \end{array}

is equivalent to $L_{1}=a^{*} \cdot b$, $L_{2}=b^{*}$, and $L_{3}=a^{*} \cdot b^{+}$.

However, I don't seem to understand the process of reducing the languages. Can someone easily explain it to me?


1 Answer 1


Think set theory.

We have for L1

$$ (A - {a}) \subset A^* $$ $$ A^*.(A-{a}).A^* \subset A^* $$

Then $$ S1 = A^*.\{b\} $$ $$ S1 = A^*.(A)^*.A^*.\{b\} $$ $$ S2 = (A^*.(A-{a})).A^*.\{b\} $$

$$ S1 - S2 = a^*b$$

Basically you removed everything from A* that does not have a, then you end up with a*.

Same argument goes for L2.

Then: $$ L1.L2 = a*.b.b* = a^*.{b+b*} = a.b^+ $$

Note: This does not "reduce" the languages, but help you see how to arrive to the answer.

You may have to brush up on the operations of regular expressions, but the general logic should be a bit similar, if you realize that A* is a prefix closure and can be written in many forms.


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