--- a/hws/hw05.tex Tue Oct 31 12:52:36 2023 +0000
+++ b/hws/hw05.tex Sat Nov 04 18:28:09 2023 +0000
@@ -40,6 +40,11 @@
\sim r$
\end{center}
+\solution{
+ There is the obvious solution $\sim{}\ZERO$, but also $a + \sim{}a$ would work.
+}
+
+
%\item Assume the delimiters for comments are \texttt{$\slash$*}
%and \texttt{*$\slash$}. Give a regular expression that can
%recognise comments of the form
@@ -58,7 +63,7 @@
$r^+$ & (one or more matches)\\
$r^?$ & (zero or one match)\\
$r^{\{n\}}$ & (exactly $n$ matches)\\
-$r^{\{m, n\}}$ & (at least $m$ and maximal $n$ matches, with the\\
+$r^{\{m.. n\}}$ & (at least $m$ and maximal $n$ matches, with the\\
& \phantom{(}assumption $m \le n$)\\
\end{tabular}
\end{center}
@@ -69,6 +74,20 @@
$r ::= \ZERO \;|\; \ONE \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$
\end{center}
+\solution{
+ $r^+ \dn r\cdot r^*$\\
+ $r^? \dn r + 1$\\
+ $r^{\{0\}} = \ONE$\\
+ $r^{\{n\}} \dn r\cdot r^{\{n-1\}}$\\
+ $r^{\{..n\}} \dn (r^?)^{\{n\}}$\\
+ $r^{\{n..m\}} \dn r^{\{..m-n\}}\cdot r^{\{n\}}$\\
+
+ BTW, $r^{\{n..m\}}$ cannot be defined in terms of $r^{\{n..\}} \;\&\; r^{\{..m\}}$ where $\&$ is
+ the intersection operator I introduced this year. For example assume $r=aaa + aaaaaaa$, then
+ $r^{\{4..6\}}$ cannot match 21 a's, but $r^{\{4..\}} \;\&\; r^{\{..6\}}$.
+ }
+
+
\item Give the regular expressions for lexing a language
consisting of identifiers, left-parenthesis \texttt{(},
right-parenthesis \texttt{)}, numbers that can be either
@@ -88,6 +107,10 @@
Observe the maximal munch rule and the priorities of your regular
expressions that make the process of lexing unambiguous.)
+\solution{
+ The first two strings can be lexed. But not the last ($/$ is not part of the language).
+}
+
\item Suppose the following context-free grammar $G$
\begin{plstx}[margin=1cm]
@@ -109,6 +132,15 @@
\item[$\bullet$] $baa$
\end{itemize}
+\solution{
+ The first and the last cannot be matched. Maybe it is a good exercise to
+ write down the derivations for the rest.
+
+ BTW, the language recognised by this grammar is strings consisting of
+ a's and b's where there are equal or more number of b's than a's (including the
+ empty string).
+}
+
\item Suppose the following context-free grammar
\begin{plstx}[margin=1cm]
@@ -117,7 +149,11 @@
\end{plstx}
Describe which language is generated by this grammar.
-
+
+\solution{Palindromes with the same number of a's and b's, including
+ the empty string}
+
+
\item Remember we have specified identifiers with regular expressions as
strings that start with a letter followed by letters, digits and
underscores. This can also be specified by a grammar rule or rules.