On Complete Systems and Finite Automata
Arthur T. Pu · IEEE Transactions on Computers · 1972
A production on T* is a rewriting rule σα→σ' for all aϵ T*, where σ, σ' are strings in T* with a' lexicographically earlier than σ. Any finite collection of productions is called a system. This note shows that any system that is consistent, complete, and has the nonprefix property uniquely represents an automaton. This formulation characterizes automata as recognition devices in terms of a set of rewriting rules, similar to the characterizatibn of automata as generating devices by grammars.