ABSTRACT
Q, F and Δ are referred to as the set of states, the set of final states and the alphabet of input symbols, respectively� Q contains a special state called the start state, usually denoted by s� M accepts w ∈ Δ* if sw ⇒* f in M with f ∈ F� The language accepted by M or, briefly, the language of M is denoted by L(M) and defined as the set of all strings that M accepts; formally,
L(M) = {w| w ∈ Δ*, sw ⇒* f, f ∈ F }
Every string an FA M rewrites has the form qav, where q ∈ Q, a ∈ Δ ∪ {ε}, and v ∈ Δ*� By using a rule of the form qa → p, where q, p ∈ Q and a ∈ Δ ∪ {ε}, M reads a and changes q to p� By repeatedly performing rewriting steps like this, M reads the string of input symbols in a left-to-right
32
way and, simultaneously, moves the current state closer toward its right end� M accepts w ∈ Δ* if starting from sw, it reads all the input string and ends up in a final state�
We next introduce some specific terminology concerning finite automata� We use this terminology throughout this book whenever finite automata are under discussion�
Convention 3.2 We denote the set of all finite automata by FA Ψ� Set FA Φ = {L(M)| M ∈ FA Ψ}� For every M ∈ FA Ψ, a configuration of M is a string of the form qv, where v ∈ Δ* and q ∈ Q� M Χ denotes the set of all configurations of M� If β ⇒ χ in M, where β, χ ∈ M Χ, M makes a move or a computational step from β to χ� M makes a sequence of moves or a computation from β to χ if β ⇒* χ in M, where β, χ ∈ M Χ� A computation of the form sw ⇒* f, where w ∈ Δ* and f ∈ F, is called an accepting computation�
Furthermore, we automatically assume that Σ, Δ, Q, s, F, and R denote its total alphabet, the alphabet of input symbols, the set of states, the start state, the set of final states, and the set of rules of M, respectively�
Let us point out that apart from Convention 3�2, we frequently apply the previously introduced Convention 2�3 to FAs as well� That is, for any M ∈ FA Ψ, whenever there exists any danger of confusion concerning its components, we mark Σ, Δ, Q, s, F, and R with M as M Σ, M Δ, M Q, M s, M F, and M R, respectively, to explicitly relate these components to M (in particular, we make these marks when several automata are simultaneously discussed)�
3.1.1 Representations of Finite Automata Throughout this book, we represent any M ∈ FA Ψ in one of the following five ways�
1� The formal description of M spells out the states, symbols, and rules of M strictly according to Definition 3�1�
2� M is defined by simply listing its rules together with specifying the start state and the final states of M�
3� M is specified by its state table whose columns and rows are denoted with the members of Δ ∪ {ε} and the states of Q, respectively� The start state denotes the first row� The final states are specified by underlining� For each q ∈ Q and each a ∈ Δ ∪ {ε}, the entry in row q and column a contains {p| qa → p ∈ R}� For brevity, we omit the braces in the sets of these entries; a blank entry means ∅�
4� M is specified by its state diagram in a pictorial way� That is, this diagram is a labeled directed graph such that each node is labeled with a state q ∈ Q, and for two nodes q, p ∈ Q, there is an edge (q, p) labeled with {a| qa → p ∈ R, a ∈ Δ ∪ {ε}}� For simplicity, we entirely omit every edge labeled with ∅ in the diagram� Furthermore, in the specification of edge-labeling nonempty sets, we omit the braces; for instance, instead of {a, b} as an edge label, we just write a, b� To symbolically state that a state s is the start state, we point to it with a short arrow like in Figure 3�1� Final states are doubly circled�
5� We give an informal description of M� That is, we describe it as a procedure, omitting various details concerning their components� Describing M in this way, we always make sure that the translation from this description to the corresponding formal description represents a straightforward task�
◾
Example 3.1 In this example, we design an FA M that accepts {a}+{b}* ∪ {b}+, symbolically written as
We describe M in all five ways sketched earlier�
Informal description� We design M so it accepts either w1w2 or w3, where w1 ∈ {a}+, w2 ∈ {b}*, w3 ∈ {b}+; therefore, L(M) = {a}+{b}* ∪ {b}+� From its start state 1, without reading any input symbol, M moves either to states 2 to accept w1w2 or to state 4 to accept w3� Looping 2, M can read any number of as� In addition, M can make a move from 2 to state 3 while reading a� In 3, M reads any number of bs� As 3 is a final state, M completes the acceptance of w1w2 in this way� To accept w3, in 4, M reads any number of bs� In addition, M can make a move from 4 to state 5 with b� Since 5 is a final state, M completes the acceptance of w3�
List of Rules� M is defined by the following seven rules:
1 → 2, 1 → 4, 2a → 2, 2a → 3, 3b → 3, 4b → 4, 4b → 5 where 1 is the start state while 3 and 5 are final states�
Formal description� Let M = (Σ, R), where Σ = Q ∪ Δ with Q = {1, 2, 3, 4, 5}, Δ = {a, b}, F = {3, 5}, and 1 is the start state� Furthermore, R contains the seven rules listed earlier�
State Table� In Figure 3�2, we describe M by its state table�
State Diagram� In Figure 3�1, we describe M by its state diagram�
For instance, M accepts aab in this way
1aab ⇒ 2aab ⇒ 2ab ⇒ 3b ⇒ 3 Considering the design of M in terms of its implementation, we see that it deserves an improve-
ment� Indeed, M can be redesigned, so it contains fewer rules and states� Even more importantly, the current version of M can perform several different computations on the same input, and this nondeterminism obviously complicates its use in practice� To put it more generally, we obviously
Figure 3.2 State table.
