3
$\begingroup$

Recall that a language is $\omega$-regular if and only if it is recognized by a Büchi automaton. 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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Feb 3, 2013 at 12:35
  • 1
    $\begingroup$ 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. $\endgroup$
    – G. Bach
    Feb 3, 2013 at 12:38

3 Answers 3

6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

The question has nothing to do with ($\omega$-)regular languages. Indeed, it is a consequence of the equality $$ (L_1 + L_2)L = L_1L + L_2L $$ which holds for all subsets $L_1, L_2$ of $A^*$ and all subsets $L$ of $A^\omega$. The proof is straightforward: if $w \in (L_1 + L_2)L$, then $w = uv$ for some $u \in L_1 + L_2$ and some $v \in L$. Thus either $u \in L_1$ or $u \in L_2$ whence either $uv \in L_1L$ or $uv \in L_2L$. In the opposite direction, if $w \in L_1L + L_2L$, then either $w \in L_1L$ or $w \in L_2L$. In the first [second] case, $w = uv$ for some $v \in L$ and some $u \in L_1$ [$u \in L_2$]. In both cases, $w \in (L_1 + L_2)L$.

$\endgroup$
2
$\begingroup$

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:

First automaton
[source]

Second automaton [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$.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Dan
    Feb 11, 2013 at 17:30
  • $\begingroup$ That may be right and a good reason to post another answer. $\endgroup$
    – Raphael
    Feb 11, 2013 at 17:32
  • $\begingroup$ 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. $\endgroup$
    – Dan
    Feb 11, 2013 at 17:36
  • $\begingroup$ @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? ;)) $\endgroup$
    – Raphael
    Feb 11, 2013 at 17:38
  • $\begingroup$ No, I'm just too lazy to type it. $\endgroup$
    – Dan
    Feb 11, 2013 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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