Transposition errors in context-free languages

This article examines the problem of context-free languages that include strings containing transposition errors. The precise construction of a transposition error-correcting algorithm is given. Error detection and correction has been analyzed by others. Context-free grammar transformations to allow for the derivation of strings containing replacement, deletion, and insertion errors have been defined. This article presents an algorithm that, when given a Chomsky Normal Form context-free grammar G, constructs a Chomsky Normal Form context-free grammar, G_T, to derive strings that contain transposition errors. The strings in the new language are one transposition error away from those in the original language, L(G). G_T can be used to parse incorrect strings and to correct them. This approach also allows for the detection, classification, and correction of transposition errors occurring in the syntactic description of patterns. The number of new productions in G_T is related by a small polynomial to the number of productions in G.