0 Replies - 4554 Views - Last Post: 21 April 2015 - 09:13 PM Rate Topic: -----

#1 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12179
  • View blog
  • Posts: 45,247
  • Joined: 27-December 08

Automata Theory- Brzozowski Algebraic Method

Posted 21 April 2015 - 09:13 PM

Automata Theory- Brzozowski Algebraic Method

A LaTeX typeset copy of this tutorial is below for download:
Attached File  Brzozowski_Algebraic_Method.pdf (126.4K)
Number of downloads: 871

I. Introduction
Recall that a language is regular if and only if it is accepted by some finite state automaton. In other words, each regular expression has a corresponding finite state automaton. An important problem in Automata Theory deals with converting between regular expressions and finite state automata. The Brzozowski Algebraic Method is an intuitive algorithm which takes a finite state automaton and returns a regular expression. This algorithm relies on notions from graph theory and linear algebra; particularly, graph walks and the substitution method for solving systems of equations.


II. Notions From Graph Theory
In this section, the notions of a graph walk and the adjacency matrix will be introduced, along with some relevant results. I start with the definition of a walk.

Walk: Let G be a graph, and let v = (v_{1}, v_{2}, ..., v_{n}) be a sequence of vertices (not necessarily distinct). Then v is a walk if v_{i}, v_{i+1} are adjacent for all i \in {1, ..., n-1}.

Intuitively, we start at some vertex v_{1}. Then we visit v_{2}, which is a neighbor of v_{1}. Then v_{3} is a neighbor of v_{2}. Consider the cycle graph on four vertices, C_{4}, which is shown below. Some example walks include (v_{a}, v_{b}, v_{d}) and (v_{a}, v_{b}, v_{a}, v_{c}, v_{a}). However, (v_{a}, v_{d}, v_{a}, v_{b}) is not a walk, as v_{a} and v_{d} are not adjacent.

Posted Image


Consider an example of a walk on a directed graph. Observe that (S, A, A, q_{acc}) is a walk, but (S, A, S) is not a walk as there is no directed edge (A, S) in the graph.

Posted Image


The adjacency matrix will now be defined, and we will explore how it relates to the notion of a walk.

Adjacency Matrix: Let G be a graph. The adjacency matrix A \in {0, 1\}^{V \times V}, with A_{ij} = 1 if vertex i is adjacent to vertex j, and A_{ij} = 0 otherwise.

Note: If G is undirected, then A_{ij} = A_{ji}. Finite state automata diagrams are directed graphs, though, so A_{ij} may be different than A_{ij}.

Consider the simple C_{4} graph above. The adjacency matrix for this graph is:

Attached Image

Similarly, the adjacency matrix of the above directed graph is:

Attached Image

The adjacency matrix is connected to the notion of a walk by the fact that (A^{n})_{ij} counts the number of walks of length n starting at vertex i and ending at vertex j. The proof of this theorem provides the setup for the Brzozowski Algebraic Method. For this reason, I will provide a formal proof of this theorem.

Theorem: Let G be a graph and let A be its adjacency matrix. Let n \in \mathbb{N}. Then each cell of A^{n}, denoted (A^{n})_{ij}, counts the number of walks of length n starting at vertex i and ending at vertex j.

Proof: This theorem will be proven by induction on n \in \mathbb{N}. Consider the base case of n = 1. By definition of the adjacency matrix, if vertices i and j are adjacent, then A_{ij} = 1. Otherwise, A_{ij} = 0. Thus, A counts the number of walks of length 1 in the graph. Thus, the theorem holds at n = 1.

Suppose the theorem holds for an arbitrary integer k > 1. The theorem will be proven true for the k+1 case. As matrix multiplication is associative, A^{k+1} = A^{k} \cdot A. By the inductive hypothesis, A^{k} counts the number of walks of length k in the graph, and A counts the number walks of length 1 in the graph. Consider:

(A^{k+1})_{ij} = \sum_{x=1}^{n} ((A^{k})_{ix} \cdot A_{xj})

And so for each x \in {1, ..., n\}, (A^{k})_{ix} \cdot A_{xj} \neq 0 if and only if there exists at least one walk of length k from vertex i to vertex x, and an edge from vertex k to vertex j. Thus, the theorem holds by the principle of mathematical induction.

Example: Consider again the graph C_{4}, and (A(C_{4}))^{2}, given below. This counts the number of walks of length 2 on G. Observe that ((A(C_{4}))^{2})_{14} states that there are two walks of length 2 from vertex v_{a} to vertex v_{d}. These walks are (v_{a}, v_{b}, v_{d}) and (v_{a}, v_{c}, v_{d}).

Attached Image

III. Brzozowski Algebraic Method

The Brzozowski Algebraic Method takes a finite state automata diagram (the directed graph) and constructs a system of linear equations to solve. Solving a subset of these equations will yield the regular expression for the finite state automata. I begin by defining some notation. Let E_{i} denote the regular expression which takes the finite state automata from state q_{0} to state q_{i}.

The system of equations consists of recursive definitions for each E_{i}, where the recursive definition consists of sums of E_{j}R_{ji} products, where R_{ji} is a regular expression consisting of the union of single characters. That is, R_{ji} represents the selection of single transitions from state j to state i, or single edges (j, i) in the graph. So if \delta(q_{j}, a) = \delta(q_{j}, b) = q_{i}, then R_{ji} = (a + b). In other words, E_{j} takes the finite state automata from state q_{0} to q_{j}. Then R_{ji} is a regular expression describing strings that will take the finite state automata from state j to state i in exactly one step. That is:

E_{i} = \sum_{j \in Q, \text{there exists a walk from state j to state i}} E_{j}R_{ji}

Note: Recall that addition when dealing with regular expressions is the set union operation.

Once we have the system of equations, then we solve them by backwards substitution just as in linear algebra and high school algebra.

The explanation of this algorithm is dense, though. Let's work through an example to better understand it. We seek a regular expression over the alphabet \Sigma = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9\} describing those integers whose value is 0 modulo 3.

In order to construct the finite state automata for this language, we take advantage of the fact that a number n \equiv 0 \pmod{3} if and only if the sum of n's digits are also divisible by 3. For example, we know 3|123 because 1 + 2 + 3 = 6, a multiple of 3. However, 125 is not divisible by 3 because 1 + 2 + 5 = 8 is not a multiple of 3.

Now for simplicity, let's partition \Sigma into its equivalence classes a = {0, 3, 6, 9\} (values congruent to 0 mod 3), b = {1, 4, 7\} (values equivalent to 1 mod 3), and c = {2, 5, 8\} (values equivalent to 2 mod 3). Similarly, we let state q_{0} represent a, state q_{1} represent b, and state q_{2} represent c. Thus, the finite state automata diagram is given below, with q_{0} as the accepting halt state:

Posted Image

We consider the system of equations given by E_{i}, taking the FSM from state q_{0} to q_{i}:
  • E_{0} = \lambda + E_{0}a + E_{1}c + E_{2}b

    If at q_{0}, transition to q_{0} if we read in the empty string, or if we go from q_{0} \to q_{0} and read in a character in a; or if we go from q_{0} \to q_{2} and read in a character in c; or if we go from q_{0} \to q_{2} and read in a character from b.

  • E_{1} = E_{0}b + E_{1}a + E_{2}c

    To transition from q_{0} \to q_{1}, we can go from q_{0} \to q_{0} and read in a character from b; go from q_{0} \to q_{1} and read in a character from a; or go from q_{0} \to q_{2} and read in a character from c.

  • E_{2} = E_{0}c + E_{1}b + E_{2}a

    To transition from q_{0} \to q_{2}, we can go from q_{0} \to q_{0} and read a character from c; go from q_{0} \to q_{0} and read in a character from b; or go from q_{0} \to q_{2} and read in a character from a.


Since q_{0} is the accepting halt state, only a closed form expression of E_{0} is needed.

There are two steps which are employed. The first is to simplify a single equation, then to backwards substitute into a different equation. We repeat this process until we have the desired closed-form solution for the relevant E_{i} (in this case, just E_{0}). In order to simplify a variable, we apply Arden's Lemma, which states that E = \alpha + E\beta = \alpha(\beta)^{*}, where \alpha, \beta are regular expressions.

We start by simplifying E_{2} using Arden's Lemma: E_{2} = (E_{0}c + E_{1}b)a^{*}.

We then substitute E_{2} into E_{1}, giving us E_{1} = E_{0}b + E_{1}a + (E_{0}c + E_{1}b(a)^{*}c = E_{0}(b + ca^{*}c) + E_{1}(c + ba^{*}c). By Arden's Lemma, we get E_{1} = E_{0}(b + ca^{*}c)(a + ba^{*}c)^{*}

Substituting again, E_{0} = \lambda + E_{0}a + E_{0}(b + ca^{*}c)(a + ba^{*}c)^{*}c + (E_{0}c + E_{1}b)a^{*}b.

Expanding out, we get E_{0} = \lambda + E_{0}a + E_{0}(b + ca^{*}c)(a + ba^{*}c)^{*}c + E_{0}ca^{*}b + E_{0}(b + ca^{*}c)(a + ba^{*}c)^{*}a^{*}b.

Then factoring out: E_{0} = \lambda + E_{0}(a + ca^{*}b + (b + ca^{*}c)(a + ba^{*}c)^{*}(c + ba^{*}b) ).

By Arden's Lemma, we have: E_{0} = (a + ca^{*}b + (b + ca^{*}c)(a + ba^{*}c)^{*}(c + ba^{*}b) )^{*}, a closed form regular expression for the integers mod 0 over \Sigma.


Note: The hard part of this algorithm is the careful bookkeeping. In a substitution step, the regular expression for an E_{i} may grow and require simplification. Be careful to keep track of how the regular expression is expanded on a substitution step, and how it is possible to factor out terms.

Is This A Good Question/Topic? 1
  • +

Page 1 of 1