8
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Perhaps periodic or eventually periodic. $\endgroup$ – Yuval Filmus Jan 1 '18 at 21:24
  • $\begingroup$ Pumping: Your statement about infinite strings is hardly an analogue of the Pumping Lemma, which says that sufficiently long words in a regular language contain a substring which may be repeated to yield another word. It does not say that all words have that form! $\endgroup$ – PJTraill Jan 8 '18 at 11:51
  • $\begingroup$ Terminology: You talk about a string being regular, whereas the term regular is normally applied to languages. $\endgroup$ – PJTraill Jan 8 '18 at 11:53
15
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • 3
    $\begingroup$ Nice. Perhaps add explicitly that $\omega$-regular languages are finite unions of languages $AB^\omega$, where $A,B$ regular. Don't know about pumping, but sometimes it is useful to observe that each $\omega$-regular language must contain an eventually periodic string. $\endgroup$ – Hendrik Jan Jan 1 '18 at 21:56
  • 10
    $\begingroup$ I've always hated the standard presentation of the pumping lemma for being so damn obtuse. When you get right down to it, all it really says is that since there's a finite set of states, any string with more symbols than there are states must visit some state twice during a run of the automaton. The symbols participating in this loop are the ones you can "pump". Cast in this light, it is clear that there is an analog when we transition to infinite strings but retain finite states; so the question is not "is there a pumping lemma?" but "how much more complicated is the pumping lemma?". $\endgroup$ – Daniel Wagner Jan 1 '18 at 23:16
  • $\begingroup$ @DanielWagner: Wow, yeah... the standard presentation is indeed pretty damn obtuse and yours makes it vividly clear. Thank you for that explanation! $\endgroup$ – user541686 Jan 2 '18 at 9:47
  • 4
    $\begingroup$ @DanielWagner: the pumping lemma certainly is confusing, but the advantage of the standard presentation is that it does not refer to the mechanics of automata, regular expressions, or any other particular way of defining regular languages. It only talks about strings! $\endgroup$ – Max Jan 2 '18 at 11:51
  • $\begingroup$ @Max A dubious advantage indeed! $\endgroup$ – Daniel Wagner Jan 2 '18 at 16:13
3
$\begingroup$

This is a basic result in Type Two Effectivity, which I think answers your question from a computable point of view. In the following, our languages consist only of infinite strings. We denote the set of infinite strings $\Sigma^\omega$.

Theorem: If a realizable automaton terminates on every infinite string, then the language of the automaton is equal to $S\Sigma^\omega$ where $S$ is a finite set of finite strings.

The proof is by Konig's lemma.

The conclusion is that a language over infinite strings is either "simple" in some sense (which is an interesting fact) or undecidable. Any non-trivial notion of language over infinite strings is undecidable.

You can presumably study less simple languages if you allow membership to be semidecidable rather than decidable. This can still be considered "computer science" and not just infinitary mathematics (it's to do with search problems instead of decision problems; semidecidability is in a sense sufficient for doing a search).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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