๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A note on the density of inherently ambiguous context-free languages

โœ Scribed by R. Kemp

Publisher
Springer-Verlag
Year
1980
Tongue
English
Weight
139 KB
Volume
14
Category
Article
ISSN
0001-5903

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A note on context-free languages
A note on context-free languages
โœ R.F.C. Walters ๐Ÿ“‚ Article ๐Ÿ“… 1989 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 296 KB
On regularity of context-free languages
On regularity of context-free languages
โœ A. Ehrenfeucht; D. Haussler; G. Rozenberg ๐Ÿ“‚ Article ๐Ÿ“… 1983 ๐Ÿ› Elsevier Science โš– 112 KB
On the context-free production complexit
On the context-free production complexity of finite languages
โœ Zsolt Tuza ๐Ÿ“‚ Article ๐Ÿ“… 1987 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 696 KB

The following problem is investigated. Let L be a given finite language, LcL,= {ub: I ~o,bsn, of/~}. Determine the minimal natural number c(L) such that L can be generated by c(L) context-free productions. Among others, max c(L) = O(n'/log n) is proved, and languages satisfying c(L) = IL) are charac

The Set of Minimal Words of a Context-fr
The Set of Minimal Words of a Context-free Language is Context-free
โœ Jean Berstel; L. Boasson ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 360 KB

Let A be a finite, totally ordered alphabet, and let P be the lexicographic ordering on A\*. Let X be a subset of A\*. The language of minimal words of X is the subset of X composed of the lexicographically minimal word of X for each length: The aim of this paper is to prove that if L is a context-