495 us have a look how the right-hand sides of the equations are |
495 us have a look how the right-hand sides of the equations are |
496 constructed. First have a look at the second equation: the |
496 constructed. First have a look at the second equation: the |
497 left-hand side is $q_1$ and the right-hand side $q_0\,a$. The |
497 left-hand side is $q_1$ and the right-hand side $q_0\,a$. The |
498 right-hand side is essentially all possible ways how to end up |
498 right-hand side is essentially all possible ways how to end up |
499 in $q_1$. There is only one incoming edge from $q_0$ consuming |
499 in $q_1$. There is only one incoming edge from $q_0$ consuming |
500 an $a$. Therefore the right hand side is |
500 an $a$. Therefore the right hand side is this |
501 state followed by character---in this case $q_0\,a$. Now lets |
501 state followed by character---in this case $q_0\,a$. Now lets |
502 have a look at the third equation: there are two incoming |
502 have a look at the third equation: there are two incoming |
503 edges. Therefore we have two terms, namely $q_1\,a$ and |
503 edges for $q_2$. Therefore we have two terms, namely $q_1\,a$ and |
504 $q_2\,a$. These terms are separated by $+$. The first states |
504 $q_2\,a$. These terms are separated by $+$. The first states |
505 that if in state $q_1$ consuming an $a$ will bring you to |
505 that if in state $q_1$ consuming an $a$ will bring you to |
506 $q_2$, and the secont that being in $q_2$ and consuming an $a$ |
506 $q_2$, and the secont that being in $q_2$ and consuming an $a$ |
507 will make you stay in $q_2$. The right-hand side of the |
507 will make you stay in $q_2$. The right-hand side of the |
508 first equation is constructed similarly: there are three |
508 first equation is constructed similarly: there are three |
833 regular expressions because they are useful for recognising |
833 regular expressions because they are useful for recognising |
834 comments. But in principle we did not need to. The argument |
834 comments. But in principle we did not need to. The argument |
835 for this is as follows: take a regular expression, translate |
835 for this is as follows: take a regular expression, translate |
836 it into a NFA and DFA that recognise the same language. Once |
836 it into a NFA and DFA that recognise the same language. Once |
837 you have the DFA it is very easy to construct the automaton |
837 you have the DFA it is very easy to construct the automaton |
838 for the language not recognised by an DFA. If the DAF is |
838 for the language not recognised by an DFA. If the DFA is |
839 completed (this is important!), then you just need to exchange |
839 completed (this is important!), then you just need to exchange |
840 the accepting and non-accepting states. You can then translate |
840 the accepting and non-accepting states. You can then translate |
841 this DFA back into a regular expression. |
841 this DFA back into a regular expression. |
842 |
842 |
843 Not all languages are regular. The most well-known example |
843 Not all languages are regular. The most well-known example |