48       $A = \{[a]\}$, $B = \{[]\}$ and $C = \{[a], []\}$}

    50         $A = \{[a]\}$, $B = \{[]\}$ and $C = \{[a], []\}$\medskip

    51 

    52         For equations like 3 it is always a god idea to prove the

    53         two inclusions

    54 

    55         \[

    56           A^* \subseteq  A^* @ A^*   \qquad

    57           A^* @ A^* \subseteq A^*

    58         \]  

    59 

    60         This means for every string $s$ we have to show

    61 

    62         \[

    63           s \in A^*    \;\textit{implies}\;  s \in A^* @ A^* \qquad

    64           s \in A^* @ A^* \;\textit{implies}\;  s \in A^*

    65         \]

    66 

    67         The first one is easy because $[] \in A^*$ and therefore

    68         $s @ [] \in A^* @ A^*$.

    69 

    70         The second one says that $s$ must be of the form $s = s_1 @ s_2$ with

    71         $s_1 \in A^*$ and $s_2 \in A^*$. We have to show that

    72         $s_1 @ s_2 \in A^*$.

    73 

    74         If $s_1 \in A^*$ then there exists an $n$ such that $s_1 \in A^n$, and

    75         if $s_2 \in A^*$ then there exists an $m$ such that $s_2 \in A^m$.\bigskip

    76 

    77 

    78         Aside: We are going to show that

    79 

    80         \[

    81         A^n \,@\, A^m = A^{n+m}  

    82         \]  

    83 

    84         We prove that by induction on $n$.

    85 

    86         Case $n = 0$: $A^0 \,@\, A^m = A^{0+m}$ holds because $A^0 = \{[]\}$

    87         and $\{[]\} \,@\, A^m = A ^ m$ and $0 + m = m$.\medskip

    88         

    89         Case $n + 1$: The induction hypothesis is

    90 

    91         \[ A^n \,@\, A^m = A^{n+m}

    92         \]

    93 

    94         We need to prove

    95 

    96         \[

    97         A^{n+1} \,@\, A^m = A^{(n+1)+m}  

    98         \]

    99 

   100         The left-hand side is $(A \,@\, A^n) \,@\, A^m$ by the definition of

   101         the power operation. We can rearrange that

   102         to $A \,@\, (A^n \,@\, A^m)$.   \footnote{Because for all languages $A$, $B$, $C$ we have $(A @ B) @ C = A @ (B @ C)$.}

   103 

   104         By the induction hypothesis we know that $A^n \,@\, A^m = A^{n+m}$.

   105 

   106         So we have $A \,@\, (A^{n+m})$. But this is $A^{(n+m)+1}$ again if we

   107         apply the definition of the power operator. If we

   108         rearrange that we get $A^{(n+1)+m}$ and are done with

   109         what we need to prove for the power law.\bigskip

   110 

   111         Picking up where we left, we know that $s_1 \in A^n$ and $s_2 \in A^m$. This now implies that $s_1 @ s_2\in A^n @ A^m$. By the power law this means

   112         $s_1 @ s_2\in A^{n+m}$. But this also means $s_1 @ s_2\in A^*$.

   113       }

   103       

   168       \solution{$((ba)^* \cdot (a)^*)^*\,\cdot\,a$}

   108    \solution{No, the first one can match for example abababababbbbb}

   173   \solution{No, the first one can match for example abababababbbbb

   174   while the second can only match for example aaaaaabbbbb or bbbbbbb}

   131       Find a counter example?

   197   Find a counter example?

   198 

   199 

   200   \solution{

   201     Here the idea is that nullable for NOT can be defined as

   202 

   203     \[nullable(\sim r) \dn \neg(nullable(r))\]

   204 

   205     This will satisfy the property

   206     $nullable(r) \;\;\text{if and only if}\;\;[] \in L(r)$. (Remember how

   207     $L(\sim r)$ is defined).\bigskip

   208 

   209     But you cannot define

   210 

   211     \[zeroable(\sim r) \dn \neg(zeroable(r))\]

   212 

   213     because if $r$ for example is $\ONE$ then $\sim \ONE$ can match

   214     some strings (all non-empty strings). So $zeroable$ should be false. But if we follow

   215     the above definition we would obtain $\neg(zeroable(\ONE))$. According

   216     to the definition of $zeroable$ for $\ONE$ this would be false,

   217     but if we now negate false, we get actually true. So the above

   218     definition would not satisfy the property

   219 

   220     \[

   221       zeroable(r) \;\;\text{if and only if}\;\;L(r) = \{\}

   222     \]  

   223     }

   140 number of $a$s or an even number of $b$s.     

   232   number of $a$s or an even number of $b$s.

   233 

   234   \solution{

   235     If the a's and b's are meant to be separate, then this is easy 

   236 

   237     \[a(aa)^* + (bb)^*\]

   238 

   239     If the letters are mixed, then this is difficult

   240 

   241     \[(aa|bb|(ab|ba)\cdot (aa|bb)^* \cdot (ba|ab))^* \cdot (b|(ab|ba)(bb|aa)^* \cdot a)

   242     \]

   243 

   244     (copied from somewhere ;o)

   245 

   246     The idea behind it is essentially the DFA

   247 

   248 \begin{center}    

   249 \begin{tikzpicture}[scale=1,>=stealth',very thick,

   250                     every state/.style={minimum size=0pt,

   251                     draw=blue!50,very thick,fill=blue!20}]

   252   \node[state,initial]   (q0) at (0,2) {$q_0$};

   253   \node[state,accepting] (q1) at (2,2) {$q_1$};

   254   \node[state]           (q2) at (0,0) {$q_2$};

   255   \node[state]           (q3) at (2,0) {$q_3$};

   256 

   257  \path[->]  (q0) edge[bend left] node[above] {$a$} (q1)

   258             (q1) edge[bend left] node[above] {$a$} (q0)

   259             (q2) edge[bend left] node[above] {$a$} (q3)

   260             (q3) edge[bend left] node[above] {$a$} (q2)

   261             (q0) edge[bend left] node[right] {$b$} (q2)

   262             (q2) edge[bend left] node[left]  {$b$} (q0)

   263             (q1) edge[bend left] node[right] {$b$} (q3)

   264             (q3) edge[bend left] node[left]  {$b$} (q1);

   265 \end{tikzpicture}

   266 \end{center}

   267 }