𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Self-embedded context-free grammars with regular counterparts

✍ Scribed by Stefan Andrei; Wei-Ngan Chin; SalvadorValerio Cavadini

Publisher
Springer-Verlag
Year
2004
Tongue
English
Weight
191 KB
Volume
40
Category
Article
ISSN
0001-5903

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Simulating finite automata with context-
Simulating finite automata with context-free grammars
✍ Michael Domaratzki; Giovanni Pighizzini; Jeffrey Shallit πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 78 KB

We consider simulating finite automata (both deterministic and nondeterministic) with context-free grammars in Chomsky normal form (CNF). We show that any unary DFA with n states can be simulated by a CNF grammar with O(n 1/3 ) variables, and this bound is tight. We show that any unary NFA with n st

Homogeneous grammars with a reduced numb
Homogeneous grammars with a reduced number of non-context-free productions
✍ A. Meduna; D. KolΓ‘Ε™ πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 70 KB

A homogeneous production has its left-hand side formed by a non-empty string of identical nonterminals. A phrase-structure grammar is homogeneous if each of its productions is homogeneous. The present paper discusses the reduction of homogeneous grammars with respect to the number of non-context-fre

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