- Build an Automat to guess r 5 =(r 7 ) *
Maybe you are interested!
-
When Should a Healthy Child Get the First Dose of Hepatitis B Vaccine? (Check Only One) -
Two Elements A And B Are In Two Consecutive Main Groups In The Periodic System. In Their Pure Substance State, A And B Do Not React With Each Other. Total Number Of Protons -
Effects of Voltage (A); Kcl Concentration (B); Electrolysis Time (C); and Stirring Time (D) on Hg Signal (Ii) -
Equations Expressing the Relationship Dt/d1,3 In the Form: Dt = A + B.d1,3 At Different Ages -
Hplc Spectrum of 5-Fu (A) and Hplc Spectrum of Pns-Gptms-Cs-Mpeg System Carrying Released 5-Fu (B)
2
a
3
Start
0
1
6
7
4
b
5
Figure 2.24. The guessing automaton r 5 = (a+b) *
Do the same with r 6 = a; r 3 = r 5 r 6 ; r 4 = b; r 1 = r 3 r 4 ; r 2 = b; r = r 1 r 2 . Get the result as shown below:
2
a
3
Start
0
1
6
7
a
8
b
9
b
10
4
b
5
Figure 2.25. The guessing automaton r=(a b) * abb
QUESTIONS AND EXERCISES CHAPTER 2
2.1. - State the concepts: word cards, vocabulary values, vocabulary patterns; give examples.
- State the methods of representing word cards; give illustrative examples.
2.2. State the position, function and task of the vocabulary analysis stage.
2.3. State the techniques for reading source programs using buffers.
2.4. State the algorithm for lexeme recognition using deterministic automaton DFA. Run an illustrative example
2.5. State the algorithm for lexeme recognition using non-deterministic automaton NFA. Run an illustrative example.
2.6. State the algorithm for lexeme recognition using non-deterministic automaton NFA . Run the illustrative example.
2.7. State the algorithm to transform a non-deterministic automaton NFA into a deterministic automaton DFA that recognizes the same language. Give an illustrative example.
2.8. State the algorithm to transform a non-deterministic automaton NFA into a deterministic automaton DFA that recognizes the same language. Give an illustrative example.
2.9. State Thomson's algorithm to build an automaton that recognizes a regular expression. Give an illustrative example.
2.10. Identify the lexical values and indicate the tokens in the following Pascal program segments:
function max2 (i, j : integer) : integer;
{ Returns the larger integer between i and j } begin
If i > j then max2 : = i
else max2 : = j;
end;
2.11.
Identify the lexical values and indicate the tokens in the following Pascal program segments:
PROGRAM GPTB2;
VAR a,b,c,x1,x2: real; FUNCTION Delta: real;
Begin
Delta:= Sqr(b) - 4*a*c; End;
PROCEDURE Ptb2;
VAR r: real; {r is a variable} BEGIN
BEGIN
r := Sqrt (delta); x1 := (-br)/(2*a);
x2 := (-b+r)/(2*a); END;
END;
(* program body *) BEGIN
REPEAT
Write(„a=‟); readln(a); UNTIL a<>0 ;
Write('b='); readln(b);
Write(„c=‟); readln(c); If (delta < 0) Then
Writeln ( 'PT Vo Nghiem'); If delta = 0 Then
Writeln ( 'PT has the same meaning x1 = x2 =',x1:1:2); If delta > 0 Then
Begin
Ptb2;
Writeln ( 'PT has 2 meanings: x1=',x1:1:2,'x2=',x2:1:2); Writeln ( 'x2 =', x2:1:2);
End;
Readln;
END.
2.12. In the high-level programming language Pascal, given a number of word tags expressed verbally as follows:
1) An unsigned integer is a string that starts with a number, followed by zero, one, or more digits.
2) An integer is a string that starts with a sign, followed by an unsigned integer; the sign is either + or - or no character.
3) A fixed-point real number is a string that starts with a sign part; then an integer part, then a decimal part; the decimal part may or may not be present; if there is a decimal part, the two parts are separated by a period. The integer part and the decimal part are unsigned integers.
4) A floating point number is a string that starts with an integer, followed by a period, then an unsigned integer, followed by an exponent. The exponent starts with the letter E, followed by an integer.
5) Arithmetic operators are one of the operations +, -, * , / , **
6) Whitespace is one or more blank characters or a tab or newline character.
7) A name is a string of characters, starting with a letter; followed by zero, one, or more letters or digits. Letters or digits may be replaced by underscores.
a) Represent each word tag above using a regular expression and indicate the word tag, vocabulary pattern, and vocabulary value of each word.
b) Build a transition diagram to identify each token above.
2.13. Given Automat M:
Start
1
q 10
0 1
q 2 q 3
0, 1
q 4
0
1
Figure BT 2.13
a) Identify the components of automaton M. What type of automaton is it? Why?
b) Use the algorithm to recognize lexemes using the Automat corresponding to M; Check if M can recognize the following lexemes?
1) 1010101100$
2) 110011101$
3) 000000000$
c) Indicate the language recognized by M
2.14. For Automat M
1
0
1
A
0
1
0
Start
B
0
C
1
D
Figure bt 2.14
a) List the components of M
b) Use the lexeme prediction algorithm corresponding to the above automaton to predict the words:
+ w = 1110011$
+ w = 100001110$
+ w = 111100000$
c) Indicate the language recognized by M
d) Build a DFA that recognizes the same language as Automat M
2.15. For Automat M
a
b
1
a
2
b
Start
0
b
a
b
5
6
3
a
4
b
b
Figure BT 2.15
a) List the components of M
b) Use the lexeme prediction algorithm corresponding to the above automaton to predict the words:
+ w = baaaabb$
+ w = aabbbab$
+ w = aababbbb$
c) Indicate the language recognized by M
d) Build a DFA that recognizes the same language as Automat M
2.16. For Automat M.
Start
q 0
0
q 10
q 2
1
q
3
1
0
Figure BT 2.16
a) Identify the components of automaton M. What type of automaton is it? Why?
b) Use the algorithm to recognize lexemes using the Automat corresponding to M; Check if M can recognize the following lexemes?
1) 00011111$
2) 01111110$
3) 000000001$
c) Indicate the language recognized by M
d) Build a DFA that recognizes the same language as Automat M
2.17. For Automat M.
Start
1
0
q 0 0 q 1
0 0
1
q 2 q 3
Figure BT 2.17
a) Identify the components of automaton M. What type of automaton is it? Why?
b) Use the algorithm to recognize lexemes using the Automat corresponding to M; Check if M can recognize the following lexemes?
1) 000101001$
2) 01010100$
3) 0000000010$
c) Indicate the language recognized by M
d) Build a DFA that recognizes the same language as Automat M
2.18. For Automat M
b
a
1
a
b
2
Start
0
b
3
b
4
Figure BT 2.18
a) List the components of M
b) Use the lexeme prediction algorithm corresponding to the above automaton to predict the words:
1) w = bbbaaa$
2) w = bbaaab$
c) Indicate the language recognized by M
d) Build a DFA that recognizes the same language as Automat M
2.19. For Automat M
a
1
a
2
Start
0
b
a
5
6
3
4
b
b
Figure BT 2.19
a) List the components of M
b) Use the lexeme prediction algorithm corresponding to the above automaton to predict the words:
+ w = aaaaab
+ w = bbbbab
c) Indicate the language recognized by M
d) Build a DFA that recognizes the same language as Automat M
2.20. For Automat M
1
Start
A
1
1
B
0
C
1
D
Figure BT 2.20
a) List the components of M
b) Use the lexeme prediction algorithm corresponding to the above automaton to predict the words:
+ w = 111110
+ w = 111111
c) Indicate the language recognized by M
d) Build a DFA that recognizes the same language as Automat M
2.21. For Automat M
a
1
b
2
Start
b
0
3
a
4
a
a
a) List the components of M
b
Figure BT 2.21
b) Use the lexeme prediction algorithm corresponding to the above automaton to predict the words:
+ w = bbbaaaa
+ w = aaaaabba
c) Indicate the language recognized by M
d) Build a DFA that recognizes the same language as Automat M