equal
deleted
inserted
replaced
7 \section*{Homework 3} |
7 \section*{Homework 3} |
8 |
8 |
9 \HEADER |
9 \HEADER |
10 |
10 |
11 \begin{enumerate} |
11 \begin{enumerate} |
|
12 \item The regular expression matchers in Java, Python and Ruby can be |
|
13 very slow with some (basic) regular expressions. What is the main |
|
14 reason for this inefficient computation? |
|
15 |
12 \item What is a regular language? Are there alternative ways |
16 \item What is a regular language? Are there alternative ways |
13 to define this notion? If yes, give an explanation why |
17 to define this notion? If yes, give an explanation why |
14 they define the same notion. |
18 they define the same notion. |
15 |
19 |
16 \item Why is every finite set of strings a regular language? |
20 \item Why is every finite set of strings a regular language? |
25 \begin{center} $r ::= |
29 \begin{center} $r ::= |
26 \ZERO \;|\; \ONE \;|\; c \;|\; r_1 + r_2 \;|\; |
30 \ZERO \;|\; \ONE \;|\; c \;|\; r_1 + r_2 \;|\; |
27 r_1 \cdot r_2 \;|\; r^*$ |
31 r_1 \cdot r_2 \;|\; r^*$ |
28 \end{center} |
32 \end{center} |
29 |
33 |
30 \item Define the function \textit{zeroable} which takes a |
34 %\item Define the function \textit{zeroable} which takes a |
31 regular expression as argument and returns a boolean. |
35 % regular expression as argument and returns a boolean. |
32 The function should satisfy the following property: |
36 % The function should satisfy the following property: |
33 |
37 % |
34 \begin{center} |
38 % \begin{center} |
35 $\textit{zeroable(r)} \;\text{if and only if}\; |
39 % $\textit{zeroable(r)} \;\text{if and only if}\; |
36 L(r) = \{\}$ |
40 % L(r) = \{\}$ |
37 \end{center} |
41 % \end{center} |
38 |
42 |
39 \item Given the alphabet $\{a,b\}$. Draw the automaton that has two |
43 \item Given the alphabet $\{a,b\}$. Draw the automaton that has two |
40 states, say $Q_0$ and $Q_1$. The starting state is $Q_0$ and the |
44 states, say $Q_0$ and $Q_1$. The starting state is $Q_0$ and the |
41 final state is $Q_1$. The transition function is given by |
45 final state is $Q_1$. The transition function is given by |
42 |
46 |