The undecidability of form equivalence for context-free and E0L forms

AbstractThis paper studies the decidability status of various equivalence problems in form theory. Most of our discussions concern the notion of a language form. We compare the form equivalence problem between language forms with the ordinary equivalence problem between languages. However, the main results deal with L forms and grammar forms under strict interpretations. We prove that the form equivalence problem is undecidable for (a) context-free grammar forms, and (b) E0L forms. The proofs of these results are based on our investigations concerning language forms