Question: Compare recursive and recursively enumerable languages
1

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: Dec 2015,May 2015

ADD COMMENTlink
modified 3.2 years ago  • written 3.2 years ago by gravatar for Pooja Joshi Pooja Joshi740
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'

ADD COMMENTlink
modified 3.2 years ago  • written 3.2 years ago by gravatar for Pooja Joshi Pooja Joshi740
Please log in to add an answer.