𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Recursively enumerable languages and van Wijngaarden grammars

✍ Scribed by Jan Van Leeuwen

Publisher
Elsevier Science
Year
1977
Weight
580 KB
Volume
80
Category
Article
ISSN
1385-7258

No coin nor oath required. For personal study only.

✦ Synopsis

We show that each re language can be generated by a minimal deterministic linear contextfree based strict normal VW-grammar.

We also prove that each re language can be generated by a strict normal VW-grammar with at most one metanotion denoting a non-regular contextfree language.

📜 SIMILAR VOLUMES

PC grammar systems with five context-fre
PC grammar systems with five context-free components generate all recursively enumerable languages
✍ Erzsébet Csuhaj-Varjú; Gheorghe Păun; György Vaszil 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 143 KB

Parallel communicating grammar systems (PC grammar systems, in short) are language generating devices consisting of several context-free grammars which work synchronously on their own sentential forms and communicate the generated strings to each other by request. These systems with eleven component