2,704 views
1 votes
1 votes
what is the difference between recursive, RE and REL language?? confuse...

2 Answers

Best answer
1 votes
1 votes

A recursive language is a language for which  there exists a total turing machine which accepts the language and halts on every input string w. Either it will accept the string and halt, or reject the string and halt. It is also called decidable language.

L= {anbncn|n>=1} is recursive because we can construct a turing machine which will move to final state if the string is of the form anbncn else move to non-final state. So the TM will always halt in this case.

A recursively enumerable language is a language for which  there exists a total turing machine which accepts it. It may or may not halt for input strings w. if it accepts a string it will halt (enter into final state) and if it does not accept a string it may or may not enter reject state(will loop infinitely ) . It is also known as semi-decidable or partially decidable or turing recognizable  or turing acceptable language.

The halting problem is recursively enumerable but not recursive. we can run the Turing Machine and accept if the machine halts, hence it is recursively enumerable.  

selected by
1 votes
1 votes

RE or REL(recursive enumerable languages) or Turing-recognizable are same.

recursive  or decider or Turing-decider are same .

when we start a Turing machine on an input, three outcomes are possible. That the Turing machine may ---

  • Accept the input 
  • Reject the input
  • Loop (by loop mean that the machine simply does not halt. Looping may entail any simple or complex behavior that never leads to a halting state.)

RECURSIVE LANGUAGE:

 when a Turing machine halts on all inputs (i.e. Accept or Reject the inputs) , never loops , such Turing machines are called  decider or Turing-decider. And that language is called recursive or Turing decidable

RECURSIVE ENUMERABLE LANGUAGE:

when a Turing machine may halt(i.e. Accept or Reject the inputs) or may not halt (means Turing machine go into loop), such Turing machines are called  Turing-recognizer. And that language is called recursive-enumerable or Turing-recognizable.

   * But sometimes it is difficult to distinguish that a Turing machine is looping or taking a long time for an input.(i.e.   UNDECIDABILITY)

  * Every recursive language is recursive enumerable.

in other words, 

a language L is said to be decidable if L is Turing-recognizable and L' is also Turing-recognizable.

edited by

Related questions

0 votes
0 votes
0 answers
4
sripo asked Jan 5, 2019
523 views
As per the given solution,B should be the correct answer right why is D given as the correct answer as the machine accepts atleast one b.