# What's the true meaning of $(a + b)^\omega$ in regular expression

I'm starting to dabble in language theory, regular expression & infinite words.

I'm not quite sure I completely get the meaning of this expression:

$$(a + b)^\omega$$

$$^w$$ meaning infinite repetition, I'm not positive it's standard syntaxe or just our class.

My main question is - do I have to "settle" on either a or b after some position in the infinite word? $$abbbbaab^\omega$$ would be fine but not $$abbbbaa[ a | b]^\omega$$ (e.g. I keep having either a or b infinitely)? My understanding is that an English translation would be "you must either have a, or b, at any given position indefinitely". So the + would be like a or condition, essentially.

Expending on that, then $$((a+b)(c+d))^\omega$$ would accept any alternating patter of (a or b)(c or d), e.g. things like acbcbcadad... but again wouldn't have to "settle" on either $$(ac)^\omega$$ or $$(ad)^\omega$$ or $$(cc)^\omega$$ etc...

• $r^\omega$ is defined very similarly to $r^*$, only you are now taking infinitely many words and concatenating them. See for example Wikipedia. – Yuval Filmus Feb 5 at 16:19
• It's omega, not w. – Yuval Filmus Feb 5 at 16:24
• Corrected - yeah that would have looked pretty noob. – LogicOnAbstractions Feb 5 at 16:41

## 2 Answers

For a language $$L$$ not containing $$\epsilon$$, $$L^\omega$$ is obtained by concatenating infinitely many words from $$L$$: $$L^\omega = \{ w_1 w_2 \ldots : w_1,w_2, \ldots \in L \}.$$ The words can be arbitrary words from $$L$$. In particular, $$\Sigma^\omega$$ consists of all $$\omega$$-words over $$\Sigma$$.

When $$\epsilon \in L$$, then the definition is the same, but we only accept a resulting word if it is infinite. This is equivalent to removing $$\epsilon$$ from $$L$$, or to require that at most finitely many of the words are $$\epsilon$$.

Compare this to the definition of $$L^*$$: $$L^* = \{ w_1 w_2 \ldots w_n : n \in \mathbb{N}, w_1,w_2,\ldots,w_n \in L \}.$$ Here also, the words need not be the same.

• Ah - so the key part would be " The words can be arbitrary words from L ". So in essence, since (for the 2nd example) ac and bc and bd are arbitrary words from L, it does imply I do not need to "settle" on either ac or bc or bd indefinitely. – LogicOnAbstractions Feb 5 at 16:26

The notation is standard but it's an omega ($$\omega$$, the first infinite ordinal; basically, the infinity in "There are infinitely many natural numbers"), not a $$w$$ (the 23rd letter of the Latin alphabet).

Both as a closure operator applied to languages and as an operator in $$\omega$$-regular expressions, $$^\omega$$ is directly analogous to $${}^*$$, except it denotes the concatenation of infinitely many things, rather than any finite number of them.