Complement of a recursive language

Question

Given a TM M, complement of L(M) is context-free. True/False?

Comments

I need to re-look over it now :)

---

Sorry, I mistook the statement. The question should be FALSE.

---

:/

Answer 1

"There exists a Non-Context-Free Recursive Language whose complement is Context Free."

We know that CFLs are not closed under Complement.

This implies that there exists a CFL, $L$ such that $\widetilde{L}$ is not Context Free.

Since every Context Free Language is also a Recursive Language, $L$ must be a Recursive Language.

Since Recursive Languages are closed under Complement, $\widetilde{L}$ must be a Recursive Language.

So $\widetilde{L}$ is a Non-Context-Free Recursive Language whose complement is a Context Free Language.

---

"There exists a Non-Context-Free Recursive language whose complement is not is also not Context Free."

Consider the following language $A$, 

$A =\left \{ a^{p} \mid \text{p is a prime number} \right \}$.

It is known that $A$ is a Non-Context-Free Recursive language.

but checking 

1) If a number is prime &

2)If it is a non-prime,

both requires division.

So I guess here both $A$ and $\widetilde{A}$ are Non-Context-Free Recursive Languages.

So this part should also be true.

Hence, I guess the statement  

"Complement of a Recursive but not Context Free Language is Context Free."

should neither be a Tautology nor a Contradiction, it should be a Contingency.

 

Comments

Everything is correct except the guess

"So I guess here both"

The statement is counter intuitive but you know that complement of language for "ww" is context-free. We cannot recognize prime number with CFL, but can we recognize non-prime numbers with a CFL? 

---

Sir, I made an effort for making that guess logical by mentioning about divisibility. :)

I'll try to do that more rigorously using Pumping Lemma.

---

yes, you can give that. You should get one..

---

A CSL is recursive but not CFL,its complement is CSL and not CFL because CSL are closed under complementation then how above statement is true sir ?

---

It is not true. I mistook the statement.

---

what is the correct approach to do it ?

---

Giving  counter example would do. We have to take a non-CFL but recursive language and show that its complement is not CFL. Guess pumping lemma is the only standard way.

---

L={$a^{n^2},n \geq 1$ }  will works ?

---

yes, it works for L and for L' also it works.

---

:)

---

"A unary language is Context Free if and only if it is Regular."

This fact is based on Parikh's Theorem.

Clearly $L$ is not regular & hence its compliment can't be Regular as regular sets are closed under complement.

So if $\widetilde{L}$ can't be regular it can't be Context Free using the same fact.

Hence both $L$ and $\widetilde{L}$ are non-context-free recursive languages.

http://cs.stackexchange.com/questions/51671/pumping-lemma-for-l-left-ac-mid-textc-is-a-composite-number-right

---

yes