Write regular expressions for the following character sets:

$($a$)$ All strings of lowercase letters that begin and end in a

$($b$)$ All strings of lowercase letters that do not start with a zero

$($c$)$ All strings of digits such that all the $2$s occur before the $9$s

$[3]$

$[3]$

$[4]$

Consider the following grammar:

::$=.$

::$=|$ ;

::$=$

::$=$ :$=$

::$=$ a $|$ b $|$ c

::$=9$

Give a derivation of b :$=9$;c :$=9.$ from the start symbol $.$

$[10]$

Consider the following grammar representing simplified LISP$-$like expressions

lexp $->$ atom $|$ list

atom $->$ number $|$ identifier

list $->($lexp$-$seq$)$

lexp$-$seq $->$ lexp$-$seq lexp $|$ lexp

Write a leftmost and rightmost derivation for the string $($a $23($m x y$)).$

$[20]$

Consider whether the following grammar is ambiguous. Use an example of your choice to prove your answer.

lexp $->$ number $|($op lexp$-$seq$)$

op $->+|-|*$

lexp$-$seq $->$ lexp$-$seq lexp $|$ lexp

$[10]$

A calculator accepts commands according to the following EBNF grammar:

Command ::$=$ Expression $=$

Expression ::$=$ Numeral $((+|-|*)$ Numeral$)*$

Numeral ::$=$ Digit Digit$*$

Digit ::$=0|1|2|3|4|5|6|7|8|9$

Construct a recursive$-$descent parser for a calculator command. The terminal symbols should be individual characters.

$[50]$