The operands in our language regular expressions are single letters or (epsilon). The operators are:

| means "or" (alternation)

writing two or more things next to each other means "followed by" (catenation)

* means "zero or more" (closure or iteration)

+ means "one or more" (positive closure)

( ) are used for grouping

In a regular expression, * and + have the same, highest precedence, "followed by" has middle precedence, and | has the lowest precedence. All of the operators are left associative.

Below are 5 incorrect CFGs for the language of regular expressions. For each CFG, do one of the following:

a. Give one string that is a legal regular expression (given our definition above), but is not in the language of the CFG.

b. Give one string that is not a legal regular expression (given our definition above), but is in the language of the CFG.

c. Show that the CFG is ambiguous by drawing two different parse trees for some string in the language of the CFG.

For cases (a) and (b), be sure to say which of the two cases you are illustrating.

Note that the terminals are LTR, EPS, OR, STAR, PLUS, LPAR, and RPAR. Note also that there is a difference between the terminal EPS (which represents the token epsilon in our language of regular expressions) and the symbol (which is used on the right-hand-side of a grammar production indicating the non-terminal on the left-hand-side derives an empty sequence of symbols).

CFG 1:

expr  expr OR term | term term  term item | item factor  item STAR | item PLUS | item item  LTR | EPS | LPAR expr RPAR

CFG 2:

expr  expr OR term | term term  term item | item item  expr STAR | expr PLUS | LTR | EPS | LPAR expr RPAR

CFG 3:

expr  LPAR expr RPAR | term term  term OR factor | factor factor  factor item | item item  item STAR | item PLUS | LTR | EPS

CFG 4:

expr  expr OR term | term term  term item |  item  item STAR | item PLUS | LTR | EPS | LPAR expr RPAR 

CFG 5:

expr  expr OR term | term term  term item | LPAR expr RPAR | item item  item STAR | item PLUS | LTR | EPS