𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A decision method for Parikh slenderness of context-free languages

✍ Scribed by Juha Honkala

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
218 KB
Volume
73
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

In a recent paper we introduced Parikh slender languages as a generalization of slender languages defined and studied by AndraSiu, Dassow, Pgun and Salomaa. Results concerning Pa&h slender languages can be applied in ambiguity proofs of context-free languages. In this paper an algorithm is presented for deciding whether or not a given context-free language is Parikh slender.

📜 SIMILAR VOLUMES

Chomsky-Schützenberger Type Characteriza
Chomsky-Schützenberger Type Characterizations of Poly-Slender and Parikh Slender Context-Free Languages
✍ Masami Ito; Carlos Martín-Vide; Victor Mitrana 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 272 KB

In this paper we propose a Chomsky-Schützenberger type characterization ofpoly-slender context-free languages, as the homomorphical image of an intersection of a Dyck language and a ´¾ • ½ µ -poly-slender regular language. A stronger result is provided, namely the homomorphism and the Dyck language

Comparisons of Parikh's condition to oth
Comparisons of Parikh's condition to other conditions for context-free languages
✍ G. Ramos-Jiménez; J. López-Muñoz; R. Morales-Bueno 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 792 KB

In this paper we first compare Parikh's condition to various pumping conditions ~ Bar-Hillel's pumping lemma, Ogden's condition and Bader-Moura's condition; secondly, to interchange condition; and finally, to Sokolowski's and Grant"s conditions. In order to carry out these comparisons we present som

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.