recategorized by
5,344 views
28 votes
28 votes
  1. 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
  1. Given that a language $L_1$ is regular and that the language $L_1 \cup L_2$ is regular, is the language $L_2$ always regular? Prove your answer.
recategorized by

4 Answers

Best answer
25 votes
25 votes
  1. 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.
edited by
24 votes
24 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. 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 votes
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
0 votes
0 votes

@Arjun 

sir...we know expansion of π never ends..

now it may be true that π is computable as we can find its nth digit..within n steps of computation..

but here what we need to do is make a T.M. and give input string as 3.141592....

but in toc we consider only finite length input strings .

but here input itself is infinite length..

even if it has a x-block of 5's we don't know how far .may be infinitely distance away..

anyway...its a infinite string as input. which is not the convention..

so shouldn't it be a NON-R.E. language..???

Related questions

3 votes
3 votes
1 answer
1
gatecse asked May 3, 2021
2,324 views
State whether the following statements are True or False with reasons for your answer:A two pass assembler uses its machine opcode table in the first pass of assembly.
5 votes
5 votes
1 answer
2
gatecse asked May 3, 2021
1,278 views
State whether the following statements are True or False with reasons for your answerA symbol declared as ‘external’ in an assembly language program is assigned an ad...
5 votes
5 votes
5 answers
3
gatecse asked May 2, 2021
3,415 views
For a $B^+$ - tree of order $d$ with $n$ leaf nodes, the number of nodes accessed during a search is $O(\_)$.
34 votes
34 votes
4 answers
4
Kathleen asked Oct 5, 2014
19,575 views
Consider the resource allocation graph in the figure.Find if the system is in a deadlock stateOtherwise, find a safe sequence