Question: Here is an incorrect proof that E DFA = { D:D is a DFA, and L ( D ) = } E DFA = {

Here is an incorrect proof that E DFA={D:D is a DFA, and L(D)=}E DFA ={D:D is a DFA, and L(D)=} is decidable.
proof: Define a TM M1 as follows:On input DD:For all w{0,1}w{0,1} : simulate DD on ww. If DD accepts ww, that means L(D)L(D)=, so reject.If we find no strings that DD accepts, then L(D)=L(D)=, so accept.
This Turin Machine M1 accepts inputs DD with L(D)=L(D)= and rejects inputs DD with L(D)L(D)=, so this machine decides E DFA E DFA
Question 1
The Turing Machine M 1 M 1 does prove something about E DFA E DFA . What does it prove?
Choice 1 of 3: E DFA E DFA is recognizable
Choice 2 of 3: E DFA E DFA is co-recognizable
Choice 3 of 3: E DFA E DFA is not decidable
Question 2
Is E DFA E DFA decidable?
Choice 1 of 2: Yes
Choice 2 of 2: No

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!