# Distributivity of $\omega$-regular expressions

How can I prove that

$\qquad (E_1 + E_2).F^\omega$

is equivalent to

$\qquad {E_1.(F^\omega)+E_2.(F^\omega)}$

where

• both expressions are omega regular expressions, and
• $E_1$, $E_2$ and $F$ are arbitrary regular expressions with $\epsilon \notin L(F)$.

One way I could think of is to convert expression to a DFA and check if it is equivalent.

Or I will really appreciate a hint on how to do the equivalence proof, but how to represent $E_1$, $E_2$ and $F$ in DFA.

-
 What's an omega regular expression? What do you mean by infinity regular expression? – saadtaame Feb 3 at 11:59 @saadtaame Search it online, it's a fairly known thing. A language is ω-regular if and only if it is recognized by a Büchi automaton. – Pål GD Feb 3 at 12:10 I think your approach to 1. is as easy as it gets; have you actually tried that path? I don't understand what you say in 2. at all; try using the proof for the equivalence of NBA and omega-regular expressions. – Raphael♦ Feb 3 at 12:35 I don't think you have to construct anything for 1. here; simply express the languages represented by the two omega-regular expressions as sets and then show that they are equal, which is just a little set arithmetic. As was already pointed out, please clarify 2. – G. Bach Feb 3 at 12:38 This question is already asked at cstheory.stackexchange.com, and I already answered it. – Dan Feb 3 at 14:27

As suggested by Raphael, here's a proof doing it via the sets represented by those expressions.

$\qquad L_\omega((E_1+E_2) \cdot F^\omega) \\= L(E_1+E_2) \cdot L_\omega(F^\omega) \\= (L(E_1) \cup L(E_2)) \cdot L_\omega(F^\omega) \\= \{w_1w_2 | w_1 \in (L(E_1) \cup L(E_2)) \wedge w_2 \in L_\omega(F^\omega) \} \\= \{w_1w_2|(w_1 \in L(E_1) \wedge w_2 \in L_\omega(F^\omega)) \lor (w_1 \in L(E_2) \wedge w_2 \in L_\omega(F^\omega))\}\\= \{w_1w_2|(w_1 \in L(E_1) \wedge w_2 \in L_\omega(F^\omega))\} \cup \{w_1w_2|(w_1 \in L(E_2) \wedge w_2 \in L_\omega(F^\omega))\} \\= (L(E_1)\cdot L_\omega(F^\omega)) \cup (L(E_2)\cdot L_\omega(F^\omega))\\=L_\omega(E_1 \cdot F^\omega) \cup L_\omega(E_2 \cdot F^\omega)\\=L_\omega(E_1\cdot F^\omega + E_2 \cdot F^\omega)$

So the only thing that's actual work here is to translate the logical operators into set operators.

-

We have to show that

$\qquad (E_1 + E_2).F^\omega = E_1.(F^\omega) + E_2.(F^\omega)$.

We have do to some preparation. $E_1, E_2$ and $F$ are regular expressions, so they have (deterministic) finite automata $A_1, A_2, A_F$. It is easy to see that we can construct NBA for the left and right hand side from those, respectively:

[source]

[source]

Showing that these are correct should be a simple exercise, given the proof for the equivalence of $\omega$-regular expressions and NBA you should have seen.

Note that the transitions going into the DFA connect with their respective initial states, while the outgoing one originate from their final states (w.l.o.g. there is only one in each DFA).

Now, as usual, show $\subseteq$ and $\supseteq$ separately. Both directions work in the same way; let's look at it for $\subseteq$.

Assume a word $w$ is in the language generated by $(E_1 + E_2).F^\omega$. Then, there is an accepting (infinite) path in above automaton. The same path basically works for the lower automatong: depending on whether the run goes through $A_1$ or $A_2$, replace $q_m$ with $q_{m1}$/$q_{m2}$ and $q_e$ similarly.

A similar construction works for $\supseteq$.

-
 You do not need to look at the automata. You can do the whole proof more easily by just looking at how a word $\alpha \in L((E_1 + E_2) \cdot F^\omega)$ is constructed. – Dan Feb 11 at 17:30 That may be right and a good reason to post another answer. – Raphael♦ Feb 11 at 17:32 Yes, perhaps. The solution should be somewhere in my notes as it is a simple exercise our students are asked to solve it at the very beginning of the course. – Dan Feb 11 at 17:36 @Dan I am quite sure the question came up during homework, that's why I waited before I gave an answer. (Come on, you need notes for this? ;)) – Raphael♦ Feb 11 at 17:38 No, I'm just too lazy to type it. – Dan Feb 11 at 17:39