93
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1 |
\documentclass{article}
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
2 |
\usepackage{../style}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
3 |
\usepackage{../graphics}
|
527
|
4 |
\usepackage{../grammar}
|
93
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
5 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
6 |
\begin{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
7 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
8 |
% explain what is a context-free grammar and the language it generates
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
9 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
10 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
11 |
|
93
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
12 |
\section*{Homework 5}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
13 |
|
359
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
14 |
\HEADER
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
15 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
16 |
|
93
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
17 |
\begin{enumerate}
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
18 |
\item Consider the basic regular expressions
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
19 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
20 |
\begin{center}
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
21 |
$r ::= \ZERO \;|\; \ONE \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
22 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
23 |
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
24 |
and suppose you want to show a property $P(r)$ for all
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
25 |
regular expressions $r$ by structural induction. Write
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
26 |
down which cases do you need to analyse. State clearly
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
27 |
the induction hypotheses if applicable in a case.
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
28 |
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
29 |
\item Define a regular expression, written $ALL$, that can
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
30 |
match every string. This definition should be in terms
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
31 |
of the following extended regular expressions:
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
32 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
33 |
\begin{center}
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
34 |
$r ::= \ZERO \;|\;
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
35 |
\ONE \;|\;
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
36 |
c \;|\;
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
37 |
r_1 + r_2 \;|\;
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
38 |
r_1 \cdot r_2 \;|\;
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
39 |
r^* \;|\;
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
40 |
\sim r$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
41 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
42 |
|
322
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
43 |
%\item Assume the delimiters for comments are \texttt{$\slash$*}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
44 |
%and \texttt{*$\slash$}. Give a regular expression that can
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
45 |
%recognise comments of the form
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
46 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
47 |
%\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
48 |
%\texttt{$\slash$*~\ldots{}~*$\slash$}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
49 |
%\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
50 |
%
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
51 |
%where the three dots stand for arbitrary characters, but not
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
52 |
%comment delimiters.
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
53 |
|
93
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
54 |
\item Define the following regular expressions
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
55 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
56 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
57 |
\begin{tabular}{ll}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
58 |
$r^+$ & (one or more matches)\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
59 |
$r^?$ & (zero or one match)\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
60 |
$r^{\{n\}}$ & (exactly $n$ matches)\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
61 |
$r^{\{m, n\}}$ & (at least $m$ and maximal $n$ matches, with the\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
62 |
& \phantom{(}assumption $m \le n$)\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
63 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
64 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
65 |
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
66 |
in terms of the usual basic regular expressions
|
93
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
67 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
68 |
\begin{center}
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
69 |
$r ::= \ZERO \;|\; \ONE \;|\; c \;|\; r_1 + r_2 \;|\; r_1 \cdot r_2 \;|\; r^*$
|
93
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
70 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
71 |
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
72 |
\item Give the regular expressions for lexing a language
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
73 |
consisting of identifiers, left-parenthesis \texttt{(},
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
74 |
right-parenthesis \texttt{)}, numbers that can be either
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
75 |
positive or negative, and the operations \texttt{+},
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
76 |
\texttt{-} and \texttt{*}.
|
93
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
77 |
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
78 |
Decide whether the following strings can be lexed in
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
79 |
this language?
|
147
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
80 |
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
81 |
\begin{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
82 |
\item \texttt{"(a3+3)*b"}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
83 |
\item \texttt{")()++-33"}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
84 |
\item \texttt{"(b42/3)*3"}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
85 |
\end{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
86 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
87 |
In case they can, give the corresponding token sequences. (Hint:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
88 |
Observe the maximal munch rule and the priorities of your regular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
89 |
expressions that make the process of lexing unambiguous.)
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
90 |
|
602
|
91 |
\item Suppose the following context-free grammar $G$
|
527
|
92 |
|
|
93 |
\begin{plstx}[margin=1cm]
|
|
94 |
: \meta{S\/} ::= \meta{A\/}\cdot\meta{S\/}\cdot\meta{B\/} \;\mid\;
|
|
95 |
\meta{B\/}\cdot\meta{S\/}\cdot\meta{A\/} \;\mid\; \epsilon\\
|
|
96 |
: \meta{A\/} ::= a \mid \epsilon\\
|
|
97 |
: \meta{B\/} ::= b\\
|
|
98 |
\end{plstx}
|
|
99 |
|
602
|
100 |
where the starting symbol is $\meta{S}$.
|
|
101 |
Which of the following strings are in the language of $G$?
|
527
|
102 |
|
|
103 |
\begin{itemize}
|
|
104 |
\item[$\bullet$] $a$
|
|
105 |
\item[$\bullet$] $b$
|
|
106 |
\item[$\bullet$] $ab$
|
|
107 |
\item[$\bullet$] $ba$
|
|
108 |
\item[$\bullet$] $bb$
|
|
109 |
\item[$\bullet$] $baa$
|
619
|
110 |
\end{itemize}
|
|
111 |
|
|
112 |
\item Suppose the following context-free grammar
|
|
113 |
|
|
114 |
\begin{plstx}[margin=1cm]
|
|
115 |
: \meta{S\/} ::= a\cdot \meta{S\/}\cdot a\;\mid\;
|
|
116 |
b\cdot \meta{S\/}\cdot b\;\mid\; \epsilon\\
|
|
117 |
\end{plstx}
|
|
118 |
|
|
119 |
Describe which language is generated by this grammar.
|
|
120 |
|
527
|
121 |
|
|
122 |
|
444
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
123 |
\item {\bf(Optional)} Recall the definitions for $Der$ and $der$
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
124 |
from the lectures. Prove by induction on $r$ the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
125 |
property that
|
147
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
126 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
127 |
\[
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
128 |
L(der\,c\,r) = Der\,c\,(L(r))
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
129 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
130 |
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
131 |
holds.
|
294
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
132 |
|
444
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
133 |
\item \POSTSCRIPT
|
93
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
134 |
\end{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
135 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
136 |
\end{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
137 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
138 |
%%% Local Variables:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
139 |
%%% mode: latex
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
140 |
%%% TeX-master: t
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
141 |
%%% End:
|