Question

Write a regular expression defining strings that begin with an a and end with a b and can contain any number (including zero) of c's or d's in the middle. Every c that is in the string must be followed by at least one d.

Construct a deterministic finite state automaton with no more than four states that accepts the language defined by the regular expression in problem 1.

Answer 1

Try
my $pat="^ad*(cd+)*b\$"

Use this pattern to match strings according to the rules specified.

Note that $pat will <i>match</i> a qualifying string, but does not define a string.

Hope someone else can answer the second part.

Answer 2

Explanation of the pattern follows:

^a specifies the string begins with "a"
b\$ specifies that the string ends with "b"
d* allows 0 or more embedded d's.
(cd+)* requires a "c" to be followed by at least one "d". This can happen 0 or more times.