0
$\begingroup$
  • Given any Context-Free-Grammar, $G$, and another in Chomsky Normal Form, $G_c$, how can we check if both $G$ and $G_c$ generate the same language?

One of the trivial ways I know of is to convert $G$ into a CNF form. which motivates my second question,

  • Can two different Context-Free-Grammars in CNF, $G_c$ and $G_c^\prime$, generate the same language? (I would appreciate a proof of it)
$\endgroup$
  • 2
    $\begingroup$ Equivalence of CFGs is undecidable. $\endgroup$ – G. Bach Sep 22 '13 at 15:08
4
$\begingroup$

Chomsky normal forms are not unique. If they were, we'd have an algorithm for deciding whether two CF grammars are equal. But equivalence of CF grammars is undecidable.

$\endgroup$
1
$\begingroup$

Compare $$\begin{align}S &\to AB \\ B &\to BB \\ A &\to a \\ B &\to b\end{align}$$ With $$\begin{align}S &\to AB \\ A &\to AB \\ A &\to a \\ B &\to b \end{align}$$ By what comparison would these grammars be equal?

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