$1\mathrm{.}11$ Exercises

Exercise $1\mathrm{.}1$ Given the regular expression $(b|),$

$($a$)$ Using the derivation rules in Fig. $1\mathrm{.}1,$ show that $L(s)$ contains the string ac$.$

$($b$)$ Find the complete set $L(s).$

$1\mathrm{.}1$ Regular Expressions

$3$

$\backslash$table$[[$Regexp$,$Derivation rules,Informal description$],[$a$,,\backslash$table$[[$The one$-$letter string a$.$ No derivation rule,$],[$as it is already a string.$]]],[,\backslash$table$[[s|t|=>s,,$The empty string.$],[s|t|=>t,,]],\backslash$table$[[$Either $s$ or $t.$ Note that this allows multiple$],[$different derivations.$]]],[st,st=>s^{\text{'}}{t}^{\text{'}},$ if $s=>s^{\text{'}}$ and $t=>t^{\text{'}},\backslash$table$[[$Something derived from $s$ followed by some$-],[$thing derived from $t.]]],[s^{**},s^{**}=>s(s^{**}),\backslash$table$[[$A concatenation of any number $($including $0)],[$of strings derived from $s.$ The number de$-],[$pends on how many times the second rule is$],[$used$.]]]]$

Fig. $1\mathrm{.}1$ Regular expressions and their derivation