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 O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.