Looking for a Unsorted Math Worksheet Templates? Download it for free!

Exercises On Grammars And Regular Expressions Worksheet With Answer Key - Olena Gryn, Louisiana State University, 2006 Page 2

Exercise 1 on slide 13

For each of the following regular expressions give two strings that are members of the language

it represents and give two that are not:

1) a

∗

2) a(ba)

∗

Solution

1) aaabb and a are members, aba and ba are not members.

2) aa and abababaa are members, a and ababa are not members.

Exercise 2 on slide 13

Give a regular expression for the intersection, union, and concatenation respectively of the two

languages: A = {w ∈ {0, 1}

: w begins with 11} and B = {w ∈ {0, 1}

: w ends with 00}

∗

Solution

a) A ∩ B = 11(1 ∪ 0)

∗

b) A ∪ B = (11(1 ∪ 0)

) ∪ ((1 ∪ 0)

∗

00)

a) AB = 11(1 ∪ 0)

∗

Exercise 3 on slide 13

Give a regular expression for decimal digits.

Solution

(0 ∪ (1 ∪ (2 ∪ (3 ∪ (4 ∪ (5 ∪ (6 ∪ (7 ∪ (8 ∪ 9)))))))))

Exercise 4 on slide 13

Let R be a regular expression over some set.

a) Do (R ∪ ∅) and (R ) denote the same set?

b) What set does (R ∪ ) represent?

c) What set does (R∅) represent?

Solution

a) (R ∪ ∅) is R since ∅ does not add anything to their union, and (R ) means appending nothing

to all strings in R which is also R, hence they are the same (by Jens Christian Godskesen).

b) (R ∪ ) represents the set R and empty string.

c) (R∅) represents R.

Exercises On Grammars And Regular Expressions Worksheet With Answer Key - Olena Gryn, Louisiana State University, 2006 Page 2