On fault tolerance of syntax

AbstractIn this paper we formulate the problem, and start an investigation of the complexity of recognizing fault tolerance of syntax, or in other words, of formal language. The research on this problem is motivated by the growing interest to methods of estimation of quality of software systems – a user language is a part of such systems, and its reliability towards syntactic errors is a feature of its quality. We analyse the computational complexity of recognizing one type of such fault tolerance towards a fixed number of errors: a language is fault-tolerant iff any set of replacements of characters within the fixed number in any string in the language produces a string not in the language; a grammar defining the language produces a string not in the language; a grammar defining the language (the syntax) is supposed to be given as input. The property of this kind of fault tolerance is shown to be algorithmically undecidable even for context-free languages. But for nondeterministic finite-automaton languages it is shown to be recognizable in time polynomial in the size of the automaton representing an input language and exponential in the number of errors. In the concluding part of the paper wider views on the problem of fault tolerance of syntax are briefly discussed