Decidability Question

Question

a) language accepted by a CFG(Context free grammar) is nonempty.

is it D or UD?

Comments

non empty means L(G) satisfies $\Sigma ^{*}$

and $\Sigma ^{*}$ is a regular language. So, it satisfy by CFL too

---

no ,no i don't mean this , it's irrelevant from what i said.

i said you're asking decidability of 'non emptiness of CFL'

i answered it in a general way like

We know emptiness for CFL is decidable and non-emptiness is just complement of this problem.

and complement of some decidable problem would also be decidable.

if you can design algorithm for some problem P there also exists an algorithm for complement of P.

---

srestha , regularity of 'Non emptiness' is playing what role here?

i know complement of ∅ is ∑^*  , but i answered it in general sense.

explain your second line

Σ∗ is a regular language. So, it satisfy by CFL too

Answer 1

First consider this problem

Given a CFG G, does L(G) is $\phi$???

This problem is decidable, i.e. we have an algorithm to find whether L(G) is empty or not.

How?

Just check whether $S$ (starting symbol of the grammar) is useless or not. If it is useless then it means that it never generates a string, or we can say that it never terminates to a string of terminals. If $S$ is useless, it signifies that L(G) is empty. And if it is useful, then it means $S$ is not empty.

So, we have an algorithm to check if L(G) is not empty. Hence given a CFG G, is L(G) not empty? -  is decidable.

https://cseweb.ucsd.edu/classes/fa01/cse105_B/lec15seq.pdf

https://drona.csa.iisc.ernet.in/~deepakd/atc-2011/tm-cfl-undecidable.pdf

Comments

Awesome thanks! @Rishabh Gupta 2

Answer 2

its DECIDABLE

because if we perform operation like eliminating epsilon,UNIT productions ,UNREACHABLE productions,from the grammer

and finally after  doing this stuff  if we find that START SYMBOL was  UNREACHABLE  then we can say that its is DECIDABLE