1
$\begingroup$

I'm trying to prove the following identity: $$ ({L_A}^*\ L_B)^+ = (L_A \cup L_B)^*L_B $$

which is clearly true as both sides will exactly match "any sequence of A and B ending with B" :

$$ B, AB,AAB, ABBABAB, ... $$

I tried thinking about the set properties and even tried to reasoning about the NFA constructed by the the two sides of the equation but to no avail so far.

Does anyone know how to prove it?

$\endgroup$
1
$\begingroup$

The idea is to prove separately the two inclusions, each of them using induction.

Part 1: $(L_A^*L_B)^+ \subseteq (L_A \cup L_B)^* L_B$

We will prove by induction that for all $n \geq 1$, $(L_A^*L_B)^n \subseteq (L_A \cup L_B)^* L_B$.

When $n = 1$, we need to show that $L_A^* L_B \subseteq (L_A \cup L_B)^* L_B$. This is clear since $L_A \subseteq L_A \cup L_B$. (More formally, we could prove inductively that $L_A^mL_B \subseteq (L_A \cup L_B)^m L_B$ for all $m \geq 0$.)

Suppose that $(L_A^* L_B)^n \subseteq (L_A \cup L_B)^* L_B$, and let $w \in (L_A^* L_B)^{n+1}$. Thus we can write $w = xy$, where $x \in L_A^* L_B$ and $y \in (L_A^* L_B)^n$. Since $L_A,L_B \subseteq L_A \cup L_B$, it follows that $x \in (L_A \cup L_B)^*$. By assumption, $y \in (L_A \cup L_B)^* L_B$. Hence $xy \in (L_A \cup L_B)^* L_B$.

Part 2: $(L_A \cup L_B)^* L_B \subseteq (L_A^* L_B)^+$.

We will prove by induction that for all $n \geq 0$, $(L_A \cup L_B)^n L_B \subseteq (L_A^* L_B)^+$.

When $n = 0$, we need to show that $L_B \subseteq (L_A^* L_B)^+$. Since $\epsilon \in L_A^*$, it follows that indeed $L_B \subseteq L_A^* L_B \subseteq (L_A^* L_B)^+$.

Suppose that $(L_A \cup L_B)^n L_B \subseteq (L_A^* L_B)^+$, and let $w \in (L_A \cup L_B)^{n+1} L_B$, so that $w = xy$, where $x \in L_A \cup L_B$ and $y \in (L_A \cup L_B)^n L_B \subseteq (L_A^* L_B)^+$. We consider two cases.

Case 1: $x \in L_A$. Since $y \in (L_A^* L_B)^+$, we can write $y = st$, where $s \in L_A^* L_B$ and $t \in (L_A^* L_B)^*$. Thus $xs \in L_A L_A^* L_B \subseteq L_A^* L_B$, and so $w = xst \in L_A^* L_B (L_A^* L_B)^* = (L_A^* L_B)^+$.

Case 2: $x \in L_B$. In this case $x \in L_A^* L_B$, and so $w = xy \in L_A^* L_B (L_A^* L_B)^+ \subseteq (L_A^* L_B)^+$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Although I can't do the proof completely right now, maybe looking at $(L_A^* L_B)^+ \subseteq (L_A \cup L_B)^*L_B$ and $(L_A \cup L_B)^*L_B \subseteq (L_A^* L_B)^+$ helps here. So from left to right: If you take a word $w \in (L_A^* L_B)^+$, can you split it up into $0..m$ subwords of the form $(L_A \cup L_B)$ and one postfix-subword of form $L_B$? I hope this helps you.

| cite | improve this answer | |
$\endgroup$

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.