360 $\ONE \cdot r$ & $\mapsto$ & $r$\\ |
360 $\ONE \cdot r$ & $\mapsto$ & $r$\\ |
361 $\sum\;[r_1,..,r_n]$ & $\mapsto$ & $\sum\;(\texttt{(flts + distinct)}[simp(r_1),..,simp(r_n)])$\\ |
361 $\sum\;[r_1,..,r_n]$ & $\mapsto$ & $\sum\;(\texttt{(flts + distinct)}[simp(r_1),..,simp(r_n)])$\\ |
362 \end{tabular} |
362 \end{tabular} |
363 \end{center} |
363 \end{center} |
364 |
364 |
365 The last case is as follows: first apply $simp$ to all regular expressions |
365 The last case is as follows: first apply $simp$ to all regular |
366 $r_1,.. ,r_n$; then flatten the resulting list using \texttt{flts}; |
366 expressions $r_1,.. ,r_n$; then flatten the resulting list using |
367 finally remove all duplicates in this list (this can be done in Scala |
367 \texttt{flts}; finally remove all duplicates in this list (this can be |
368 using the function \texttt{\_.distinct}). |
368 done in Scala using the function |
|
369 \texttt{\_.distinct}). \textcolor{red}{When you perform these |
|
370 operations, you end up with three cases, namely where the list is |
|
371 empty, contains a single element and ``otherwise''. These cases |
|
372 should be processed as follows} |
|
373 \begin{center} |
|
374 \textcolor{red}{\begin{tabular}{l@{\hspace{4mm}}c@{\hspace{4mm}}ll} |
|
375 $\sum\;[]$ & $\mapsto$ & $\ZERO$\\ |
|
376 $\sum\;[r]$ & $\mapsto$ & $r$\\ |
|
377 $\sum\;rs$ & $\mapsto$ & $\sum\;rs$ & ``otherwise''\\ |
|
378 \end{tabular}} |
|
379 \end{center} |
|
380 |
|
381 |
369 |
382 |
370 For example the regular expression |
383 For example the regular expression |
371 \[(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot (r_4 \cdot \ZERO)\] |
384 \[(r_1 + \ZERO) \cdot \ONE + ((\ONE + r_2) + r_3) \cdot (r_4 \cdot \ZERO)\] |
372 |
385 |
373 simplifies to just $r_1$. \textbf{Hint:} Regular expressions can be |
386 simplifies to just $r_1$. \textbf{Hint:} Regular expressions can be |