# Describe the Process of Guessing and Recognizing Strings

5

 {2, 3} b 6 {2, 3} b 7 {2, 3} \$

Maybe you are interested!

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‟>