if ϕ was not present then it would be RE right ?

The Gateway to Computer Science Excellence

+6 votes

Best answer

1. Using dovetailing: (intuitive and best)

Property : Acceptance of a finite language $\begin{align} L(M) = \phi \cup \left \{ 00 \right \}\cup \left \{ 11 \right \}\cup \left \{ 00,11 \right \} \\ \end{align}$.

For checking any $M$ belonging to the property, we have to use an UTM and check $\langle M,w \rangle$ pairs , feeding $w$ in a dovetailing (zigzag) manner.

We have to confirm the acceptance of some strings (as shown above) and non-acceptance of all other strings.

"non-acceptance of all other strings", this requirement is hard and TM may go infinite loop.

So we can not even check $M$ for although $M$ may belong to property.

$\Rightarrow$ $L1$ is non-computable or NOT-RE.

2. Using Rice Theorem.

$$\begin{align} T_{1_{yes}} &= \phi = \left \{ \right \} \\ T_{2_{yes}} &= \left \{ 00 \right \}

\\ T_{3_{yes}} &= \left \{ 11 \right \}

\\ T_{4_{yes}}

&= \left \{ 11,00 \right \} \\ \end{align}$$

Whenever $\phi \in \text{Property SET}$ then corresponding property language is NOT-RE.

Or, Some supersets of any $T_{yes}$ does not satisfy the given property. Hence NOT RE

Property : Acceptance of a finite language $\begin{align} L(M) = \phi \cup \left \{ 00 \right \}\cup \left \{ 11 \right \}\cup \left \{ 00,11 \right \} \\ \end{align}$.

For checking any $M$ belonging to the property, we have to use an UTM and check $\langle M,w \rangle$ pairs , feeding $w$ in a dovetailing (zigzag) manner.

We have to confirm the acceptance of some strings (as shown above) and non-acceptance of all other strings.

"non-acceptance of all other strings", this requirement is hard and TM may go infinite loop.

So we can not even check $M$ for although $M$ may belong to property.

$\Rightarrow$ $L1$ is non-computable or NOT-RE.

2. Using Rice Theorem.

$$\begin{align} T_{1_{yes}} &= \phi = \left \{ \right \} \\ T_{2_{yes}} &= \left \{ 00 \right \}

\\ T_{3_{yes}} &= \left \{ 11 \right \}

\\ T_{4_{yes}}

&= \left \{ 11,00 \right \} \\ \end{align}$$

Whenever $\phi \in \text{Property SET}$ then corresponding property language is NOT-RE.

Or, Some supersets of any $T_{yes}$ does not satisfy the given property. Hence NOT RE

0

bro.. intutively speaking since if a language accepts 00 or 11 or both (not talking about empty string) then it will yes and if it accepts any other string then we can stop and say no. only condition on which we can't say no is when it doesn't accept anything but since it can say yes it becomes RE ? thanks for the link but i am not able to understand rice theorem therefore working intutively.

+2 votes

not even RE.

i should print all the turing machines which accepts 00 or 11 or both and i should make sure that it doesnt accept any string other than 00 and 11. if a particular turing machine loops infinitely on a string other than 00 and 11.. we will not be able to say "yes" for the turing machines which belong to the language.

i should print all the turing machines which accepts 00 or 11 or both and i should make sure that it doesnt accept any string other than 00 and 11. if a particular turing machine loops infinitely on a string other than 00 and 11.. we will not be able to say "yes" for the turing machines which belong to the language.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,741 questions

57,253 answers

198,063 comments

104,700 users