3
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – LogicOnAbstractions Feb 5 at 16:26
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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