Peter Linz Exercise 11.1

Question

If L is recursive, is it necessarily true that L⁺ is also recursive?

Comments

Recursive languages are closed under Kleene's Closure. L* is Recursive, i think L+ is also recursive.

Answer 1

Recursive languages are closed under the following operations. That is, if L and P are two recursive languages, then the following languages are recursive as well : 

• The concatenation 
• The union 
• The intersection 
• The complement of 
• The Kleene closure or Kleene star L*
• The Kleene Plus L⁺   (Which You were asking)
• The set difference 

The last property follows from the fact that the set difference can be expressed in terms of intersection and complement.

"Every Language type which is closed under Kleene star, is also closed under Kleene Plus. 

Every Language type which is NOT closed under Kleene star, is also NOT closed under Kleene Plus. "