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

摘要

LetAbe a finite, totally ordered alphabet, and let ⪯ be the lexicographic ordering onA*. LetXbe a subset ofA*. Thelanguage of minimal wordsofXis the subset ofXcomposed of the lexicographically minimal word ofXfor each length: Min(X)={x∈X |  ∀w∈X, |w|=|x|⇒x⪯w}. The aim of this paper is to prove that ifLis a context-free language, then the language Min(L) context-free.