There are not much of reasons to deal with nondeterminism in mathematics. However, it works with values, sets, and functions. Corresponding to these, nondeterminism exists in the Turing machine and in finite automata (nondeterministic FA). Using the latter, we can build nondeterministic models of computation. Unlike a deterministic FA, a nondeterministic FA can have many transitions (in parallel) for an input symbol, or there may not be any transition at some states, or there may be transitions without any input. Given any regular expression we can build a nondeterministic FA as a first step, then convert this NFA into DFA, and then minimize the DFA. Another variant of FA is two-way FA, unlike FA it has head movement in both directions—left and right, which makes it more like a Turing machine, but the tape head can read only. Yet another interesting coverage in this chapter is finite-state transducers (FSTs)—they produce output sequences corresponding to input sequences in contrast to finite automata which produce yes/no output for an input sequence. The FST can be in the form of a Mealy machine or a Moore machine. The FSTs have applications in human speech processing and phonological and morphological analysis in Natural language Processing. The chapter ends with self-assessment review questions, a number of practice exercises, and solved exercises at the end.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Variants of Finite Automata

  • K. R. Chowdhary

摘要

There are not much of reasons to deal with nondeterminism in mathematics. However, it works with values, sets, and functions. Corresponding to these, nondeterminism exists in the Turing machine and in finite automata (nondeterministic FA). Using the latter, we can build nondeterministic models of computation. Unlike a deterministic FA, a nondeterministic FA can have many transitions (in parallel) for an input symbol, or there may not be any transition at some states, or there may be transitions without any input. Given any regular expression we can build a nondeterministic FA as a first step, then convert this NFA into DFA, and then minimize the DFA. Another variant of FA is two-way FA, unlike FA it has head movement in both directions—left and right, which makes it more like a Turing machine, but the tape head can read only. Yet another interesting coverage in this chapter is finite-state transducers (FSTs)—they produce output sequences corresponding to input sequences in contrast to finite automata which produce yes/no output for an input sequence. The FST can be in the form of a Mealy machine or a Moore machine. The FSTs have applications in human speech processing and phonological and morphological analysis in Natural language Processing. The chapter ends with self-assessment review questions, a number of practice exercises, and solved exercises at the end.