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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+15 votes

**(a) **Given a set:

$$S = \left\{x \mid \text{ there is an x-block of 5's in the decimal expansion of } \pi\right\}$$

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

Which of the following statements is true with respect to $S$? No reason to be given for the answer.

- $S$ is regular
- $S$ is recursively enumerable
- $S$ is not recursively enumerable
- $S$ is recursive

**(b) **Given that a language $L_1$ is regular and and that the language $L_1 \cup L_2$ is regular, is the language $L_2$ always regular? Prove your answer.

+14 votes

Best answer

0

Sir , 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

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

0

I guess there is something wrong with my answer. Suppose "555" is in decimal expansion of $\pi$ we have to accept 3. Likewise if "555555" is there we have to accept 6. Is this right?

0

sir it is varying ,it is not fixed , now even in the question they haven't mentioned that whether the decimal expansion is finite or infinite , if it is a finite expansion , even within that expansion we will be able to find different length of blocks but yes we can count them and accept using FSA ,but since nothing is mentioned so I I really can't guess anything .

0

I guess it is not asking to find that maximum number.. we have to accept all those I guess and it is for infinite length as it is $\pi$. So, I guess it should be r.e. only.

0

But entire decimal expansion is not known so how will the turing machine halt for the language when the string itself is infinite .

0

:) That's why I guess it should only be r.e. Suppose $\underbrace{55\cdots 5}_{k \text{ times}}$ is there in the decimal expansion TM can eventually know this and accept $k$. If it is not present TM continues waiting.

0

But in the decimal expansion as per the link after some large amount of finite symbols we have successive occurrences of 5's so then TM won't wait as it will find after finite steps k 5's ,so I guess it should be regular only , since we have successive occurrences after finite steps.

0

but 'k' is not necessarily 1 or 2. It can go till any number. Or we have to be sure k > some finite number is not possible.

+1

I am getting no idea for this question now , it is getting quite tricky ,Recursively enumerable seems fine to me .

+12 votes

a) Expansion of Pi. Which is a real number. Real numbers are not COUNTABLE. (We cant have one one correspondence for them where as we can have one one correspondence for integers & quotients hence countable)

Stackoverflow says: a real number r is computable if there exists an algorithm to find its `n`

th digit.

Stackoverflow also says Pi is computable. http://stackoverflow.com/questions/4134282/is-pi-a-turing-computable-number

(If it is, then I do not know how. :D I am not satisfied with the answers)

So if it is computable, then we can find a turing machine machine for finding x block of 5's.

Hence RE. Definitely it will not halt. Hence not Recursive.

Answer is (ii)

P.s: Answer is based on assumptions. Not any proofs. If Pi is computable then it has to be RE & you know it will not halt.

b) L1: (a+b)* (Regular)

L2: a^n b^n (DCFL)

L1 U L2: (a+b)* (Regular)

Hence L2 need not to be regular.

0

I am little bit confused .... if there is a algorithm to compute it ... then it should be recursive ... correct me if i am wrong ...

0

But if we are unable to enumerate all elements of a language, then that language is non- R.E. (Example: diagonalization language). Here, since the expansion of π is infinite so we can't enumerate all digits in its expansion and thus all the elements of the given language S cannot be enumerated. So, shouldn't the answer be (c) i.e. S is non-RE ?

0

@Puja Mishra I am having same doubt. I think it should be recursive. Because by actual definition of computability, it states that* a function f on a certain domain is said to be computable if there exists a TM that computes the value of f for all arguments of its domain*, and

So if it is computable, then we can find a turing machine machine for finding x block of 5's.

Hence RE. Definitely it will not halt. Hence not Recursive.

@Ahwan please confirm where i am going wrong??. " Definitely it will not halt." can you elaborate this line.

0 votes

Answer is B

- A recursively enumerable language is a formal language for which there exists a Turing machine (or other computable function) which will enumerate all valid strings of the language. Note that if the language is infinite, the enumerating algorithm provided can be chosen so that it avoids repetitions, since we can test whether the string produced for number
*n*is "already" produced for a number which is less than*n*. If it already is produced, use the output for input*n+1*instead (recursively), but again, test whether it is "new" Wikipedia

- All categories
- General Aptitude 1.6k
- Engineering Mathematics 7.3k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.4k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 570
- Exam Queries 566
- Tier 1 Placement Questions 23
- Job Queries 70
- Projects 18

48,691 questions

52,776 answers

183,436 comments

68,390 users