equal
deleted
inserted
replaced
11 \begin{document} |
11 \begin{document} |
12 |
12 |
13 \section*{Homework 7} |
13 \section*{Homework 7} |
14 |
14 |
15 \begin{enumerate} |
15 \begin{enumerate} |
16 \item Suppose the following grammar for positive numbers |
16 \item Suppose the context-sensitive grammar |
17 |
17 |
18 \begin{center} |
18 \begin{center} |
|
19 \begin{tabular}{lcl} |
|
20 $S$ & $\rightarrow$ & $bSAA\;|\; \epsilon$\\ |
|
21 $A$ & $\rightarrow$ & $a$\\ |
|
22 $bA$ & $\rightarrow$ & $Ab$\\ |
|
23 \end{tabular} |
|
24 \end{center} |
19 |
25 |
20 \end{center} |
26 where $S$ is the starting symbol of the grammar. |
|
27 Give a derivation of the string $"\!aaabaaabb"$. |
|
28 What can you say about the number of as and bs in the |
|
29 strings recognised by this grammar. |
|
30 |
21 |
31 |
22 \item Consider the following grammar |
32 \item Consider the following grammar |
23 |
33 |
24 \begin{center} |
34 \begin{center} |
25 \begin{tabular}{l} |
35 \begin{tabular}{l} |
39 |
49 |
40 \begin{center} |
50 \begin{center} |
41 \texttt{The trainer trains the student team} |
51 \texttt{The trainer trains the student team} |
42 \end{center} |
52 \end{center} |
43 |
53 |
44 \item {\bf (Optional)} The task is to match strings where the letters are in alphabetical order---for example, |
54 \item Transform the grammar |
45 \texttt{abcfjz} would pass, but \texttt{acb} would not. Whitespace should be ignored---for example |
|
46 \texttt{ab c d} should pass. The point is to try to get the regular expression as short as possible! |
|
47 See: |
|
48 |
55 |
49 \begin{center} |
56 \begin{center} |
50 \url{http://callumacrae.github.com/regex-tuesday/challenge11.html} |
57 \begin{tabular}{lcl} |
|
58 $A$ & $\rightarrow$ & $0A1 \;|\; BB$\\ |
|
59 $B$ & $\rightarrow$ & $\epsilon \;|\; 2B$ |
|
60 \end{tabular} |
51 \end{center} |
61 \end{center} |
|
62 |
|
63 \noindent |
|
64 into Chomsky normal form. |
|
65 |
|
66 |
|
67 %\item {\bf (Optional)} The task is to match strings where the letters are in alphabetical order---for example, |
|
68 %\texttt{abcfjz} would pass, but \texttt{acb} would not. Whitespace should be ignored---for example |
|
69 %\texttt{ab c d} should pass. The point is to try to get the regular expression as short as possible! |
|
70 %See: |
|
71 |
|
72 %\begin{center} |
|
73 %\url{http://callumacrae.github.com/regex-tuesday/challenge11.html} |
|
74 %\end{center} |
52 \end{enumerate} |
75 \end{enumerate} |
53 |
76 |
54 \end{document} |
77 \end{document} |
55 |
78 |
56 %%% Local Variables: |
79 %%% Local Variables: |