7 \section*{Homework 3} |
7 \section*{Homework 3} |
8 |
8 |
9 \HEADER |
9 \HEADER |
10 |
10 |
11 \begin{enumerate} |
11 \begin{enumerate} |
12 \item What is a regular language? Are there alternative ways to define this |
12 \item What is a regular language? Are there alternative ways |
13 notion? If yes, give an explanation why they define the same notion. |
13 to define this notion? If yes, give an explanation why |
|
14 they define the same notion. |
14 |
15 |
15 \item Why is every finite set of strings a regular language? |
16 \item Why is every finite set of strings a regular language? |
16 |
17 |
17 \item Assume you have an alphabet consisting of the letters $a$, $b$ |
18 \item Assume you have an alphabet consisting of the letters |
18 and $c$ only. (1) Find a regular expression that recognises the two |
19 $a$, $b$ and $c$ only. (1) Find a regular expression |
19 strings $ab$ and $ac$. (2) Find a regular expression that matches |
20 that recognises the two strings $ab$ and $ac$. (2) Find |
20 all strings \emph{except} these two strings. Note, you can only use |
21 a regular expression that matches all strings |
21 regular expressions of the form |
22 \emph{except} these two strings. Note, you can only use |
|
23 regular expressions of the form |
22 |
24 |
23 \begin{center} $r ::= |
25 \begin{center} $r ::= |
24 \varnothing \;|\; \epsilon \;|\; c \;|\; r_1 + r_2 \;|\; |
26 \ZERO \;|\; \ONE \;|\; c \;|\; r_1 + r_2 \;|\; |
25 r_1 \cdot r_2 \;|\; r^*$ |
27 r_1 \cdot r_2 \;|\; r^*$ |
26 \end{center} |
28 \end{center} |
27 |
29 |
28 \item Define the function \textit{zeroable} which takes a regular |
30 \item Define the function \textit{zeroable} which takes a |
29 expression as argument and returns a boolean. The function should |
31 regular expression as argument and returns a boolean. |
30 satisfy the following property: |
32 The function should satisfy the following property: |
31 |
33 |
32 \begin{center} |
34 \begin{center} |
33 $\textit{zeroable(r)} \;\text{if and only if}\; L(r) = \varnothing$ |
35 $\textit{zeroable(r)} \;\text{if and only if}\; |
|
36 L(r) = \{\}$ |
34 \end{center} |
37 \end{center} |
35 |
38 |
36 \item Given the alphabet $\{a,b\}$. Draw the automaton that has two |
39 \item Given the alphabet $\{a,b\}$. Draw the automaton that has two |
37 states, say $q_0$ and $q_1$. The starting state is $q_0$ and the |
40 states, say $q_0$ and $q_1$. The starting state is $q_0$ and the |
38 final state is $q_1$. The transition function is given by |
41 final state is $q_1$. The transition function is given by |