Representing Automata Graphically

Begin

Q‟: = {q 0 };

 ‟ := 

Figure 2.14 is the block diagram of the algorithm for determining Q' and  '. Suppose we number the symbols of  ‟ as a 1 , a 2 ,..., a n

 T  Q‟ unmarked

S

End

D

S

i  n

D

B:=  (T, a i )

Q‟:= Q‟  {B};

 ‟ :=  ‟  {  ‟( T, a i ) = B }

i := i+1

Mark T

i := 1

Figure 2.14. Algorithm diagram

Example 2.21:

a) For a finite automaton NFA M = < Q,  ,  , q 0 , F > whose transition graph is

Start

0

a

first

a

2

b

3

b

b

a

2.15. Let's build a deterministic finite Automaton D that recognizes the same language as M. a

Figure 2.15. Represent automata graphically

We can see that M predicts language N(M) = b * (a| b)a + (a| b) Applying the algorithm, we have:

D= ‟,  ‟, q‟ 0 , F‟>. In there:

-  ‟ = {a, b};

- q‟ 0 = {0} = A; Q‟ = {A};

- Consider A:

+  (A, a) =  ({0}, a) =  (0, a) = {1} = B

 Q‟ = {A, B};  ‟ = {  ‟(A, a) = B}

+  (A, b) =  ({0}, b)) =  (0, b) = {0, 1} = C

 Q‟ = {A, B, C};  ‟ = {  ‟(A, a) = B;  ‟(A, b) = C}

- Consider B:

+  (B, a) =  (1, a) = {1} = B

 Q‟ = {A, B, C};  ‟ = {  ‟(A, a) = B;  ‟(A, b)) = C;  ‟(B, a) = B}

+  (B, b)) =  (1, b) = 

 Q‟ = {A, B, C};

 ‟ = {  ‟(A, a) = B;  ‟(A, b)) = C;  ‟(B, a) = B}

- Consider C:

+  (C, a)) =  ({0, 1}, a) =  (0, a)   (1, a) = {1, 2} = D

 Q‟ = {A, B, C, D};

 ‟ = {  ‟(A, a) = B;  ‟(A, b)) = C;  ‟(B, a) = B;  ‟(C, a) = D}

+  (C, b)) =  ({0, 1}, b) =  (0, b)   (1, b) = {0, 1} = C

 Q‟ = {A, B, C, D};

 ‟ = {  ‟(A, a) = B;  ‟(A, b)) = C;  ‟(B, a) = B;  ‟(C, a) = D;

 ‟(C, b) = C}

- Consider D:

+  (D, a)) =  ({1, 2}, a) =  (1, a)   (2, a) = {1, 2}  {3}= {1, 2, 3 }=E

 Q‟ = {A, B, C, D, E};

 ‟ = {  ‟(A, a) = B;  ‟(A, b)) = C;  ‟(B, a) = B;  ‟(C, a) = D;

 ‟(C, b) = C;  ‟(D, a) = E}

+  (D, b)) =  ({1, 2}, b) =  (1, b)   (2, b) = {3} = F

 Q‟ = {A, B, C, D, E, F};

 ‟ = {  ‟(A, a) = B;  ‟(A, b)) = C;  ‟(B, a) = B;  ‟(C, a) = D;

 ‟(C, b) = C;  ‟(D, a) = E;  ‟(D, b) = F}

- Consider E:

+  (E, a)) =  ({1, 2, 3}, a) =  (1, a)   (2, a)   (3, a) = {1, 2, 3} =E

 Q‟ = {A, B, C, D, E, F};

 ‟ = {  ‟(A, a) = B;  ‟(A, b)) = C;  ‟(B, a) = B;  ‟(C, a) = D;

 ‟(C, b) = C;  ‟(D, a) = E;  ‟(D, b) = F;  ‟(E, a) = E}

+  (E, b)) =  ({1, 2, 3}, b) =  (1, b)   (2, b)   (3, b) = {3}= F

 Q‟ = {A, B, C, D, E, F};

 ‟ = {  ‟(A, a) = B;  ‟(A, b)) = C;  ‟(B, a) = B;  ‟(C, a) = D;

 ‟(C, b) = C;  ‟(D, a) = E;  ‟(D, b) = F;  ‟(E, a) = E;  ‟(E, b) = F}

- Consider F:

 (F, a)) =  ({3}, a) =  (3, a) = 

 Q‟ = {A, B, C, D, E, F};

 ‟ = {  ‟(A, a) = B;  ‟(A, b)) = C;  ‟(B, a) = B;  ‟(C, a) = D;

 ‟(C, b) = C;  ‟(D, a) = E;  ‟(D, b) = F;  ‟(E, a) = E;  ‟(E, b) = F}

 (F, b)) =  ({3}, b) =  (3, b) = 

 Q‟ = {A, B, C, D, E, F};

 ‟ = {  ‟(A, a) = B;  ‟(A, b)) = C;  ‟(B, a) = B;  ‟(C, a) = D;

 ‟(C, b) = C;  ‟(D, a) = E;  ‟(D, b) = F;  ‟(E, a) = E;  ‟(E, b) = F}

- F' = {E, F}.

So D = ‟,  ‟, q‟ 0 , F‟>. In there:

Q' = {A, B, C, D, E, F} ;

 ‟ = {a, b}; q' 0 = A;

 ‟:{  ‟(A, a) = B;  ‟(A, b)) = C;  ‟(B, a) = B;  ‟(C, a) = D;  ‟(C, b) = C;

 ‟(D, a) = E;  ‟(D, b) = F;  ‟(E, a) = E;  ‟(E, b) = F}

F' = {E, F}.

Transfer graph of automaton D

Start

A

a

B

a

C

a

D

a

E

b

F

b

b

ab a

Figure 2.16. Represent automata graphically

We can see that D predicts the language L(M) = b * a + (b |  ) We can summarize the results of implementing the above algorithm as follows:

- q‟ 0 = {q 0 } = A;

-  ‟ = {a, b};

- Determine Q' and  '

Step

Maybe you are interested!

• Factors Representing Research Variables And Sign Expectations:
• Model Representing the Pre-Trained Distillation Steps of Miniature Bert Models [111]
• Graph Representing the Dependence of Angle 𝛹 on 𝜂
• Method for Representing Objects in Two-Dimensional Space
• Logic Functions and Methods for Representing Logic Functions Methods for Representing Logic Functions

Table 2.9. Algorithm simulation

- Determine F' = {B, C}.

2.6. Thomson's algorithm

For the purpose of using Finite Automat for lexical analysis. Thomson proposed an algorithm to solve the following problem: Given a regular expression. Let's build an Automat that recognizes the language represented by that regular expression. The ideology of the algorithm is based on the idea that every regular expression can be decomposed into simpler regular expressions. From there, build simple Automata that recognize simple regular expressions. Then synthesize it to get the Automat you need to build.

1) Method for building automata to predict simple regular expressions

a) Build an Automat to guess the empty word  . Figure 2.17 is an Automat that accepts the empty word with i as the starting state, f as the ending state.

Start

i



f

Figure 2.17. Automat guesses the expression r= 

b) Build an Automat to guess the character a  .

Start

i

a

f

Figure 2.18. Automat guesses the expression r = a

Figure 2.18 is a diagram representing Automata guessing and receiving  a  , with i being the starting state, f being the ending state.

2) Method for building synthetic automata from automata

a) Suppose s and t are two regular expressions and N(s), N(t) are two Automata guessing s and t respectively, then the Automator guessing the regular expression s + t looks like Figure 2.19 .



N(s)



Start

i

f



N(t)



Figure 2.19. Automat guesses the expression r = s+t

Here i, f are new states that are not yet in N(s), N(t), from the starting state i Automat sees the empty word; it can go to the starting state of N(r) or the starting state of N(t). Conversely, from the final state of N(s) or N(t), it can move to the final state f when encountering an empty word.

b) Build an Automator to recognize regular expressions st. Suppose N(s), N(t) are two automatons that accept s and t respectively, then automata accepts the regular expression st as shown in figure 2.20.

Start

i

N(s)

N(t)

f

Figure 2.20. Automat guesses the expression r=st

Here i is a new state that does not exist in N(s) and N(t). When encountering an empty word, Automat moves to the starting state of N(s), the ending state of N(s) and the starting state. of N(t) are combined into one state, the final state of N(t) becomes the final state of the composite Automat.

c) Assuming s is a regular expression, and N(s) is an Automator that accepts it, we build an Automata that accepts s * and s + . Figure 2.21a depicts Automat N(s * ), Figure 2.21 b

describes Automat N(s + ) 

Start



i

N(s)



f



Figure 2.21a. Automat guesses the expression r = s *



Start

i 

N(s)



f

Figure 2.21b. Automat guesses the expression r = s +

Here i, f are new states, respectively the starting state and final state of Automat.

3) Thomson's algorithm

Input: r – regular expression; Output: NFA  M ; N( M) = N(r). Process:

Step 1: Parse r into simple regular expressions

- Find in the regular expression the operation with the lowest priority

- If so, parse the regular expression into operands according to that operation. Each row – a simpler regular expression.

- Go back to step 1 until you have analyzed all regular expressions and simple regular expressions of the form r = a.

Step 2: Construction

- Build simple automata that recognize simple regular expressions.

- Build synthesis automata in reverse order until building a synthesis automaton that recognizes the regular expression r.

Comment:

- With a regular expression r, Automat N(r) predicts that it will have a maximum number of states not exceeding twice the number of characters in r and the number of operations in it. This observation is due to the fact that in the Thomson algorithm, for each symbol or operation in r, we add no more than two states.

- Each Automat N(r) built according to the Thomson algorithm has only one initial state and one final state, and the final state never switches to any other state.

- Each state of Automat N(r) has only one transition state according to the symbol of the set  and a maximum of two transition states according to the empty symbol  , so in general, an Automat built according to the Thomson algorithm is an Automata. not deterministic.

- Because each time we build a new Automat, we add a new start and end state, so an Automat built according to the Thomson algorithm does not have two overlapping states.

Example 2.22:

Let r = (a  b) * abb. Let's build NFA  to predict regular expression r according to Thomson's algorithm.

Step 1: Analyze r = (a + b) * abb

- r = r 1 r 2 ;

r 1 = (a + b) * ab; r 2 = b;

- r 1 = r 3 r 4 ;

r 3 = (a + b) * a; r 4 = b;

- r 3 = r 5 r 6 ;

r 5 = (a + b) * ; r 6 = a;

- r 5 = (r 7 ) * ; r 7 = a + b;

- r 7 = r 8 r 9 ;

R 8 = a ; r 9 = b;

Step 2: Construction

- Build Automate to guess r 8 = a; r 9 = b

Start

2

a

3

Start

4

b

5

Figure 2.22. The automata guesses a and b

- Build a Automator to guess r 7 = r 8 + r 9



2

a

3



Start

first



6



4

b

5

Figure 2.23. Automata guesses r 7 = a+b