Markers and Deterministic Acceptors for Non-Deterministic Languages
Helmut Jürgensen · Journal of automata, languages and combinatorics · 2009
We investigate the question as to how the intuitive structure of words in a formal language is reflected by the structure of the reduced deterministic acceptor for that language. Markers in words are known to facilitate the understanding of structure and the design ofword recognition algorithms. Explicit markers, that is, special symbols,are rather artificial. To avoid such special symbols, but to benefit from the effect of markers we consider implicit markers -- special words which provide segmentation information about input words. We propose a formal definition of markers based on the notion of relativized solid codes and indicate how this concept can assist in the understanding of the structure of words and the construction of acceptors via automaton extensions.