CS 220

Home
Assignments
Study Materials

Proof of Undecidability Homework

Let \(EQ_{CFG} = \{\langle G_1,G_2 \rangle | G_1\) and \(G_2\) are CFGs and \(L(G_1) = L(G_2) \}\)

Prove that \(EQ_{CFG}\) is undecidable. Hint: you can use a reduction from the language in theorem 5.13 from the book.