𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The Set of Minimal Words of a Context-free Language is Context-free

✍ Scribed by Jean Berstel; L. Boasson

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
360 KB
Volume
55
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

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-free language, then the language Min(L) context-free. ] 1997 Academic Press

1. NOTATIONS

A context-free grammar G=(V, S, P) over an alphabet A is composed of finite alphabet V of variables or nonterminals disjoint from A, a disinguished nonterminal S called the axiom and a finite set P/V_(V _ A)* of productions or derivation rules. Letters in A are called terminal letters.

πŸ“œ SIMILAR VOLUMES

Hippocampal context processing is critic
Hippocampal context processing is critical for interference free recall of odor memories in rats
✍ Dan A. Butterly; Maurice A. Petroccione; David M. Smith πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 431 KB

## Abstract Interference is a critical problem for memory systems and a primary cause of retrieval failure. One strategy for minimizing interference is to associate the items to be remembered with the context in which they were learned. For example, human subjects who learn two lists of words in se

The equivalence of Nonassociative Lambek
The equivalence of Nonassociative Lambek Categorial Grammars and Context-Free Grammars
✍ Maciej Kandulski πŸ“‚ Article πŸ“… 1988 πŸ› John Wiley and Sons 🌐 English βš– 699 KB

Besides this introduction the paper contains four sections. I n section 1 we describe three equivalent axiomatizations of NLP. the third one playing important role in what follows. I n section 2 we deal with a system AC: (the Ajdukiewicz calculus with product) and prove the equivalence of AC-grammar