CS421 - Yoshii - HW 3
Regular Expressions and DFAs and the Scanner
======
DUE: Week 8– 1st lecture at the beginning of lecture
TOTAL: 52 pts
** Group #:
** Name1:
** Attached drafts for which problems?
** Came to the meeting(s) to assemble work together?
** Name2:
** Attached drafts for which problems?
** Came to the meeting(s) to assemble work together?
** Name3:
** Attached drafts for which problems?
** Came to the meeting(s) to assemble work together?
------
Problem 1 [8pts (12pts with extra)] Token --> RE
------
Your first task as a scanner designer is to turn each token into
a regular expression.
First describe what you want to express in English.
Then, give the RE for it.
e.g. {a^n b^m | n >= 0 m >= 1}
English: 0 or more a's followed by 1 or more b's
RE: a^* b^+
Alphabet is {a,b}. OK to use e for empty strings.
A) {a^2n b^2m+1 | n >= 0 ; m >= 0 }
Describe the language completely in English:
RE for it:
B) {w | w has at least one pair of consecutive a's }
Describe the language completely:
RE for it:
EXTRA credit:
C) {w | w has no pair of consecutive b's }
HINT: every b must be followed by a but the string may end in b.
Describe the language completely:
RE for it:
------
Problem 2 [12pts] RE -> NFA-e
------
Then the 2nd step in creating a scanner.
Give NFA-e for the following REs. Show component machines first
and then show all steps of connecting these machines using the methods
described in week5.a notes.
Hand-drawing is OK.
Do not use any simplification. Having many e-moves is what we want.
For b(a|bb)^*
No state numbers are needed
M1 for b:
M2 for a:
M3 for bb: by connecting M1’s
Start combining them now (show all states):
M4 for (a|bb): M2 and M3
M5 for (a|bb)^*: modify M4
The whole thing for b(a|bb)^* (make sure state numbers are unique)
Put M1 in front of M4 and give state numbers
------
Problem 3 [12pts] NFA-e -> NFA
------
The 3rd step in creating a scanner.
Remove e-moves from the following:
e q2 --- a --- q3 ------e ------
q0- e - q1 q8 -- e - q9
e q4 --- b ---- q5 --- e --- q6 ---- b ---- q7 - e -
i.e.
Trs(q0,e) = q1
Trs(q1,e) = q2
Trs(q1,e) = q4
Trs(q2,a) = q3
Trs(q3,e) = q8
Trs(q4,b) = q5
Trs(q5,e) = q6
Trs(q6,b) = q7
Trs(q7,e) = q8
Trs(q8,e) = q9 final
1) Please compute Trs-e for each state-symbol pair: [8pts]
Trs-e(q0,e*ae*) = {}
Trs-e(q0,e*be*) = {}
Trs-e(q1,e*ae*) = {}
Trs-e(q1,e*be*) = {}
Trs-e(q2,e*ae*) = { }
Trs-e(q2,e*be*) = { }
etc. Continue for all state-symbol pair.
2) Then draw the NFA based on the above (hand-drawing is OK):[4ptds]
------
Problem 4: [8pts] NFA -> DFA
------
The very last step.
Before we can implement a scanner, your machine has to become deterministic.
NFA: q0 loop on 0/1
q0 --- 0 ---> q1
q1 loop on 0/1
q1 --- 1 ---> q2
q2 loop on 0/1. q2 is final.
A) DFA: Trs(<q0>, 0) = < q0q1 >
Trs(<q0>, 1) = < q0 >
Then from each resulting state, give Trs on 0 and 1.....
...... finish this until there are no more new states
-- List the Trs's here: [4pts]
-- Then draw the DFA and mark all final states:[2pts]
C) What is the language accepted by this DFA? Give its RE.[2pts]
======
Problem 5: Implementation [12pts]
======
Divide the work as specified:
Look at the file fa.C.
Compile it and run it with
abbb and
abb to see what it does.
This program accepts a b^+
Change this program with new transitions (follow my comments)
to accept the following:
function ident l ( l + d + _ )^* to be done by member A
fundtion real d^* . d^+ to be done by member B
function int d^+ to be done by member C
function operator <= | >= to be done by member D if available
Note: l can be either a or b
d can be either 2 or 3
You do not have to handle other digits and characters.
THE FOLLOWING TO BE DONE by the ENTRE GROUP together:
------
main() should accept a string from the user
and then call ident_token, real_token and int_token(and operator_token) in this order until
one of them returns TRUE.
Cout the token type
e.g. "The string is IDENT"
If all machines returned FALSE,
Cout “Lex error: the string is not in my language.”
Must test the program on: (done by the entire group)
ab_2a - ident
.23 - real
23.3 - real
23 - int
ab&c - bad
23.6 - bad
2a3 - bad
22..2 - bad
23. – bad
<= - operator (for the 4member teams)
>= - operator
< - bad
= - bad
Each function must have the authors' name(s) in the header comment.
Submit the program and the output (screen dump) for the test cases.