An algorithm for error correction in context-free languages
The task of error correction in various applications of parsing is drawing more and more interest and concern. This paper presents an algorithm that corrects three common spelling errors in a context-free language and then describes an implementation on a digital computer.
The algorithm described initially applies transformations to the original grammar to produce three new grammars. Each new grammar will generate the strings in the original language with one occurrence of an error. Each new grammar is then used to define a pushdown transducer which will recognize a string in the error corrupted language. The output will be a string in the original language along with a special symbol to show where the error correction has occurred.
Thesis74.M545.pdf
3.2 MB
Adobe PDF
50ac26ee67f3ea1fb60f69387ed456ce