The set of minimal words of a context-free language is context-free

J. Berstel, L. Boasson

IBP-Litp 1995/04: Rapport de Recherche Litp / Litp research reports
21 pages - Janvier/January 1995 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: The set of minimal words of a context-free language is context-free

Résumé : Soit A un alphabet fini totalement ordonné, et soit ¾ l'ordre lexicographique sur A*. Soit X une partie de A*. Le langage des mots minimaux de X est la partie de X constituée, pour chaque longueur, du mot lexicographiquement minimal de X:
Min(X) = {x OE X Ù w OE X, |w| = |x| Þ x ¾w}
Le but de cet article est de prouver que si L est un langage algébrique, alors Min(L) est un langage algébrique.

Abstract : Let A be a finite, totally ordered alphabet, and let ¾ be the lexicographical 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:
Min(X) = {x OE X Ù w OE X, |w| = |x| Þ x ¾w}
The aim of this paper is to prove that if L is a context-free language, then the language Min(L) is context-free.

Publications internes Litp 1995 / Litp research reports 1995