# HG changeset patch # User Christian Urban # Date 1414858745 0 # Node ID c29853b672fb722c2e86fb808bfaf78b0ae55112 # Parent ca349cfe3474315cc5f6f0da75f41e8f33e4576d updated hws diff -r ca349cfe3474 -r c29853b672fb hws/hw01.pdf Binary file hws/hw01.pdf has changed diff -r ca349cfe3474 -r c29853b672fb hws/hw01.tex --- a/hws/hw01.tex Sat Nov 01 15:06:41 2014 +0000 +++ b/hws/hw01.tex Sat Nov 01 16:19:05 2014 +0000 @@ -42,7 +42,9 @@ \item How is the power of a language defined? (Hint: There are two rules, one for $\_^0$ and one for $\_^{n+1}$.) -\item Let $A = \{[], [a], [b], [c]\}$. How many strings are in $A^4$? +\item Let $A = \{[a], [b], [c], [d]\}$. How many strings are in $A^4$? + Consider the case of $A^4$ where one of the strings in $A$ is the + empty string. \item How many regular expressions are there to match the string $abc$? How many if they cannot include $\epsilon$ and $\varnothing$? diff -r ca349cfe3474 -r c29853b672fb hws/hw02.pdf Binary file hws/hw02.pdf has changed diff -r ca349cfe3474 -r c29853b672fb hws/hw02.tex --- a/hws/hw02.tex Sat Nov 01 15:06:41 2014 +0000 +++ b/hws/hw02.tex Sat Nov 01 16:19:05 2014 +0000 @@ -69,6 +69,32 @@ \item Do $(a + b)^* \cdot b^+$ and $(a^* \cdot b^+) + (b^*\cdot b^+)$ define the same language? + +\item Define the function $zeroable$ by recursion over regular + expressions. This function should satisfy the property + + \[ + zeroable(r) \;\;\text{if and only if}\;\;L(r) = \varnothing\qquad(*) + \] + + The function $nullable$ for the not-regular expressions can be defined + by + + \[ + nullable(\sim r) \dn \neg(nullable(r)) + \] + + Unfortunately, a similar definition for $zeroable$ does not satisfy + the property in $(*)$: + + \[ + zeroable(\sim r) \dn \neg(zeroable(r)) + \] + + Find out why? + +\item Give a regular expressions that can recognise all strings from the + language $\{a^n\;|\;\exists k. n = 3 k + 1 \}$. \end{enumerate} \end{document} diff -r ca349cfe3474 -r c29853b672fb hws/hw03.pdf Binary file hws/hw03.pdf has changed diff -r ca349cfe3474 -r c29853b672fb hws/hw03.tex --- a/hws/hw03.tex Sat Nov 01 15:06:41 2014 +0000 +++ b/hws/hw03.tex Sat Nov 01 16:19:05 2014 +0000 @@ -159,6 +159,12 @@ this automaton. (Hint: If you use Brzozwski's method, you can assume Arden's lemma which states that an equation of the form $q = q\cdot r + s$ has the unique solution $q = s \cdot r^*$.) + +\item If a non-deterministic finite automaton (NFA) has +$n$ states. How many states does a deterministic +automaton (DFA) that can recognise the same language +as the NFA maximal need? + \end{enumerate} \end{document} diff -r ca349cfe3474 -r c29853b672fb hws/hw04.pdf Binary file hws/hw04.pdf has changed diff -r ca349cfe3474 -r c29853b672fb hws/hw04.tex --- a/hws/hw04.tex Sat Nov 01 15:06:41 2014 +0000 +++ b/hws/hw04.tex Sat Nov 01 16:19:05 2014 +0000 @@ -67,7 +67,11 @@ that can recognise any character, and a regular expression \texttt{NOT} that recognises the complement of a regular expression.) - +\item How many basic regular expressions are there to match the string + $abcd$? (ii) How many if they cannot include $\epsilon$ and + $\varnothing$? (iii) How many if they are also not allowed to + contain stars? (iv) How many if they are also not allowed to contain + $\_ + \_$? %\item (Optional) The tokenizer in \texttt{regexp3.scala} takes as %argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so diff -r ca349cfe3474 -r c29853b672fb hws/hw05.pdf Binary file hws/hw05.pdf has changed diff -r ca349cfe3474 -r c29853b672fb hws/hw05.tex --- a/hws/hw05.tex Sat Nov 01 15:06:41 2014 +0000 +++ b/hws/hw05.tex Sat Nov 01 16:19:05 2014 +0000 @@ -12,6 +12,42 @@ \section*{Homework 5} \begin{enumerate} +\item Consider the basic regular expressions + +\begin{center} +$r ::= \varnothing \;|\; \epsilon \;|\; 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. + +\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 \;|\; + c \;|\; + r_1 + r_2 \;|\; + r_1 \cdot r_2 \;|\; + r^* \;|\; + \sim r$ +\end{center} + +\item Assume the delimiters for comments are \texttt{$\slash$*} +and \texttt{*$\slash$}. Give a regular expression that can +recognise comments of the form + +\begin{center} +\texttt{$\slash$*~\ldots{}~*$\slash$} +\end{center} + +where the three dots stand for arbitrary characters, but not +comment delimiters. + \item Define the following regular expressions \begin{center} @@ -24,15 +60,32 @@ \end{tabular} \end{center} -in terms of the usual regular expressions +in terms of the usual basic regular expressions \begin{center} $r ::= \varnothing \;|\; \epsilon \;|\; 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{*}. +Decide whether the following strings +can be lexed in this language? -\item Recall the definitions for $Der$ and $der$ from the lectures. +\begin{enumerate} +\item \texttt{"(a3+3)*b"} +\item \texttt{")()++-33"} +\item \texttt{"(b42/3)*3"} +\end{enumerate} + +In case they can, give the corresponding token sequences. (Hint: +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 \[ @@ -40,6 +93,7 @@ \] holds. + \end{enumerate} \end{document} diff -r ca349cfe3474 -r c29853b672fb hws/hw06.pdf Binary file hws/hw06.pdf has changed