0
$\begingroup$

Given set of grammar rules, how to find if they correspond to Context-free or unrestricted?

Just for Understanding (don't solve the below one), eg:

\begin{align} S &\rightarrow B/A, \\ 1B &\rightarrow 111B, \\ 1A0 &\rightarrow 00 \end{align}

$\endgroup$
  • $\begingroup$ Since it is undecidable to check if a set of grammar rues is context-free or not, there is no algorithm to accomplish the task. That is, it will forever be an art or research to understand or find whether they are context-free or not, although we might increase our heuristic indefinitely. $\endgroup$ – Apass.Jack Dec 20 '18 at 0:23
  • $\begingroup$ @vamsikrishna Is your question about whether a set of rules qualifies syntactically as valid CFG rules or whether they are equivalent to a CFG? (In the latter case, refer to Apass.Jack's comment.) $\endgroup$ – dkaeae Dec 20 '18 at 8:28
1
$\begingroup$

It is undecidable to determine whether the language generated by a given grammar has a context-free grammar.

However, if you are simply asking whether a grammar itself is context-free, look no further than the left hand side of each production. A grammar is context free iff the left hand side of each production is a single non-terminal.

$\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.