5

{2, 3} | b | |

6 | {2, 3} | b |

7 | {2, 3} | $ |

Maybe you are interested!

- A, B, C. Describe the String Analysis Process W = Cad
- Bidv Quang Trung's Formation and Development Process
- The Formation And Development Process Of Vpbank Ha Tinh Branch
- Process of Consumer Lending of Saigon Thuong Tin Commercial Joint Stock Bank – Hanoi Branch
- Commercial Bank's Consumer Lending Process

Table 2.5. Describe the process of guessing and receiving strings

We have q = {2, 3} F = {3} .

So the above automaton guesses the word w = aaabbbb.

**2.4.3. ****The algorithm uses NFA **

Input: NFA M and the input string w is terminated by $. Output: Did M guess get w?

Process:

q:= ε-closure(q 0 ); c:= get_char(); While c <> “$” do

Begin

q:= ε-closure( (q,c));

c:= get_next_char();

End;

If q F then writeln (“recognize w”)

Else writeln ('w not recognized');

Example 2.19:

Let Automat be represented graphically as shown.

Use the above algorithm to test Automat's prediction of the word w = aababb

2

a

3

Start

0

first

6

7

a

8

b

9

b

ten

4

b

5

Figure 2.8. NFA with ε - displacement

We can present the algorithm using automaton to guess w with the following table:

Step

q = ε -closure( (q,c)) | c | |

initialization | {0, 1, 2, 4, 6, 7} | a |

first | {1, 2, 3, 4, 6, 7, 8} | a |

2 | {1, 2, 3, 4, 6, 7, 8} | b |

3 | {1, 2, 4, 5, 6, 7, 9} | a |

4 | {1, 2, 3, 4, 6, 7, 8} | b |

5 | {1, 2, 4, 5, 6, 7, 9} | b |

6 | {1, 2, 4, 5, 6, 7, 10} | $ |

Table 2.6. Describe the process of guessing and receiving strings

We have q F = {10} . So the above automaton guesses w = aababb.

NFA is a special case of NFA . Therefore, we can still use the above algorithm for NFA to recognize lexemes and in this case we always have ε-closure(T) = T with T Q.

**2.5. ****Automated transformation techniques**

Deterministic Finite Automata and Non-Deterministic Finite Automata are linguistically equivalent, that is, they assume the same regular set. However, in terms of structure and writing translation programs, Non-Deterministic Finite Automata is much more complicated than Deterministic Finite Automata, so it is necessary to convert Non-Deterministic Finite Automata to Deterministic Finite Automata.

To transform a non-deterministic finite Automat into a linguistically equivalent deterministic Automat, first let's recall some of the following knowledge:

Consider the finite Automata M = < Q, , , q 0 , F > non-deterministic

*-* We call the set ε-closure(q) the set of states that M can reach from state q Q when Automat reads the empty word .

ε-closure(q) = p Q * (q, ) = p

*-* We call the set ε-closure(T) the set of states that M can reach from any state q T with T Q when Automat reads the empty word as

ε-closure(T) = p Q * (q, ) = p; q T; T Q

= q T ε-CLOSURE(q) with T Q

- We call the set δ (T, a) the set of states that M can reach from any state q T with T Q when Automat reads an input symbol a as

δ (T, a) = q T δ(q, a)

1) The idea of the algorithm

Suppose there is a non-deterministic finite Automata M = , , q 0 , F>.

We need to build a deterministic finite automaton D = ‟, ‟, q' 0 , F'> are equivalent to recognizing the same language.

Then each state of deterministic Automaton D will correspond to a set of states of nondeterministic Automaton M that M can reach after reading a character of the input word. Initially D has a starting state of ε-closure(q 0 ) and the final state of D is a state that contains a final state of M. The process of calculating ε-closure(T) is the process of finding the node that can be reached on the graph from a given set of starting nodes with input characters being letters of the input alphabet .

2) Algorithm to transform NFA to DFA

Input: NFA M = , , q 0 , F>.

Output: DFA D = ‟, ‟, q‟ 0 , F‟>;

L( M) = L(D).

Process:

Step 1: Determine q' 0 ; ‟

- ‟ = ;

- Calculate q‟ 0 : A = ε-closure(q 0 );

- Put A into the state Q' and consider it as an unmarked state T. Step 2: Determine Q' and '

If in Q' there is an unmarked state T, then mark T

- For each a ‟ performed

+ Calculate B = ε-closure( (T,a));

+ If B is a new state that does not exist in Q', then put B in Q';

+ Insert into the table the transfer function ‟: ‟(T, a) = B.

Step 3: Repeat step 2 if Q's status is still unchecked. Step 4: F‟ = {A Q‟ / A F }

Step 5: D = ‟, ‟, q‟ 0 , F‟>

Begin

Q‟: = e_closure(q 0 );

‟ :=

Figure 2.9 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:= e-cloure( (T, a i ))

Q‟:= Q‟ {B};

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

i := i+1

Mark T

i := 1

Figure 2.9. Algorithm diagram

Example 2.20:

a) Let the finite Automata NFA M = < Q, , , q 0 , F > have a transition graph of

Start

0

first

a

2

b

3

b

b

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

Figure 2.10. Represent automata graphically

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

D = < Q‟, ‟, ‟, q‟ 0 , F‟ >. In there:

- ‟ = {a, b};

- q‟ 0 = ε-closure(0) = {0, 1} = A; Q‟ = {A};

- Consider A:

+ ε-closure( (A, a)) = ε-closure( ({0, 1}, a))

= ε-closure ( (0, a) (1, a)) = ε-closure( {1, 2})

= ε-closure({1, 2}) = ε-closure(1) ε-closure(2)

= {1} {2, 3} = {1, 2, 3} = B

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

+ ε-closure( (A, b)) = ε-closure( ({0, 1}, b))

= ε-closure ( (0, b) (1, b)) = ε-closure({0,1} )

= ε-closure({0, 1}) = ε-closure(1) ε-closure(1)

= {0,1} {1} = {0, 1} = A

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

- Consider B:

+ ε-closure( (B, a)) = ε-closure( ({1, 2, 3}, a))

= ε-closure ( (1, a) (2, a) (3, a))

= ε-closure({1,2} )= ε-closure({1, 2})

= {1, 2, 3} = B

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

+ ε-closure( (B, b)) = ε-closure( ({1, 2, 3}, b))

= ε-closure ( (1, b) (2, b) (3, b))

= ε-closure( {3} ) = ε-closure({3})

= {3} = C

Q‟ = {A, B, C} ;

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

- Consider C:

+ ε-closure( (C, a)) = ε-closure( (3, a)) =

+ ε-closure( (C, b)) = ε-closure( (3, b)) =

- F‟ = {B, C}

So D = < Q‟, ‟, ‟, q‟ 0 , F‟ >. In which: Q' = {A, B, C} ;

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

‟: ‟(A, a)) = B; ‟(A, b)) = A; ‟(B, a) = B; '(B, b) = C

F' = {B, C}.

Transfer graph of automaton D

Start

A

a

B

b

C

b a

Figure 2.11. 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 = ε-closure(q 0 ) = ε-closure(0) = {0, 1} = A;

- ‟ = {a, b};

- Determine Q' and '

Step

Mark T | a i | B = ε-closure( (T, a i )) | Bsung in Q' | Add in ‟ | |

Kt | {0, 1} | A | |||

first | A | a | {1, 2, 3} | B | ‟(A, a) = B |

b | {0, 1} | ‟(A, b) = A | |||

2 | B | a | {1, 2, 3} | ‟(B, a) = B | |

b | {3} | C | '(B, b) = C | ||

3 | C | a | | ||

b | |

Table 2.7. Algorithm simulation

- Determine F' = {B, C}

b) Consider the finite Automata M = < Q, , , q 0 , F > non-deterministic with displacement.

With Q = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ; q 0 = 0 ; F = 10 ; = a,b ; function

shown in figure 2.15.

We can check that the set of languages predicted by the finite Automator M is the set N(M) = (a b) * abb.

2

a

3

Start

0

first

6

7

a

8

b

9

b

4

b

5

ten

Figure 2.12. Represent automata graphically

To build a deterministic finite automaton D that recognizes the same language as Automat M, we use the above algorithm.

- Calculate q‟ 0 = ε-closure(q 0 ) = ε-closure(0) = 0, 1, 2, 4, 7 = A;

- ‟ = {a, b};

- Determine Q' and ':

Step

Mark T | a i | B = ε-closure( (T, a i )) | Add to Q' | Add to ' | |

Kt | {0, 1, 2, 4, 7} = A | A | |||

first | A | a | {1, 2, 3, 4, 6, 7, 8} = B | B | ‟(A, a) = B |

b | {1, 2, 4, 5, 6, 7} = C | C | '(A, b) = C | ||

2 | B | a | {1, 2, 3, 4, 6, 7, 8} = B | ‟(B, a) = B | |

b | {1, 2, 4, 5, 6, 7, 9} = D | D | ‟(B, b) = D | ||

3 | C | a | {1, 2, 3, 4, 6, 7, 8} = B | ‟(C, a) = B | |

b | {1, 2, 4, 5, 6, 7} = C | ‟(C, b) = C | |||

4 | D | a | {1, 2, 3, 4, 6, 7, 8}= B | ‟(D, a) = B | |

b | {1, 2, 4, 5, 6, 7, 10} = E | E | ‟(D, b) = E | ||

5 | E | a | {1, 2, 3, 4, 6, 7, 8}= B | ‟(E, a) = B | |

b | {1, 2, 4, 5, 6, 7} = C | ‟(E, b) = C |

Table 2.8. Algorithm simulation

- Determine F' = {E}

b

C

b

a

a

b

Start

A

a

B b

D

b

E

aa _

Figure 2.13. Represent automata graphically

Attention:

NFA is a special case of NFA . So we can still use the above algorithm to convert NFA to DFA. However, in this case there is always ε-closure(T) = T with T Q. Therefore, a specific algorithm can be given in this case as follows.

3) Algorithm to transform NFA into DFA

Input: NFA M = < Q, , , q 0 , F >.

Output: DFA D = < Q‟, ‟, ‟, q‟ 0 , F‟ >; L( M) = L(D).

Process:

Step 1: Determine q' 0 ; ‟

- ‟ = ;

- Calculate q' 0 : A = q 0 ;

- Put A into the state Q' and consider it as an unmarked state T. Step 2: Determine Q' and '

If in Q' there is an unmarked state T, then mark T

- For each a ‟ performed

+ Calculate B = (T,a);

+ If B is a new state that does not exist in Q', then put B in Q';

+ Insert into the table the transfer function ‟: ‟(T, a) = B.

Step 3: Repeat step 2 if Q's status is still unchecked. Step 4: F‟ = {A Q‟ / A F }

Step 5: D = <Q‟, ‟, ‟, q‟ 0 , F‟>