Description

10 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
15 points
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.
c. Your password must contain at least one alphabetic character, one integer, and one punctuation.
Page 2 of 2