afl-material: hws/hw05.tex@7ed2a25dd115 (annotated)

93 4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	1	\documentclass{article}
292 7ed2a25dd115 updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 267 diff changeset	2	\usepackage{../style}
7ed2a25dd115 updated Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 267 diff changeset	3	\usepackage{../graphics}
93 4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	4
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	5
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	6	\begin{document}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	7
267 a1544b804d1e updated homeworks Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 147 diff changeset	8	% explain what is a context-free grammar and the language it generates
a1544b804d1e updated homeworks Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 147 diff changeset	9	%
a1544b804d1e updated homeworks Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 147 diff changeset	10
a1544b804d1e updated homeworks Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 147 diff changeset	11
93 4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	12	\section*{Homework 5}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	13
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	14	\begin{enumerate}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	15	\item Define the following regular expressions
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	16
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	17	\begin{center}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	18	\begin{tabular}{ll}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	19	$r^+$ & (one or more matches)\\
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	20	$r^?$ & (zero or one match)\\
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	21	$r^{\{n\}}$ & (exactly $n$ matches)\\
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	22	$r^{\{m, n\}}$ & (at least $m$ and maximal $n$ matches, with the\\
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	23	& \phantom{(}assumption $m \le n$)\\
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	24	\end{tabular}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	25	\end{center}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	26
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	27	in terms of the usual regular expressions
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	28
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	29	\begin{center}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	30	$r ::= \varnothing \;\|\; \epsilon \;\|\; c \;\|\; r_1 + r_2 \;\|\; r_1 \cdot r_2 \;\|\; r^*$
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	31	\end{center}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	32
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	33
147 4725bba8ef26 added slides Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	34
4725bba8ef26 added slides Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	35	\item Recall the definitions for $Der$ and $der$ from the lectures.
4725bba8ef26 added slides Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	36	Prove by induction on $r$ the property that
4725bba8ef26 added slides Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	37
4725bba8ef26 added slides Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	38	\[
4725bba8ef26 added slides Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	39	L(der\,c\,r) = Der\,c\,(L(r))
4725bba8ef26 added slides Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	40	\]
4725bba8ef26 added slides Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	41
4725bba8ef26 added slides Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	42	holds.
93 4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	43	\end{enumerate}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	44
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	45	\end{document}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	46
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	47	%%% Local Variables:
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	48	%%% mode: latex
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	49	%%% TeX-master: t
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	50	%%% End:

author	Christian Urban <christian dot urban at kcl dot ac dot uk>
	Tue, 28 Oct 2014 12:24:11 +0000
changeset 292	7ed2a25dd115
parent 267	a1544b804d1e
child 294	c29853b672fb
permissions	-rw-r--r--