<p>Think set theory.</p>
<p>We have for L1</p>
<p><span class="math-container">$$ (A - {a}) \subset A^* $$</span>
<span class="math-container">$$ A^*.(A-{a}).A^* \subset A^* $$</span></p>
<p>Then
<span class="math-container">$$ S1 = A^*.\{b\} $$</span>
<span class="math-container">$$ S1 = A^*.(A)^*.A^*.\{b\} $$</span>
<span class="math-container">$$ S2 =  (A^*.(A-{a})).A^*.\{b\} $$</span></p>
<p><span class="math-container">$$ S1 - S2  = a^*b$$</span></p>
<p>Basically you removed everything from A* that does not have a, then you end up with a*.</p>
<p>Same argument goes for L2.</p>
<p>Then:
<span class="math-container">$$ L1.L2 = a*.b.b* = a^*.{b+b*} = a.b^+ $$</span></p>
<p>Note: This does not &quot;reduce&quot; the languages, but help you see how to arrive to the answer.</p>
<p>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.</p>

CC BY-SA 4.0
2021-02-10T14:30:59.927Z
2021-02-10T14:30:59.927Z
Makketronix
<p>I'm new to Theoretical Computer Science, and my textbook says that it is easy to verify that the following language</p>
<p><span class="math-container">\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}</span></p>
<p>is equivalent to <span class="math-container">$L_{1}=a^{*} \cdot b$</span>, <span class="math-container">$L_{2}=b^{*}$</span>, and <span class="math-container">$L_{3}=a^{*} \cdot b^{+}$</span>.</p>
<p>However, I don't seem to understand the process of reducing the languages. Can someone easily explain it to me?</p>

<fl.formal-languages>
Reduction of a language to a shorter equivalent
Kevin
# Reduction of a language to a shorter equivalent

(Asked by: username_0 on 2021-02-09)

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?

**Tags:** fl.formal-languages

---

## 1 answers

### Answer by username_1 on 2021-02-10. Score: 0 | Accepted answer

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.


---

