search
Log In
2 votes
59 views
consider a tùring mchine which accepts the empty language i.e TM = { (M) | M accepts empty language} the complement of the language that is generated by Turing machine is?
in Theory of Computation 59 views
1
You say Language of turing machine is Phi , so complement of it is sigma*.

1 Answer

0 votes
L = { (M) | M accepts empty language}

$L^c$ = { (M) | M accepts non-empty language}

L is NOT RE, and $L^c$ is RE.

Related questions

4 votes
2 answers
2
491 views
Consider the following statements: $S_1:\{(a^n)^m|n\leq m\geq0\}$ $S_2:\{a^nb^n|n\geq 1\} \cup \{a^nb^m|n \geq1,m \geq 1\} $ Which of the following is regular? $S_1$ only $S_2$ only Both Neither of the above
asked May 26, 2019 in Theory of Computation Hirak 491 views
2 votes
3 answers
3
419 views
How many $2$ state DFA’s with the designated initial state can be constructed over the alphabet over the alphabet $\sum = \{a, b\}$ that accept universal language? $4$ $16$ $20$ $24$
asked May 22, 2019 in Theory of Computation Hirak 419 views
0 votes
1 answer
4
142 views
Min number of states in equivalent DFA ______________ will it be 4 or 5 ??
asked May 2, 2019 in Theory of Computation srestha 142 views
...