0
$\begingroup$

We know that every $CFL$ has infinite configuration space. Due to this equality problem is undecidable. But why finiteness property is decidable inspite having infinite configuration space?

$\endgroup$

1 Answer 1

2
$\begingroup$

The language generated by a grammar with no useless symbols/productions is finite if and only if there is no non-terminal $A$ so that $A \Rightarrow^* \alpha A \beta$. This is easy to check.

$\endgroup$
3
  • $\begingroup$ $ \Rightarrow^*$ means arrow $ \Rightarrow$? $\endgroup$
    – Punia
    Oct 12, 2021 at 22:49
  • $\begingroup$ But why equality isn't decidable in same logic? $\endgroup$
    – Punia
    Oct 12, 2021 at 22:56
  • 1
    $\begingroup$ @Net, if at least one of the languages is finite, it is possible. How would you check in case both languages are infinite? $\endgroup$
    – vonbrand
    Oct 13, 2021 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.