Recursively Enumeration and Recursive Language

Language accepted by TM are called as Recursively enumerable language.The context free langauage are subset of recursively enumeration language,Just keep in mind that we are not considering the language having epsilon.




Theorem1: A Langauge is recursive if and only if it can be effectively enumerated in lexicographic order(i.e alphabet order). The String of a language L can be effectively enumerated mean,a turing machine exist for a language L which will enumarate all valid string of the language. Theorem2: If a language L and its complement L' are both recursively enumerable then both language are recursive .If L is recursive then L' is also recursive and consequently both are recursively enumerable.


Recursively Enumerable (RE)language are closed under following operation:


Suppose L and P are two RE language then these are recursively enumerable :

1) L of L

2) Concatenation L.P

3)Union L∪P

4) Intersection L∩P



      Recursively enum language are not closed under

1) Set difference

2) Complementation