afl-material: hws/hw05.tex@12ef150273ce (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
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	13	\section*{Homework 5}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	14
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	15	\begin{enumerate}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	16	\item Define the following regular expressions
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	17
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	18	\begin{center}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	19	\begin{tabular}{ll}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	20	$r^+$ & (one or more matches)\\
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	21	$r^?$ & (zero or one match)\\
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	22	$r^{\{n\}}$ & (exactly $n$ matches)\\
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	23	$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	24	& \phantom{(}assumption $m \le n$)\\
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	25	\end{tabular}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	26	\end{center}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	27
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	28	in terms of the usual regular expressions
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	29
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	30	\begin{center}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	31	$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	32	\end{center}
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	\item Given a deterministic finite automata $A(Q, q_0, F, \delta)$,
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	35	define which language is recognised by this automaton.
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	36
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	37	\item Given the following deterministic finite automata over the alphabet
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	38	$\{a, b\}$, find an automaton that recognises the complement language.
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	39	(Hint: Recall that for the algorithm from the lectures, the automaton needs to be
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	40	in completed form, that is have a transition for every letter from the alphabet.)
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	41
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	42	\begin{center}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	43	\begin{tikzpicture}[scale=3, line width=0.7mm]
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	44	\node[state, initial] (q0) at ( 0,1) {$q_0$};
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	45	\node[state, accepting] (q1) at ( 1,1) {$q_1$};
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	46	\path[->] (q0) edge node[above] {$a$} (q1)
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	47	(q1) edge [loop right] node {$b$} ()
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	48	;
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	49	\end{tikzpicture}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	50	\end{center}
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	\item Given the following deterministic finite automaton
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	53
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	54	\begin{center}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	55	\begin{tikzpicture}[scale=3, line width=0.7mm]
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	56	\node[state, initial] (q0) at ( 0,1) {$q_0$};
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	57	\node[state,accepting] (q1) at ( 1,1) {$q_1$};
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	58	\node[state, accepting] (q2) at ( 2,1) {$q_2$};
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	59	\path[->] (q0) edge node[above] {$b$} (q1)
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	60	(q1) edge [loop above] node[above] {$a$} ()
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	61	(q2) edge [loop above] node[above] {$a, b$} ()
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	62	(q1) edge node[above] {$b$} (q2)
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	63	(q0) edge[bend right] node[below] {$a$} (q2)
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	64	;
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	65	\end{tikzpicture}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	66	\end{center}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	67	find the corresponding minimal automaton. State clearly which nodes
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	68	can be merged.
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	69
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	70	\item Given the following non-deterministic finite automaton over the alphabet $\{a, b\}$,
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	71	find a deterministic finite automaton that recognises the same language:
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	72
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	73	\begin{center}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	74	\begin{tikzpicture}[scale=3, line width=0.7mm]
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	75	\node[state, initial] (q0) at ( 0,1) {$q_0$};
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	76	\node[state] (q1) at ( 1,1) {$q_1$};
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	77	\node[state, accepting] (q2) at ( 2,1) {$q_2$};
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	78	\path[->] (q0) edge node[above] {$a$} (q1)
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	79	(q0) edge [loop above] node[above] {$b$} ()
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	80	(q0) edge [loop below] node[below] {$a$} ()
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	81	(q1) edge node[above] {$a$} (q2)
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	82	;
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	83	\end{tikzpicture}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	84	\end{center}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	85
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	86	\item
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	87	Given the following finite deterministic automaton over the alphabet $\{a, b\}$:
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	88
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	89	\begin{center}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	90	\begin{tikzpicture}[scale=2, line width=0.5mm]
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	91	\node[state, initial, accepting] (q0) at ( 0,1) {$q_0$};
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	92	\node[state, accepting] (q1) at ( 1,1) {$q_1$};
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	93	\node[state] (q2) at ( 2,1) {$q_2$};
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	94	\path[->] (q0) edge[bend left] node[above] {$a$} (q1)
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	95	(q1) edge[bend left] node[above] {$b$} (q0)
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	96	(q2) edge[bend left=50] node[below] {$b$} (q0)
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	97	(q1) edge node[above] {$a$} (q2)
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	98	(q2) edge [loop right] node {$a$} ()
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	99	(q0) edge [loop below] node {$b$} ()
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	100	;
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	101	\end{tikzpicture}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	102	\end{center}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	103
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	104	Give a regular expression that can recognise the same language as
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	105	this automaton. (Hint: If you use Brzozwski's method, you can assume
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	106	Arden's lemma which states that an equation of the form $q = q\cdot r + s$
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	107	has the unique solution $q = s \cdot r^*$.)\
147 4725bba8ef26 added slides Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	108
4725bba8ef26 added slides Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	109	\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	110	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	111
4725bba8ef26 added slides Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	112	\[
4725bba8ef26 added slides Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	113	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	114	\]
4725bba8ef26 added slides Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	115
4725bba8ef26 added slides Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	116	holds.
93 4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	117	\end{enumerate}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	118
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	119	\end{document}
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	120
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	121	%%% Local Variables:
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	122	%%% mode: latex
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	123	%%% TeX-master: t
4794759139ea better organised Christian Urban <christian dot urban at kcl dot ac dot uk> parents: diff changeset	124	%%% End:

author	Christian Urban <christian dot urban at kcl dot ac dot uk>
	Wed, 13 Nov 2013 06:40:37 +0000
changeset 188	12ef150273ce
parent 147	4725bba8ef26
child 267	a1544b804d1e
permissions	-rw-r--r--