Chapter 6. Variants of Finite Automata
We have seen that DFSA, NFSA, and NFSA with ε-moves have the same power. They accept the family of regular sets. In this chapter, we consider two generalized versions of FSA. While one of them accepts only regular sets, the other accepts sets, which are not regular. We also have a discussion on probabilistic finite automata and weighted finite automata. These two models have applications in image analysis.
Two-Way Finite Automata
A two-way deterministic finite automaton (2DFSA) is a quintuple M = (K, Σ, δ, q0, F) where K, Σ, q0, F are as in DFSA and δ is a mapping from K × Σ into K × {L, R}.
The input tape head can move in both directions. The machine starts on the leftmost symbol of the input in the initial ...
Get Introduction to Formal Languages, Automata Theory and Computation now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
