4
$\begingroup$

Let $L_{\pi}$ be the language consisting of prefixes of the decimal expansion of $\pi$: $$L_\pi = \{3, 31, 314, 3141, 31415, 314159, \ldots\}.$$ Prove that Lπ is not DFA-recognizable. You may use the fact that $\pi$ cannot be written as a repeating decimal, that is, there are no sequences of digits $d_1, d_2, \ldots,d_m$ and $e_1, e_2, \ldots,e_n$ such that

$$\pi = d_1.d_2\cdots d_ne_1e_2\cdots e_n=d_1.d_2 \cdots d_m(e_1\cdots e_n)(e_1\cdots e_n)(e_1\cdots e_n)\cdots.$$

This is how I started my proof:

Proof: by contradiction.

Assume $L_\pi = L(M)$ for some DFA $M$. We'll construct a diabolical string $x$ such that $x\notin L_\pi$, but $M$ accepts $x$.

Let $x = d_1.d_2\cdots d_ne_1e_2\cdots e_n=d_1.d_2 \cdots d_m(e_1\cdots e_n)(e_1\cdots e_n)(e_1\cdots e_n)\cdots$; clearly $x\in L$.

Go through $n + 1$ states, only $n$ states in $M_1$ so $q_i = q_j$ for some $i, j$.

I based my proof off of this: https://courses.cs.cornell.edu/cs2800/wiki/images/2/29/Sp19-lec24-pumping-board.pdf

I'm stuck at the part where I'm trying to make a contradiction.

$\endgroup$
  • 1
    $\begingroup$ You'll need to use some fact about pi, as this isn't true for all numbers. You might start by pondering whether have any ideas what facts about pi might be relevant, and why you think they might be relevant. If you have no idea, maybe start reading about what is known about pi: en.wikipedia.org/wiki/Pi $\endgroup$ – D.W. Mar 27 '19 at 0:26
  • 1
    $\begingroup$ Have you recognized the similarity between repeated decimal and pumping lemma? $\endgroup$ – John L. Mar 27 '19 at 6:07
  • $\begingroup$ What do you mean by "d1.d2 · · · dne1e2 · · · en = d1.d2 · · · dm(e1 · · · en)(e1 · · · en)(e1 · · · en)· · ·"? When you say "x = d1.d2 · · · dne1e2 · · · en", what are d1,...,dn,e1,...,en? When you say "Go through n + 1 states, only n states in M1 so qi = qj for some i, j", what is n? What is M1 and what are qi,qj? Please edit your question to clarify the issues above. $\endgroup$ – xskxzr Mar 27 '19 at 12:36
  • $\begingroup$ Your title is way too general. $\endgroup$ – Yuval Filmus Mar 28 '19 at 8:05
4
$\begingroup$

The pumping lemma tells you that, if $L_\pi$ is regular, there is a word of the form $uvw$ such that $uv^kw\in L_{\pi}$ for all $k\in\Bbb N$, where $|v|>0$.

Note that if a word is in $L_\pi$, any nonempty prefix of that word is also in $L_\pi$. In particular, $uv^k\in L_\pi$ for all $k\in\Bbb N$. In other words, $uv$, $uvv$, $uvvv$, $\cdots$ are prefixes of the decimal expansion of $\pi$.

So $\pi=uvvv\cdots$, which contradicts the fact that $\pi$ cannot be written as a repeating decimal.


Here are several exercises that describe the general situation. The first two exercises are pointed out by gnasher729's comment. The last exercise comes from Yuval's comment

Exercise 1. Show the set of all prefixes of the decimal expansion of a rational number is a regular language.

Exercise 2. Show the set of all prefixes of the decimal expansion of an irrational number is not a regular language.

Exercise 3. What about binary expansion? What if the base is changed to another number?

Exercise 4. A language is a prefix language if for any two of its words $w_1$ and $w_2$, either $w_1$ is a prefix of $w_2$ or $w_2$ is a prefix of $w_1$. Show that for a prefix language $L$, $L$ is regular if and only if $L$ is context-free. In particular, $L_\pi$ cannot be context-free.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ So the prefixes of the decimal expansion of a rational number can be recognised, and the prefixes of the decimal expansion of an irrational number can’t. $\endgroup$ – gnasher729 Mar 27 '19 at 16:27
  • 1
    $\begingroup$ The same argument seems to work if you replace "regular" by "context-free". $\endgroup$ – Yuval Filmus Mar 28 '19 at 8:41

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.