Error detection in formal languages

摘要

The effects that certain classes of errors have on formal languages are considered from the point of view of preservation of languages under error transformations. This approach is an expansion of an article by Hartmanis and Stearnes [9], in which only the finite error case on regular expressions was considered.An automaton that detects that errors have occurred in an input from a given language is merely a recognizer of that language. However, an automaton that determines if errors in the input are bounded in some manner is a recognizer of a larger, errormodified language. It is these latter automata with which we are primarily concerned.An error on a symbol from an alphabet is considered in this paper to be the changing of that symbol to some other symbol from the same alphabet. Thus, errors as defined here are length-preserving substitution errors. We define classes of error transformations by the manner in which errors that occur on a string are bounded. Four classes of error transformations are considered. The first class allows errors up to a predetermined number. The second allows up to a predetermined number of errors per substring of given length. The third bounds the number of errors by a constant fraction of the number of symbols between each error and the start of the string. The fourth bounds the errors by a constant fraction of the length of the string.It is found that the first two classes (called “constant” errors) yield essentially equivalent effects on properties of the automata considered, and that the same is true for the latter two classes (called “expanding” errors). Hopcroft and Ullman in an independent, but earlier work [10] have demonstrated a number of the results shown in this paper. The major new results of this paper are:o1.The detection of expanding errors in regular laguages is normally not possible by finite-state automata, but rather require automata called 1-counters, which are less powerful than pushdown automata. The conditions under which regular languages are not preserved by expanding errors are shown.2.The detection of expanding errors in context-free languages requires deterministic linear-bounded automata in general.3.Left-context-sensitive languages are preserved under constant and the first class of expanding errors, but require linear-bounded automata for the second class of expanding errors.4.Deterministic context-sensitive languages and recursive phrase-structure languages are preserved under both constant and expanding errors.