1
Compare recursive and recursively enumerable languages

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: Dec 2015,May 2015

1  upvotes
1

Recursive Language:

Let L be a language over an input and if TM 'T' (Turing machine T) excepts every woed in L and rejects every word of L' it is called as recursive language.

Example:

  1. String ends with '101'

  2. Number of 'a'= number of 'b'

    Accept(T) = L

    Reject(T) = L'

    Loop(T) = ϕϕ

    ϕ = nullϕ = null

Recursive enumeration language:

Let L be a langauage over an input, and if TM 'T' excepts every word of L and rejects or loops every word in L' then it is called recursive enumeration language.

Example:

$a^nb^n$

Accept(T) = L

Reject(T) + Loop(T) = L'

1  upvotes
Please log in to add an answer.

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.

Search

Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More