patternMinor
What's the true meaning of $(a + b)^\omega$ in regular expression
Viewed 0 times
expressionmeaningtheomegawhatregulartrue
Problem
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...
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...
Solution
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.
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.
Context
StackExchange Computer Science Q#103892, answer score: 4
Revisions (0)
No revisions yet.