0
$\begingroup$

Given a generating grammar, is it possible to reduce it to a context free form, if one exists. One method might seem to be if the context sensitive rules can be reached from higher generating points, in some sense. However, is this an interesting question worth worrying about? Are there practical situations, where there is some benefit in reducing a more complicated language to a context free language?

$\endgroup$
1
$\begingroup$

No. By Greibach's theorem, it is undecidable whether a CSG generates a context-free language.

$\endgroup$

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.