𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The unsolvability of the equality problem for sentential forms of context-free grammars

✍ Scribed by Meera Blattner

Publisher
Elsevier Science
Year
1973
Tongue
English
Weight
258 KB
Volume
7
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

The equivalence problem for nondeterministic e-free generalized machines is known to be undecidable. It is shown here that the equivalence problem for these machines can be reduced to the equality problem of the sentential forms of a particular type of linear context-free grammars with a center-marker. Three results which follow are:

(i) The equality problem for sentential forms of c-finite grammars is unsolvable, and therefore the equality problem for the sentential forms of context-free grammars is unsolvable.

(ii) The equality problem for sentential forms of bounded context-free grammars is unsolvable. (iii) The equality problem for OL-languages is unsolvable.

πŸ“œ SIMILAR VOLUMES

The equivalence of Nonassociative Lambek
The equivalence of Nonassociative Lambek Categorial Grammars and Context-Free Grammars
✍ Maciej Kandulski πŸ“‚ Article πŸ“… 1988 πŸ› John Wiley and Sons 🌐 English βš– 699 KB

Besides this introduction the paper contains four sections. I n section 1 we describe three equivalent axiomatizations of NLP. the third one playing important role in what follows. I n section 2 we deal with a system AC: (the Ajdukiewicz calculus with product) and prove the equivalence of AC-grammar

A method for the inference of non-recurs
A method for the inference of non-recursive context-free grammars
✍ C. Chirathamjaree; Martin H. Ackroyd πŸ“‚ Article πŸ“… 1980 πŸ› Elsevier Science βš– 438 KB

A practical method is presented for the automatic generation of a non-recursive context-free grammar (cfg) from a set of strings that the cfg is required to be capable of producing. The method is efficient in computing time by comparison with enumerative methods.