The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+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. 

  1. $S$ is regular
  2. $S$ is recursively enumerable
  3. $S$ is not recursively enumerable
  4. $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.

asked in Theory of Computation by Veteran (52k points)
edited by | 1.3k views

3 Answers

+15 votes
Best answer
(b) No. Need not be. Take $L_2 = \{a^nb^n \mid n > 0\}$ and $L_1 =$ all strings over $\{a,b\}$. Now, $L_1  \cup L_2$  is $L_1$  only and is regular but $L_2$ is not regular.
answered by Veteran (406k points)
selected by
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 :
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?
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 .
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.
But entire decimal expansion is not known so how will the turing machine halt for the language when the string itself is infinite .
:) 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.
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.
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.
I am getting no idea for this question now , it is getting quite tricky ,Recursively enumerable seems fine to me .
@radha See the stackoverflow group with lots of eminent profs finding hard to decipher this question. So, if you find such a question in GATE you better leave it or blindly choose regular or r.e.
@Arjun sir       ,   can we say the closure properties are one directional  ?? and use this property in solving the que (b)    ???
+13 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 nth digit.
Stackoverflow also says Pi is computable.
(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.

answered by Boss (11.7k points)
Nice answer ...
I am little bit confused .... if there is a algorithm to compute it ... then it should be recursive ... correct me if i am wrong ...
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 ?

@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 by simplifying our concern only on the result of computation to be either yes or no(i e defining in terms of decidability) we can say that if there exists a TM which gives yes/no for every statement in the domain of the problem, then its decidable. And so it should be recursive.

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 

  1. 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
answered by Active (1.2k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,541 questions
54,094 answers
71,001 users