TOC Chapter 6

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.

6.1. Two-Way Finite Automata

A two-way deterministic finite automaton (2DFSA) is a quintuple M = (K, Σ, δ, q₀, F) where K, Σ, q₀, 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 state. At any time, depending on the state and the symbol read, the automaton changes its state, and moves its tape head left or right as specified by the move. If the automaton moves off at the right end of the input tape in a final state, the input is accepted. The input can be rejected in three ways:

6.2. Multihead Finite State Automata

One-way multihead finite automata have been studied in some detail in the literature (Rosenberg, 1996). They have more accepting power than FSA.

6.3. Probabilistic Finite Automata

Let = (x₁, ..., x_n) be an n-dimensional row stochastic vector, n ≥ 1. Then, (i) = x_i, 1 ≤ i ≤ n, 0 ≤ x_i ≤ 1, Σx_i = 1.

Definition 6.4 A finite probabilistic automaton over a finite alphabet V is an ordered triple PA = (S, s0, M), where S = {s1, s2, ..., sn} is a finite set with n ≥ 1 elements (the set of internal states), s0 is an n-dimensional stochastic row vector (the initial distribution) and M is a mapping of V into the set of n-dimensional stochastic matrices. For x ∊ V, the (i, j)th entry in the matrix M(x) is denoted by pj (si, x) and referred to as the transient probability of PA to enter into the state sj, after being in the state si after reading the input x.

6.4. Weighted Finite Automata and Digital Images

In this section we consider a variant of finite automata, which is called weighted finite automata (WFA). We give some basic definitions and notations for WFA and the representation of digital images using WFA.

A digital image of finite resolution m × n consists of m × n pixels each of which is assigned a value corresponding to its color or grayness. In this section, we consider only square images of resolution 2ⁿ × 2ⁿ.

Problems and Solutions

1.	Consider the following 2DFSA. Give two strings in T(M) and two strings not in T(M) tracing the moves of M. What is T(M)?
Solution.	Two strings accepted (i) a b a a b (ii) a a b Two strings rejected T(M) consists of strings where two b’s do not occur consecutively.
2.	Consider the PA over the alphabet {a, b} with K = {q1, q2}. Initial distribution is π = (1, 0) and . Find π M(x) where x ∊ {a2, b2, ab, a2b, b3a2}.
Solution.	π M (a2) = 0.9375, π M (b2) = 0.25, π M (ab) = 0.1250, π M (a2b) = 0.0313, π M (b3a2) = 0.9609.
3.	Consider the PA over the alphabet {a, b} with K = {q1, ..., q6}. Initial distribution is (1, 0, 0, 0, 0, 0) and S = (0, 0, 0, 1, 0, 0). Find π M(x) where x ∊ {ab, a2b2, bab, b2ab3, b4ab}. Also, find the language accepted with cut point η = 0.25.
Solution.	π M(ab) = 0, πM(a2b2) = 0, πM(bab) = 0.0625, πM(b2ab3) = 0.0098, πM(b4ab) = 0.1855. For L(G) = {bna|n ≥ 1} the cut point η is 0.25.
4.	Construct FSA over the alphabet {0, 1, 2, 3} to represent the following black and white picture.
Solution.

Exercises

1.	Consider the following 2DFSA. Give two strings in T(M) and two strings not in T(M) tracing the moves of M.
2.	Show that adding the capability of 2DFSA to keep its head stationary (and change state) on a move does not give additional power.
3.	Let M be a 2DFSA. T(M) is the set of strings which make M move off at the right end in a final state. We know T(M) is a regular set. Let Tnf(M) be the set of strings which make M move off at the right end in a non-final state; let Tleft(M) be the set of strings which make M move off at the left end of the tape. Tloop(M) be the set of strings which make M loop. Show that Tnf (M), Tleft(M), Tloop (M) are regular sets.
4.	Construct multi-head automata to accept: {wcw|w ∊ {a, b}*} {anbncn|n ≥ 1}
5.	Σ* is a semigroup. An equivalence relation E on Σ* is right invariant if xEy ⇒ xzEyz for all z ∊ Σ*. Similarly we can define left invariance. An equivalence relation is a congruence relation if it is both right invariant and left invariant. Prove that the following three statements about a language L ⊆ Σ* are equivalent: L is a regular set. L is the union of some equivalence classes generated, by a congruence relation of finite index over Σ*. The congruence relation ≡ is defined as follows: x ≡ y if and only if for all strings z and w zxw is in L exactly when zyw is in L. Then ≡ is of finite index.
6.	Construct FSA over the alphabet {0, 1, 2, 3} to represent the following black and white pictures.