points
Please code up the following functions that extend the utility of our regularexpression implementation in Haskell.
(1) a. occurrences :: Int -> RegEx -> RegEx such that occurrences n r returns a RegEx that would match exactly n occurrences of r.
b. optional :: RegEx -> RegEx such that optional r returns a RegEx that would match either zero occurrences or one occurrence of r.
Page 1 of 2
10 points
Please write a regular expression and draw a finite-state automaton with the fewest states possible that recognize the language L in (2). Assume that a space represents concatenation.
(2) a. Σ={the,very,hungry,caterpillar}
⎧⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪ the caterpillarthe hungry caterpillarthe very hungry caterpillar, , , ⎪⎪⎪⎪⎪⎫⎪⎪⎪⎪⎪⎪⎪
⎪⎪
⎪
b. L =⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪ the very very hungry caterpillarthe very very very hungry caterpillarthe very very very very hungry caterpillar. . . , , , ⎪⎪⎪⎬⎪⎪⎪⎪⎭⎪⎪⎪⎪⎪⎪⎪
⎩⎪
3
15points
Please draw a finite-state automaton with the fewest states possible that recognizes the set of strings described in (3). Please also give the set of transitions as a table.
(3) a. Your password may be any length.
b. Your password may contain alphabetic characters (a–z, A–Z), integers (0–9), punctuation (. ? !), and nothing else.
c. Your password must contain at least one alphabetic character, one integer, and one punctuation.
In your finite-state automaton, you may (and should) use A, I, and P as shorthand to represent any alphabetic character, integer, and punctuation respectively.
Page 2 of 2
