equal
deleted
inserted
replaced
7 \section*{Homework 4} |
7 \section*{Homework 4} |
8 |
8 |
9 \HEADER |
9 \HEADER |
10 |
10 |
11 \begin{enumerate} |
11 \begin{enumerate} |
|
12 |
|
13 \item Given the regular expressions |
|
14 |
|
15 \begin{center} |
|
16 \begin{tabular}{ll} |
|
17 1) & $(ab + a)\cdot (\ONE + b)$\\ |
|
18 2) & $(aa + a)^*$\\ |
|
19 \end{tabular} |
|
20 \end{center} |
|
21 |
|
22 there are several values for how these regular expressions can |
|
23 recognise the strings (for 1) $ab$ and (for 2) $aaa$. Give in each case |
|
24 \emph{all} the values and indicate which one is the POSIX value. |
|
25 |
12 |
26 |
13 \item If a regular expression $r$ does not contain any occurrence of $\ZERO$, |
27 \item If a regular expression $r$ does not contain any occurrence of $\ZERO$, |
14 is it possible for $L(r)$ to be empty? Explain why, or give a proof. |
28 is it possible for $L(r)$ to be empty? Explain why, or give a proof. |
15 |
29 |
16 \item Define the tokens and regular expressions for a language |
30 \item Define the tokens and regular expressions for a language |