diff -r 33b3e790e1d4 -r 5e070fb0332a hws/hw05.tex
--- 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.