29 |
27 |
30 \begin{center} |
28 \begin{center} |
31 $\textit{zeroable(r)} \;\text{if and only if}\; L(r) = \varnothing$ |
29 $\textit{zeroable(r)} \;\text{if and only if}\; L(r) = \varnothing$ |
32 \end{center} |
30 \end{center} |
33 |
31 |
34 \item Define the tokens and regular expressions for a language |
32 \item Given the alphabet $\{a,b\}$. Draw the automaton that has two states, say $q_0$ and $q_1$. |
35 consisting of numbers, left-parenthesis $($, |
33 The starting state is $q_0$ and the final state is $q_1$. The transition |
36 right-parenthesis $)$, identifiers and the operations $+$, |
34 function is given by |
37 $-$ and $*$. Can the following strings in this language |
|
38 be lexed? |
|
39 |
35 |
40 \begin{itemize} |
36 \begin{center} |
41 \item $(a + 3) * b$ |
37 \begin{tabular}{l} |
42 \item $)()++ -33$ |
38 $(q_0, a) \rightarrow q_0$\\ |
43 \item $(a / 3) * 3$ |
39 $(q_0, b) \rightarrow q_1$\\ |
44 \end{itemize} |
40 $(q_1, b) \rightarrow q_1$ |
|
41 \end{tabular} |
|
42 \end{center} |
45 |
43 |
46 In case they can, can you give the corresponding token |
44 What is the languages recognised by this automaton? |
47 sequences. |
45 |
|
46 \item Give a non-deterministic finite automaton that can recognise |
|
47 the language $L(a\cdot (a + b)^* \cdot c)$. |
|
48 |
|
49 |
|
50 \item Given the following deterministic finite automaton over the alphabet $\{0, 1\}$, |
|
51 find the corresponding minimal automaton. In case states can be merged, |
|
52 state clearly which states can |
|
53 be merged. |
|
54 |
|
55 \begin{center} |
|
56 \begin{tikzpicture}[scale=3, line width=0.7mm] |
|
57 \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
|
58 \node[state] (q1) at ( 1,1) {$q_1$}; |
|
59 \node[state, accepting] (q4) at ( 2,1) {$q_4$}; |
|
60 \node[state] (q2) at (0.5,0) {$q_2$}; |
|
61 \node[state] (q3) at (1.5,0) {$q_3$}; |
|
62 \path[->] (q0) edge node[above] {$0$} (q1) |
|
63 (q0) edge node[right] {$1$} (q2) |
|
64 (q1) edge node[above] {$0$} (q4) |
|
65 (q1) edge node[right] {$1$} (q2) |
|
66 (q2) edge node[above] {$0$} (q3) |
|
67 (q2) edge [loop below] node {$1$} () |
|
68 (q3) edge node[left] {$0$} (q4) |
|
69 (q3) edge [bend left=95, looseness = 2.2] node [left=2mm] {$1$} (q0) |
|
70 (q4) edge [loop right] node {$0, 1$} () |
|
71 ; |
|
72 \end{tikzpicture} |
|
73 \end{center} |
|
74 |
|
75 \item Define the language $L(M)$ accepted by a deterministic finite automaton $M$. |
48 |
76 |
49 \end{enumerate} |
77 \end{enumerate} |
50 |
78 |
51 |
79 |
52 |
80 |