O'Reilly logo

Introduction to Formal Languages, Automata Theory and Computation by Kamala Krithivasan, R Rama

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required