✦ LIBER ✦

Simulating finite automata with context-free grammars

✍ Scribed by Michael Domaratzki; Giovanni Pighizzini; Jeffrey Shallit

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 78 KB
Volume: 84
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(02)00316-2

No coin nor oath required. For personal study only.

✦ Synopsis

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 states can be simulated by a CNF grammar with O(n 2/3 ) variables. Finally, for larger alphabets we show that there exist languages which can be accepted by an n-state DFA, but which require (n/ log n) variables in any equivalent CNF grammar.

📜 SIMILAR VOLUMES

Characterizing derivation trees of conte

Characterizing derivation trees of context-free grammars through a generalization of finite automata theory

✍ J.W. Thatcher 📂 Article 📅 1967 🏛 Elsevier Science 🌐 English ⚖ 252 KB

The recognizable sets of value trees (pseudoterms) are shown to be exactly projections of sets of derivation trees of (extended) context-free grammars.

Context-free grammars with selective rew

Context-free grammars with selective rewriting

✍ G. Rozenberg; D. Wood 📂 Article 📅 1980 🏛 Springer-Verlag 🌐 English ⚖ 613 KB

Unary Context-Free Grammars and Pushdown

Unary Context-Free Grammars and Pushdown Automata, Descriptional Complexity and Auxiliary Space Lower Bounds

✍ Giovanni Pighizzini; Jeffrey Shallit; Ming-wei Wang 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 240 KB

It is well known that a context-free language defined over a one-letter alphabet is regular. This implies that unary context-free grammars and unary pushdown automata can be transformed into equivalent finite automata. In this paper, we study these transformations from a descriptional complexity poi

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

Context-free and domination grammars and

Context-free and domination grammars and the algorithmic problems connected with them

✍ M. I. Beletskii 📂 Article 📅 1971 🏛 Springer US 🌐 English ⚖ 690 KB

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