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

The finite power property for context-free languages

โœ Scribed by Charles E. Hughes; Stanley M. Selkow

Publisher
Elsevier Science
Year
1981
Tongue
English
Weight
280 KB
Volume
15
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Polynomial Size Test Sets For Context-Fr
Polynomial Size Test Sets For Context-Free Languages
โœ J. Karhumaki; W. Plandowski; W. Rytter ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 648 KB

We prove that each context-free language possesses a test set of size \(O\left(m^{6}\right)\), where \(m\) is the number of productions in a grammar-producing the language. A context-free grammar generating the test set can be found in polynomial time by a sequential algorithm. It improves the doubl

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-