Part I: Defining Program Syntax Exercises $(20$ Points$)$

Give a BNF grammar for each of the languages below. For example, a correct answer for $$the set of all strings consisting of zero or more concatenated copies of the string $$ab$$ would be this grammar:

::$=$ ab $|$

There are often many correct answers.

$(2$ points$)$ The set of all strings consisting of one or more instances of the letter a$.$

$(3$ points$)$ Show that your grammar can derive the following sentences:

a

aa

aaa

$(2$ points$)$ The set of all strings consisting of one or more instances of the letter a with a semicolon after each one.

$(3$ points$)$ Show that your grammar can derive the following sentences:

a;

a; a;

a; a; a;

$(2$ points$)$ The set of all strings consisting of an uppercase letter followed by zero or more additional characters, each of which is either an uppercase letter or one of the digits $0$ through $9.$

$(3$ points$)$ Show that your grammar can derive the following sentences:

A

AA

A$1$

AA$1$

A$1$A

$(2$ points$)$ The set of all strings consisting of an open bracket $($the symbol $[)$ followed by a list of one or more digits separated by commas, followed by a closing bracket $($the symbol $]).$ Note that the digits are $0$ through $9.$

$(3$ points$)$ Show that your grammar can derive the following sentences:

$[0]$

$[0,1]$

$[0,1,2]$