Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
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 '13 at 12:35
1  
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 '13 at 12:38

3 Answers 3

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.

share|improve this answer

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$.

share|improve this answer
    
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 '13 at 17:30
    
That may be right and a good reason to post another answer. –  Raphael Feb 11 '13 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 '13 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 '13 at 17:38
    
No, I'm just too lazy to type it. –  Dan Feb 11 '13 at 17:39

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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