2

Given a set

S={x∣ there is an x-block of 5's in the decimal expansion of π}

(Note: x-block is a maximal block of x successive 5's)

In the question it is mentioned that there is x-block of successive 5's but in the given link this block is repeated , u can see at the end there are many blocks like where we have 55 , although no relation between between previous occurrences of 55 and new occurrences of 55 , so how can it be regular :

http://www.geom.uiuc.edu/~huberty/math5337/groupe/digits.html

radhika
  • 361
  • Your question has several confusing points. You write "In the question", but what question are you referring to? – Lee Mosher Jan 31 '16 at 16:21
  • 1
    What language are you talking about? Your $S$ rather seems to be a subset of $\Bbb N$ (and many strongly believe that it is $\Bbb N$), not a language. – Hagen von Eitzen Jan 31 '16 at 16:21
  • Also, your link shows only a finite portion of the decimal expansion of $\pi$. Do you mean just the $x$-blocks in that finite portion of the decimal expansion, which would be a finite set and therefore obviously regular? Or do you instead mean the entire infinite decimal expansion of $\pi$, about which very, very little is known with full mathematical rigor? – Lee Mosher Jan 31 '16 at 16:22
  • If it is a finite expansion then even we will have different length of blocks of successive 5 but I think we can count them and construct Finite state automaton for it – radhika Jan 31 '16 at 16:51
  • And if I take the infinite expansion of the π , then how can we call it recursively enumerable as the turing machine will not halt even for the language which belongs to the given set as the decimal expansion of π is infinite – radhika Jan 31 '16 at 17:04

1 Answers1

2

The question is answerable if you say that an $x$-block is a contiguous (though not necessarily maximal) sequence of $x$ 5's in the decimal expansion of $\pi$. For example, if the decimal expansion of $\pi$ contained $\dotsc 555\dotsc$, then we would say that $\pi$ contained a 1-block, a 2-block, and a 3-block.

Under this interpretation, the answer to your question would be that the set $S$ is regular. Here's how: we'd have two possible forms for $S$,

  1. There are blocks of $x$ 5's for any $x\ge 0$.
  2. There is some $k$ such that there is a block of $k$ 5's in $\pi$, but no larger blocks.

In case (1), $S=\{1,2,3,\dotsc\}$ and in case (2) $S=\{1,2,3, \dotsc, k\}$, for some $k\in\mathbb{N}$.

Now we come to the second problem in your question: $S$ is a set of integers, and not a language, so strictly speaking the question of regularity or non-regularity of $S$ makes no sense, since those properties only apply to languages, which are sets of strings over some finite alphabet. That's not a deal-breaker, though, if we specify how we'll represent positive integers as strings of symbols. Here we have lots of reasonable choices: unary, where $n$ would be represented as a string of $n$ ones, or binary, or decimal, and so on.

Once we've settled on a representation (so we're looking at $S$ as $S'$, where $S'$ consists of the strings representing numbers in $S$) , we now have our two cases as

  1. $S'$ = all possible representations of positive integers, which is just $\Sigma^*$ for some alphabet $\Sigma$. We know this is regular.
  2. $S'$ is a finite set of strings, and we know that a finite set is regular.

We're done. Under our interpretation of an $x$-block and our clarification of treating sets of positive integers as sets of strings, we'll have $S'$ regular in any possible case.

Rick Decker
  • 8,718