diff -r e4afe3f46c29 -r 5d85dc9779b1 hws/hw05.tex --- a/hws/hw05.tex Wed Apr 06 12:18:54 2016 +0100 +++ b/hws/hw05.tex Wed Apr 06 15:55:01 2016 +0100 @@ -18,21 +18,21 @@ \item Consider the basic regular expressions \begin{center} -$r ::= \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$ +$r ::= \ZERO \;|\; \ONE \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$ \end{center} -and suppose you want to show a property $P(r)$ for all regular -expressions $r$ by structural induction. Write down which cases do you -need to analyse. State clearly the induction hypotheses if applicable -in a case. + and suppose you want to show a property $P(r)$ for all + regular expressions $r$ by structural induction. Write + down which cases do you need to analyse. State clearly + the induction hypotheses if applicable in a case. -\item Define a regular expression, written $ALL$, that can match -every string. This definition should be in terms of the -following extended regular expressions: +\item Define a regular expression, written $ALL$, that can + match every string. This definition should be in terms + of the following extended regular expressions: \begin{center} -$r ::= \varnothing \;|\; - \epsilon \;|\; +$r ::= \ZERO \;|\; + \ONE \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; @@ -66,17 +66,17 @@ in terms of the usual basic regular expressions \begin{center} -$r ::= \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$ +$r ::= \ZERO \;|\; \ONE \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$ \end{center} \item Give the regular expressions for lexing a language -consisting of identifiers, left-parenthesis \texttt{(}, -right-parenthesis \texttt{)}, numbers that can be either -positive or negative, and the operations \texttt{+}, -\texttt{-} and \texttt{*}. + consisting of identifiers, left-parenthesis \texttt{(}, + right-parenthesis \texttt{)}, numbers that can be either + positive or negative, and the operations \texttt{+}, + \texttt{-} and \texttt{*}. -Decide whether the following strings -can be lexed in this language? + Decide whether the following strings can be lexed in + this language? \begin{enumerate} \item \texttt{"(a3+3)*b"} @@ -88,14 +88,15 @@ Observe the maximal munch rule and the priorities of your regular expressions that make the process of lexing unambiguous.) -\item (Optional) Recall the definitions for $Der$ and $der$ from the lectures. -Prove by induction on $r$ the property that +\item (Optional) Recall the definitions for $Der$ and $der$ + from the lectures. Prove by induction on $r$ the + property that \[ L(der\,c\,r) = Der\,c\,(L(r)) \] -holds. + holds. \end{enumerate}