Question

Define a spooky expression as follows:
(a) αεΣ
(b) 4
(c)
(d) Sin S, where S, and S2 are spooky expressions intersection)
(e) S; where S, is a spooky expression (complement)
(b) Si S2 where S, and S2 are spooky expressions (concatenation)
(g) Si where S, is a spooky expression (Kleene Star)
In the spirit of Halloween, we will prove that a language L is regular if and only if it is described by a
spooky expression.
(a) Prove that if L is regular, then L can be described by a spooky expression. (Hint: Start with a
regular expression for L.)
(b) Prove that if L is described by a spooky expression, L is regular. (Hint: explain how to inductively
construct a machine for L. You do not need a formal description.)
Note: At first glance a spooky expression sure looks a lot like a regular expression, but its definition
is technically different, and thus you should not assume that spooky expressions describe regular
languages just because regular expressions do.

Answer 1

described by a spooky expression. (Hint: Start with a

regular expression for L.)

(b) Prove that if L is described by a spooky expression, L is regular. (Hint: explain how to inductively

construct a machine for L. You do not need a formal description.)

Note: At first glance a spooky expression sure looks a lot like a regular expression, but its definition

is technically different, and thus you should not assume that spooky expressions describe regular

languages just because regular expressions do.

definition

is technically different, and thus you should not assume that spooky expressions describe regular

languages just because regular expressions do.