2.5  Closure Properties for Finite-Memory Programs

A helpful approach in simplifying the task of programming is to divide the given problem into subproblems, design subprograms to solve the subproblems, and then combine the subprograms into a program that solves the original problem. To allow for a similar approach in designing finite-state transducers (and finite-memory programs), it is useful to determine those operations that preserve the set of relations that are computable by finite-state transducers. Such knowledge can then be used in deciding how to decompose given problems to simpler subproblems, as well as in preparing tools for automating the combining of subprograms into programs.

In general, a set is said to be closed under a particular operation if each application of the operation on elements of the set results in an element of the set.

Example 2.5.1    The set of natural numbers is closed under addition, but it is not closed under subtraction. The set of integers is closed under addition and subtraction, but not under division. The set { S | S is a set of five or more integers } is closed under union, but not under intersection or complementation. The set { S | S is a set of at most five integer numbers } is closed under intersection, but not under union or complementation.

The first theorem in this section is concerned with closure under the operation of union.

Theorem 2.5.1    The class of relations computable by finite-state transducers is closed under union.

Proof     Consider any two finite-state transducers M₁ = <Q₁, ₁, ₁, ₁, q₀₁, F₁> and M₂ = <Q₂, ₂, ₂, ₂, q₀₂, F₂>. With no loss of generality assume that the sets q₁ and q₂ of states are mutually disjoint, and that neither of them contains q₀.

Let M₃ be the finite-state transducer <Q₃, ₃, ₃, ₃, q₀, F₃>, where Q₃ = Q₁ Q₂ {q₀}, ₃ = _{1 2}, ₃ = _{1 2} {(q₀, , q₀₁, ), (q₀, , q₀₂, )}, and F₃ = F₁ F₂ (see Figure 2.5.1).

Figure 2.5.1 A schema of a finite-state transducer M3 that computes R(M1) R(M2).

Intuitively, M₃ is a finite-state transducer that at the start of each computation nondeterministically chooses to trace either a computation of M₁ or a computation of M₂.

By construction, R(M₃) = R(M₁) R(M₂).

Besides their usefulness in simplifying the task of programming, closure properties can also be used to identify relations that cannot be computed by finite-state transducers.

Example 2.5.2    The union of the languages L₁ = {} and L₂ = { 0ⁱ1ⁱ | i 1 } is equal to the language L₃ = { 0ⁱ1ⁱ | i 0 }. By Theorem 2.5.1 the union L₃ = L₁ L₂ of L₁ and L₂ is a regular language if L₁ and L₂ are regular languages. Since L₁ = {} is a regular language, it follows that L₃ is a regular language if L₂ is a regular language. However, by Example 2.4.2 the language L₃ = { 0ⁱ1ⁱ | i 0 } is not regular. Consequently, is also L₂ = { 0ⁱ1ⁱ | i 1 } not regular.

The relations R₁ = { (0ⁱ1^j, cⁱ) | i, j 1 } and R₂ = { (0ⁱ1^j, c^j) | i, j 1 } are computable by deterministic finite-state transducers. The pair (0ⁱ1^j, c^k) is in R₁ if and only if k = i, and it is in R₂ if and only if k = j. The intersection R₁ R₂ contains all the pairs (0ⁱ1^j, c^k) that satisfy k = i = j, that is, R₁ R₂ is the relation { (0ⁿ1ⁿ, cⁿ) | n 1 }.

If R₁ R₂ is computable by a finite-state transducer then the language { 0ⁿ1ⁿ | n 1 } must be regular. However, by Example 2.4.2 the language is not regular. Therefore, the class of the relations that are computable by finite-state transducers is not closed under intersection.

The class of the relations computable by the finite-state transducers is also not closed under complementation. An assumption to the contrary would imply that the nonregular language R₁ R₂ is regular, because by DeMorgan's law R₁ R₂ = . That is, an assumed closure under complementation would imply that and are computable by finite-state transducers. Theorem 2.5.1 would then imply that the union is computable by finite-state transducers. Finally, another application of the assumption would imply that = is also computable by a finite-state transducer.

The choice of R₁ and R₂ also implies the nonclosure, under intersection, of the class of relations computable by deterministic finite-state transducers. The nonclosure under union and complementation, of the class of relations computable by deterministic finite-state transducers, is implied by the choice of the relations {(1, 1)} and {(1, 11)}.

For regular languages the following theorem holds.

Theorem 2.5.2    Regular languages are closed under union , intersection, and complementation.

Proof     By DeMorgan's law and the closure of regular languages under union (see Theorem 2.5.1), it is sufficient to show that regular languages are closed under complementation.

For the purpose of this proof consider any finite-state automaton M = <Q, , , q₀, F>. By Theorem 2.3.1 it can be assumed that M is deterministic, and contains no transition rules.

Let M_eof be M with a newly added, nonaccepting "trap" state, say, q_trap and the following newly added transition rules.

1.  (q, a, q_trap) for each pair (q, a) -- of a state q in Q and of an input symbol a in -- for which no move is defined in M. That is, for each (q, a) for which no p exists in Q such that (q, a, p) is in .
2.  (q_trap, a, q_trap) for each input symbol a in .

The complementation of the language L(M) is accepted by the finite-state automaton M_complement that is obtained from M_eof by interchanging the roles of the accepting and nonaccepting states.

For each given input a₁ a_n the finite-state automaton M_complement has a unique path that consumes a₁ a_n until its end. The path corresponds to the sequence of moves that M_eof takes on such an input. Therefore, M_complement reaches an accepting state on a given input if and only if M_eof does not reach an accepting state on the the input.

Example 2.5.3    Let M be the finite-state automaton whose transition diagram is given in Figure 2.5.2(a).

Figure 2.5.2 The finite-state automaton in (b) accepts the complementation of the language that the finite-state automaton in (a) accepts.

Without the trap state q_trap, neither M nor M_complement would be able to accept the input 011, because none of them would be able to consume the whole input.

Without the requirement that the algorithm has to be applied only on deterministic finite-state automata, M_complement could end up accepting an input that M also accepts. For instance, by adding the transition rule (q₁, 1, q₁) to M and M_complement, on input 01 each of the finite-state automata can end up either in state q₀ or in state q₁. In such a case, M would accept 01 because it can reach state q₁, and M_complement would accept 01 because it can reach state q₀.

[next] [prev] [prev-tail] [front] [up]