345 views

2 Answers

0 votes
0 votes

recognizer of a language is a machine that recognizes that language. A recognizer will halt on strings that belong to the language and it may or may not halt on strings that don't belong to the language. 

Recursive languages are decidable since every Recursive language has a Halting TM. So, if a language is Turing decidable, it is Turing recognizable. 

0 votes
0 votes

REC (Turing decidable) :

  1.       A language is REC if there exists a TM that

                                   accepts all those strings that ∈ language

                                   rejects all those strings that ∉  language

by accept we mean that TM would halt in Final state.

by reject we mean that TM would halt in Non-final state.

In other words Any language for which you can write a program and get a positive or negative reply from your computer , i.e technically speaking , you can design a TM  and ensures that it always accepts or rejects. Then this language is REC.

2. As for REC languages TM would always 'halt' so in another words we can say if some problem is solvable by computer (mean algo exists) then this language is  REC.

RE(Turing recognizable / Semidecidable):

         A language is RE iff any

                              w ∈ lang => TM halts in a Final state.

                              w∉ lang  => TM halts in Non-final state or loops forever(hang).

in another words If there exists a TM that accepts every string that ∈ lang and doesn't accept strings that are not in the language (Strings that are not in languauge may be rejected or may cause the TM to go into an infinite loop).

 Hope you know every REC is RE but vice-versa is not true.

Related questions

0 votes
0 votes
1 answer
2
mrinmoyh asked Dec 27, 2018
291 views
L1 $\cap$ L2 = $\phi$ This problem is decidable or undecidable in case of CSL, REL, & REnL ????
0 votes
0 votes
0 answers
3
newdreamz a1-z0 asked Dec 22, 2018
451 views
L={ <M | ‘M’ IS A TURING MACHINE AND ‘M’ COMPUTES THE PRODUCT OF TWO NUMBERS }here what can we say about ‘L’?
2 votes
2 votes
1 answer
4
kumar.dilip asked Dec 13, 2018
461 views
If L is CFL then $\bar{L}$ is Recursive. ( True/False)If L is CFL then $\bar{L}$ is RE. (True/Flase).