Describe the Process of Guessing and Recognizing Strings

5

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

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

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

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