patternModerate
Is there an analog of "regular" for infinite strings?
Viewed 0 times
infiniteregularfortherestringsanalog
Problem
Consider the sequence $s_1 = (1, 0, 1, 0,\dots)$. It seems "regular" in a way that, e.g. $s_2 = (1, 2, 3, 4,\dots)$ is not.
I'm not sure how to formalize this intuition though. One thing which jumps out at me is that $L =\{(0 1)^n\}$ is a regular language, and $s_1$ is in some sense the limit of the strings in this language.
Is there a terminology for considering these infinite strings? Do we have something analogous to the pumping lemma, whereby we can state that any such "infinite regular" string is of the form $x y^ {\infty}z$ with $x$, $y$, $z$ finite?
I'm not sure how to formalize this intuition though. One thing which jumps out at me is that $L =\{(0 1)^n\}$ is a regular language, and $s_1$ is in some sense the limit of the strings in this language.
Is there a terminology for considering these infinite strings? Do we have something analogous to the pumping lemma, whereby we can state that any such "infinite regular" string is of the form $x y^ {\infty}z$ with $x$, $y$, $z$ finite?
Solution
Probably the most specific term to describe your first string, $010101\dots$ is periodic. A string $x_1x_2\dots$ (finite or infinite) is periodic if there is some $t$ such that, for all $i$, $x_i=x_{i+t}$. In the case of this example, we can take $t=2$. A slightly weaker notion is that a string is eventually periodic if there are $n$ and $t$ such that $x_i=x_{i+t}$ for all $i\geq n$.
More generally, though, there is a direct analogue of the regular languages, which is the $\omega$-regular languages. These are recognized by natural generalizations of finite automata. The state set is still finite but the acceptance criterion must be modified to deal with infinite words – in particular, we can't just say "Accept if the automaton finishes in an accepting state" because the automaton never finishes processing its infinite input.
The simplest class of automata for infinite words are Büchi automata. They are defined exactly like the finite automata you're used to, and they accept their input if at least one accepting state is visited infinitely often during the automaton's run. One difference from ordinary finite automata is that it turns out that nondeterministic Büchi automata are more powerful than deterministic ones, and the $\omega$-regular languages are the ones accepted by nondeterministic Büchi automata. Other sensible acceptance criteria lead to other automaton models which accept the same class of langauges.
Note that it doesn't quite make sense to write $xy^\omega z$, since you can't have anything after an infinite sequence of $y$s. At least, you can't if the positions in your string are indexed by the natural numbers. If they're indexed by larger ordinals this can make sense.
I can't actually remember if there's an analogue of the pumping lemma for $\omega$-regular languages. This is slightly embarrassing, though it is most of a decade since I taught a graduate class on this stuff.
More generally, though, there is a direct analogue of the regular languages, which is the $\omega$-regular languages. These are recognized by natural generalizations of finite automata. The state set is still finite but the acceptance criterion must be modified to deal with infinite words – in particular, we can't just say "Accept if the automaton finishes in an accepting state" because the automaton never finishes processing its infinite input.
The simplest class of automata for infinite words are Büchi automata. They are defined exactly like the finite automata you're used to, and they accept their input if at least one accepting state is visited infinitely often during the automaton's run. One difference from ordinary finite automata is that it turns out that nondeterministic Büchi automata are more powerful than deterministic ones, and the $\omega$-regular languages are the ones accepted by nondeterministic Büchi automata. Other sensible acceptance criteria lead to other automaton models which accept the same class of langauges.
Note that it doesn't quite make sense to write $xy^\omega z$, since you can't have anything after an infinite sequence of $y$s. At least, you can't if the positions in your string are indexed by the natural numbers. If they're indexed by larger ordinals this can make sense.
I can't actually remember if there's an analogue of the pumping lemma for $\omega$-regular languages. This is slightly embarrassing, though it is most of a decade since I taught a graduate class on this stuff.
Context
StackExchange Computer Science Q#86156, answer score: 15
Revisions (0)
No revisions yet.