Errors in Regular Languages
- 1 June 1974
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-23 (6) , 597-602
- https://doi.org/10.1109/T-C.1974.224000
Abstract
Random occurrences of three types of errors in the input to a finite automaton are considered: an α error is a deletion of one symbol from the input string; a β error is an insertion of one extra symbol; and a δ error is a change of one symbol into another symbol. A method using operators for determining regular expressions defining error-corrupted strings is developed and is employed in the construction of a finite automaton, the outputs of which are stochastically generated by Bayes' Rule (with certain approximations) to take into account the frequencies with which strings appear as inputs and the probabilities of errors.Keywords
This publication has 7 references indexed in Scilit:
- Estimation, Prediction, and Smoothing in Discrete Parameter SystemsIEEE Transactions on Computers, 1970
- Error detection in formal languagesJournal of Computer and System Sciences, 1970
- On the error correcting capacity of finite automataInformation and Control, 1965
- Derivatives of Regular ExpressionsJournal of the ACM, 1964
- Input-Error-Limiting AutomataJournal of the ACM, 1964
- A technique for computer detection and correction of spelling errorsCommunications of the ACM, 1964
- Regularity preserving modifications of regular expressionsInformation and Control, 1963