1495 

  1496 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  1497 \begin{frame}[c]

  1498 

  1499 \begin{center}

  1500 \begin{tikzpicture}[scale=2,>=stealth',very thick,

  1501                              every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]

  1502   \only<-7>{\node[state, initial] (q0) at ( 0,1) {$\mbox{Q}_0$};}

  1503   \only<8->{\node[state, initial,accepting] (q0) at ( 0,1) {$\mbox{Q}_0$};}                           

  1504   \only<-7>{\node[state] (q1) at ( 1,1) {$\mbox{Q}_1$};}

  1505   \only<8->{\node[state,accepting] (q1) at ( 1,1) {$\mbox{Q}_1$};}

  1506   \node[state] (q2) at ( 2,1) {$\mbox{Q}_2$};

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

  1508                   (q1) edge[bend left] node[above] {\alert{$b$}} (q0)

  1509                   (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)

  1510                   (q1) edge node[above] {\alert{$a$}} (q2)

  1511                   (q2) edge [loop right] node {\alert{$a$}} ()

  1512                   (q0) edge [loop below] node {\alert{$b$}} ()

  1513             ;

  1514 \end{tikzpicture}

  1515 \end{center}\bigskip

  1516 

  1517 \begin{center}

  1518 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}

  1519 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_1\,b +  \mbox{Q}_2\,b$}\\

  1520 \bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a$}\\

  1521 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_1\,a + \mbox{Q}_2\,a$}\\

  1522 \end{tabular}

  1523 \end{center}

  1524 

  1525 

  1526 Arden's Lemma:

  1527 \begin{center}

  1528 If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}

  1529 \end{center}

  1530 

  1531 \only<2-6>{\small

  1532 \begin{textblock}{6}(1,0.8)

  1533 \begin{bubble}[6.7cm]

  1534 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}

  1535 \multicolumn{3}{@{}l}{substitute \bl{$\mbox{Q}_1$} into \bl{$\mbox{Q}_0$} \& \bl{$\mbox{Q}_2$}:}\\    

  1536 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_0\,a\,b +  \mbox{Q}_2\,b$}\\

  1537 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$}

  1538 \end{tabular}

  1539 \end{bubble}

  1540 \end{textblock}}

  1541 

  1542 \only<3-6>{\small

  1543 \begin{textblock}{6}(2,4.15)

  1544 \begin{bubble}[6.7cm]

  1545 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}

  1546 \multicolumn{3}{@{}l}{simplifying \bl{$\mbox{Q}_0$}:}\\    

  1547 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\

  1548 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$}

  1549 \end{tabular}

  1550 \end{bubble}

  1551 \end{textblock}}

  1552 

  1553 \only<4-6>{\small

  1554 \begin{textblock}{6}(3,7.55)

  1555 \begin{bubble}[6.7cm]

  1556 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}

  1557   \multicolumn{3}{@{}l}{Arden for \bl{$\mbox{Q}_2$}:}\\    

  1558 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\

  1559 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a\,(a^*)$}

  1560 \end{tabular}

  1561 \end{bubble}

  1562 \end{textblock}}

  1563 

  1564 \only<5-6>{\small

  1565 \begin{textblock}{6}(4,10.9)

  1566 \begin{bubble}[7.5cm]

  1567 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}

  1568   \multicolumn{3}{@{}l}{Substitute \bl{$\mbox{Q}_2$} and simplify:}\\    

  1569 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b + a\,a\,(a^*)\,b)$}\\

  1570 \end{tabular}

  1571 \end{bubble}

  1572 \end{textblock}}

  1573 

  1574 \only<6>{\small

  1575 \begin{textblock}{6}(5,13.4)

  1576 \begin{bubble}[7.5cm]

  1577 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}

  1578   \multicolumn{3}{@{}l}{Arden again for \bl{$\mbox{Q}_0$}:}\\    

  1579 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\

  1580 \end{tabular}

  1581 \end{bubble}

  1582 \end{textblock}}

  1583 

  1584 

  1585 \only<7->{\small

  1586 \begin{textblock}{6}(6,11.5)

  1587 \begin{bubble}[6.7cm]

  1588 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}

  1589 \multicolumn{3}{@{}l}{Finally:}\\    

  1590 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\

  1591 \bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a$}\\

  1592 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a^*)$}\\

  1593 \end{tabular}

  1594 \end{bubble}

  1595 \end{textblock}}

  1596 

  1597 \end{frame}

  1598 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

  1599