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

93 4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	1	\documentclass{article}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	2	\usepackage{charter}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	3	\usepackage{hyperref}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	4	\usepackage{amssymb}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	5	\usepackage{amsmath}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	6	\usepackage{tikz}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	7	\usetikzlibrary{automata}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	8
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	9	\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	10
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	11	\begin{document}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	12
267 a1544b804d1e updated homeworks Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 147 diff changeset	13	% 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	14	%
a1544b804d1e updated homeworks Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 147 diff changeset	15
a1544b804d1e updated homeworks Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 147 diff changeset	16
93 4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	17	\section*{Homework 5}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	18
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	19	\begin{enumerate}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	20	\item Define the following regular expressions
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	21
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	22	\begin{center}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	23	\begin{tabular}{ll}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	24	$r^+$ & (one or more matches)\\
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	25	$r^?$ & (zero or one match)\\
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	26	$r^{\{n\}}$ & (exactly $n$ matches)\\
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	27	$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	28	& \phantom{(}assumption $m \le n$)\\
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	29	\end{tabular}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	30	\end{center}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	31
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	32	in terms of the usual regular expressions
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	33
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	34	\begin{center}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	35	$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	36	\end{center}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	37
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	38
147 4725bba8ef26 added slides Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	39
4725bba8ef26 added slides Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	40	\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	41	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	42
4725bba8ef26 added slides Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	43	\[
4725bba8ef26 added slides Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	44	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	45	\]
4725bba8ef26 added slides Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	46
4725bba8ef26 added slides Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	47	holds.
93 4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	48	\end{enumerate}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	49
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	50	\end{document}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	51
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	52	%%% Local Variables:
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	53	%%% mode: latex
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	54	%%% TeX-master: t
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	55	%%% End:

author	Christian Urban <christian dot urban at kcl dot ac dot uk>
	Fri, 10 Oct 2014 16:59:22 +0100
changeset 267	a1544b804d1e
parent 147	4725bba8ef26
child 292	7ed2a25dd115
permissions	-rw-r--r--