Minimal strings in a regular language with respect to a partial order on the alphabet (Q807021): Difference between revisions

Let L be a regular language over an alphabet \(\Sigma\) with partial order ``\(\leq ''\). It is proved that the language of minimal strings in L, with respect to ``\(\leq ''\), is a regular language. The marked finite state machine is introduced which is a finite automaton with one or more marked transitions. The language \(L_ m(M)\) accepted by the marked machine M is the set of strings which leads M from its start state to one of the final states by passing at least through one marked transition. It is proved that \(L_ m(M)\) is regular for a deterministic or nondeterministic marked finite state-machine. For proving the main theorem: ``Ḻ\(=\{x:\) x is minimal in \(L\}\) is regular if L is regular'', a marked finite-state machine \(M''\) such that \(L_ m(M'')=L''\), where \(L''=\{y:\) \(y>x\) for some \(x\in L\}\), is constructed. Then, from Ḻ\(=L-L''\), it follows that Ḻ is regular if \(L''\) is regular. Some problems concerning with the number of states in the minimum deterministic marked machine are solved. Finally, two open problems are given.