Consider rational numbers given as their decimal expansions, then for every number we can build a finite automaton able to accept it. To simplify the argument, assume that finite rational expansions are followed by an infinite number of zeros. In such case it is easy to see that the automaton that accepts such numbers would have to have a finite (possibly empty) non-repeating part and a repeating part. The automaton accepts the number in the same sense as $\omega$-automata do, i.e.

A run of a Büchi automaton on an $\omega$-word is an infinite sequence of states and transitions.

A run is accepting if it visits the set of final states infinitely often.

Source (Wikipedia article is non-functional in this regard)

Looking for a similar equivalence with PDA I thought of continued fractions as a good candidate, but I don't have a good way to get convinced / dissuaded that is the case.

Some of my thoughts in this direction: what is the number representing the Dyck language? Suppose you encode open parenthesis as 1 and closing parenthesis as 0, and the number is thus given by $\{w\;|\;\#(w)_0 = \#(w)_1 \land \forall vu = w: \#(v)_0 \leq \#(v)_1\}$. To me this seems like a whole class of numbers rather than a single number, but maybe my example is unhelpful.

  • $\begingroup$ Interesting question. Certainly the language of decimal expressions of rationals is regular, but it seems that in some sense that the language of algebraic integers might also be regular, since (my memory is hazy here, so I may be wrong) all algebraic integers are expressible as finite or periodic continued fractions. $\endgroup$ – Rick Decker Dec 4 '15 at 19:59
  • $\begingroup$ The continued fraction representation for $\sqrt2$ seems to be $[1;2,2,2,,\dots]$. This seems to be as much as a repeating part as for $0.3333\dots$? Is that not "regular"? $\endgroup$ – Hendrik Jan Dec 4 '15 at 21:37
  • $\begingroup$ @HendrikJan what I mean is the digits of the decimal expansion. To the best of my memory decimal expansion of $\sqrt{2}$ doesn't have repetitions in it suitable for being described by a regular grammar. $\endgroup$ – wvxvw Dec 5 '15 at 15:43
  • $\begingroup$ The last part of the question seems to overlook the difference between finite words vs infinite words. The Dyck language is a set of finite words, so if you treat each of them as a number, then they are all finite sequences of 0's and 1's (and thus rational). You are trying to reason about infinite decimal expansions of numbers, which are infinite words, so the Dyck language isn't relevant. In general, PDA's won't work -- they only accept finite words. I suspect you need a generalization of PDA's for infinite words. I don't know if such a thing exists, offhand. $\endgroup$ – D.W. Dec 6 '15 at 19:33

Your Answer

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

Browse other questions tagged or ask your own question.