Approximate Recognition of Non-regular Languages by Finite Automata

Eisman, G. and Ravikumar, B.

Approximate computation is a central concept in algorithms and computation theory. Our notion of approximationis that the algorithm perform correctly on most of the inputs. We propose some finite automata models to study the question of how well a finite automaton can approximately recognize a nonregular language. On the one hand, we show that there are natural probelsm for which a DFA can correctly solve almost all the instances. The design of theee DFA's leads to a linear time randomized algorithm for approximate integer multiplication. On the other hand, we show that some languages (such as Lmajority = {x � (0 + 1)* ? x has more 1's than 0's}) can't be approximated by any regular language in a strong sense. We also present results comparing different models of approximation.

Cite as: Eisman, G. and Ravikumar, B. (2005). Approximate Recognition of Non-regular Languages by Finite Automata. In Proc. Twenty-Eighth Australasian Computer Science Conference (ACSC2005), Newcastle, Australia. CRPIT, 38. Estivill-Castro, V., Ed. ACS. 219-228.

(from crpit.com) (local if available)