45 \end{tabular} |
45 \end{tabular} |
46 \end{center} |
46 \end{center} |
47 |
47 |
48 What is the language recognised by this automaton? |
48 What is the language recognised by this automaton? |
49 |
49 |
50 \item Give a non-deterministic finite automaton that can recognise the |
50 \item Give a non-deterministic finite automaton that can |
51 language $L(a\cdot (a + b)^* \cdot c)$. |
51 recognise the language $L(a\cdot (a + b)^* \cdot c)$. |
52 |
52 |
53 \item Given a deterministic finite automata $A(Q, q_0, F, \delta)$, |
53 \item Given a deterministic finite automaton $A(Q, q_0, F, |
54 define which language is recognised by this automaton. Can you |
54 \delta)$, define which language is recognised by this |
55 define also the language defined by a non-deterministic automaton? |
55 automaton. Can you define also the language defined by a |
|
56 non-deterministic automaton? |
56 |
57 |
57 \item Given the following deterministic finite automata over the |
58 \item Given the following deterministic finite automaton over |
58 alphabet $\{a, b\}$, find an automaton that recognises the |
59 the alphabet $\{a, b\}$, find an automaton that |
59 complement language. (Hint: Recall that for the algorithm from the |
60 recognises the complement language. (Hint: Recall that |
60 lectures, the automaton needs to be in completed form, that is have |
61 for the algorithm from the lectures, the automaton needs |
61 a transition for every letter from the alphabet.) |
62 to be in completed form, that is have a transition for |
|
63 every letter from the alphabet.) |
62 |
64 |
63 \begin{center} |
65 \begin{center} |
64 \begin{tikzpicture}[>=stealth',very thick,auto, |
66 \begin{tikzpicture}[>=stealth',very thick,auto, |
65 every state/.style={minimum size=0pt, |
67 every state/.style={minimum size=0pt, |
66 inner sep=2pt,draw=blue!50,very thick, |
68 inner sep=2pt,draw=blue!50,very thick, |
90 %\end{tikzpicture} |
92 %\end{tikzpicture} |
91 %\end{center} |
93 %\end{center} |
92 %find the corresponding minimal automaton. State clearly which nodes |
94 %find the corresponding minimal automaton. State clearly which nodes |
93 %can be merged. |
95 %can be merged. |
94 |
96 |
95 \item Given the following non-deterministic finite automaton over the |
97 \item Given the following non-deterministic finite automaton |
96 alphabet $\{a, b\}$, find a deterministic finite automaton that |
98 over the alphabet $\{a, b\}$, find a deterministic |
97 recognises the same language: |
99 finite automaton that recognises the same language: |
98 |
100 |
99 \begin{center} |
101 \begin{center} |
100 \begin{tikzpicture}[>=stealth',very thick,auto, |
102 \begin{tikzpicture}[>=stealth',very thick,auto, |
101 every state/.style={minimum size=0pt, |
103 every state/.style={minimum size=0pt, |
102 inner sep=2pt,draw=blue!50,very thick, |
104 inner sep=2pt,draw=blue!50,very thick, |