286 views
0 votes
0 votes

Can anyone explain?

2 Answers

0 votes
0 votes

Theorem: A language is decidable iff both it and its complement are recognizable.

Proof: Surely, a decidable language is recognizable. Moreover, if a language is decidable, then so is its complement, and hence that complement is recognizable.
Now suppose a language L and its complement are recognizable. Let A be a recognizer for L, and B for its complement. A decision method for L is obtained by running A and B in parallel on a given input string. In case A accepts the string, it is accepted as a member of L, and in case B accepts it, it is rejected as member of L. One of these outcomes will occur within a finite amount of time.

 

src:- http://kilby.stanford.edu/~rvg/154/handouts/decidability.html

0 votes
0 votes
ok , let me explain - say  (a <= 3) and (a>3) what is the value of  a ?........ ofcourse  a belongs to real number .

taking the same analogy if a tm  ( here P ) accepts a particular type of language and  other tm (p") rejects the same type of language then what is the union of the above languages , offcourse complete language  and a complete language is regular. now if you could remember then Regular language is decidable (i.e there exist an algorithm  or TM that decides whether  a language is regular or not )

 

coming to second point that whether there exist a TM that accepts its own encoding is undecidable

No related questions found