TOC Question

Question

Comments

I think you have missed 1 more case when {w| wϵ(a+b+c)*, n_a(w)= $n_c$(w)}.

So finally it becomes  L = {w| wϵ(a+b+c)*, n_a(w)= n_b(w)} ∪ {w| wϵ(a+b+c)*, n_b(w)= n_c(w)} U {w| wϵ(a+b+c)*, n_a(w)= $n_c$(w)}

---

@Hemant

n_a(w)=n_c(w) is not correct, see how,

let string 'a³b⁴c³' (n_a(w)=n_c(w)),.... but it is in original language L, then how could it be in complement(L)

---

Okay. Thank you..!!

Answer 1

1- Halting problem is undecidable (semi -decidable) and hence not even recursive(decidable is recursive). Hence can't be CFL as not recursive.

2- Same as 1. Undecidable.

3- You have to actually count the number of states. As explained in the comment section by @ joshi_nitish it is CFL.

Check this out :https://gatecse.in/grammar-decidable-and-undecidable-problems/ . This might help with the decidable and undecidable problems.

Comments

@sumit chakraborty

emptiness problem is Decidable for CFL, Then why we are not considering here? Can TM accept empty string? 

In TM if we start from starting state as the final state.??

Answer 2

I think C is correct