A Bridging Model for Regular Languages
摘要
The constructive proofs of the equivalence of computing models previously have relied on disparate algorithmic methods. These methods are used to link different models in such a manner that road maps have been needed to keep things straight. We give much easier proofs by simplifying the algorithms for regular languages. The simplification is due to two ideas. The first is to use a bridging model that uses a representation that is simultaneously a regular grammar and a regular expression. We can move smoothly between these extremes. Second, we also use \(\epsilon \) -free forms to lead to simplifications. Positive regular expressions and positive regular grammars are defined. We show that we can switch between normal and positive forms at any time. Further, we emphasize the primacy of nondeterministic models by showing that regular grammars provide a natural way to segue into determinism. Finite automata and determinism are not used at all, but are discussed.