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

Solutions of the exercises on

Grammars and Regular Expressions

Olena Gryn

olg@itu.dk

December, 2006

updated

Exercise 1 on slide 6

What is the language generated by G

= ({a, b, S, T, U }, {a, b}, S, P ) if P is altered to:

S → T

S → bSb

T → aT

T →

Solution

) = {b

: n ≥ 0, m ≥ 0}

L(G

Exercise 2 on slide 6

Make a grammar generating {a

: n ≥ 0}

Solution

= ({a, b, S}, {a, b}, S, P ) with P deﬁned by:

S → aSbb|

Exercise on slide 12

Why is the (inductive) deﬁnition of a regular expression a proper deﬁnition (it seems to be

recursively deﬁned)?

Solution

It is because such deﬁned regular set can be generated by a regular grammar. This follows from

the fact, that every regular set deﬁned by such deﬁnition can be recognized by a ﬁnite-state

automaton. And this can be proved from the fact, that {a},{ }, ∅ are recognized by a ﬁnite-state

automaton, and A

, (A ∪ B), (AB) are recognized by a ﬁnite-state machine whenever A and B

∗

are (see pp. 657-658 in Discrete mathematics and Its Applications, by Rosen).

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