patternMinor
Irregularity of language of prefixes of decimal expansion of pi
Viewed 0 times
irregularityexpansionprefixesdecimallanguage
Problem
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.
$$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.
Solution
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.
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.
Context
StackExchange Computer Science Q#106106, answer score: 4
Revisions (0)
No revisions yet.