afl-material: hws/hw03.tex@4deef8ac5d72 (annotated)

23 ea594f94f85d tuned Christian Urban <urbanc@in.tum.de> parents: diff changeset	1	\documentclass{article}
264 4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	2	\usepackage{../style}
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	3	\usepackage{../graphics}
23 ea594f94f85d tuned Christian Urban <urbanc@in.tum.de> parents: diff changeset	4
ea594f94f85d tuned Christian Urban <urbanc@in.tum.de> parents: diff changeset	5	\begin{document}
ea594f94f85d tuned Christian Urban <urbanc@in.tum.de> parents: diff changeset	6
ea594f94f85d tuned Christian Urban <urbanc@in.tum.de> parents: diff changeset	7	\section*{Homework 3}
ea594f94f85d tuned Christian Urban <urbanc@in.tum.de> parents: diff changeset	8
ea594f94f85d tuned Christian Urban <urbanc@in.tum.de> parents: diff changeset	9	\begin{enumerate}
132 04264d0c43bb added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	10	\item What is a regular language?
04264d0c43bb added Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 102 diff changeset	11
258 1e4da6d2490c updated programs Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 146 diff changeset	12	\item Assume you have an alphabet consisting of the letters
1e4da6d2490c updated programs Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 146 diff changeset	13	$a$, $b$ and $c$ only. (1) Find a regular expression
1e4da6d2490c updated programs Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 146 diff changeset	14	that recognises the two strings $ab$ and $ac$. (2) Find
1e4da6d2490c updated programs Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 146 diff changeset	15	a regular expression that matches all strings
1e4da6d2490c updated programs Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 146 diff changeset	16	\emph{except} these two strings. Note, you can only use
1e4da6d2490c updated programs Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 146 diff changeset	17	regular expressions of the form
1e4da6d2490c updated programs Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 146 diff changeset	18
1e4da6d2490c updated programs Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 146 diff changeset	19	\begin{center} $r ::=
1e4da6d2490c updated programs Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 146 diff changeset	20	\varnothing \;\|\; \epsilon \;\|\; c \;\|\; r_1 + r_2 \;\|\;
1e4da6d2490c updated programs Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 146 diff changeset	21	r_1 \cdot r_2 \;\|\; r^*$
1e4da6d2490c updated programs Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 146 diff changeset	22	\end{center}
1e4da6d2490c updated programs Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 146 diff changeset	23
1e4da6d2490c updated programs Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 146 diff changeset	24	\item Define the function \textit{zeroable} which takes a
1e4da6d2490c updated programs Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 146 diff changeset	25	regular expression as argument and returns a boolean.
1e4da6d2490c updated programs Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 146 diff changeset	26	The function should satisfy the following property:
1e4da6d2490c updated programs Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 146 diff changeset	27
23 ea594f94f85d tuned Christian Urban <urbanc@in.tum.de> parents: diff changeset	28	\begin{center}
258 1e4da6d2490c updated programs Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 146 diff changeset	29	$\textit{zeroable(r)} \;\text{if and only if}\; L(r) = \varnothing$
23 ea594f94f85d tuned Christian Urban <urbanc@in.tum.de> parents: diff changeset	30	\end{center}
ea594f94f85d tuned Christian Urban <urbanc@in.tum.de> parents: diff changeset	31
264 4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	32	\item Given the alphabet $\{a,b\}$. Draw the automaton that has two states, say $q_0$ and $q_1$.
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	33	The starting state is $q_0$ and the final state is $q_1$. The transition
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	34	function is given by
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	35
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	36	\begin{center}
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	37	\begin{tabular}{l}
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	38	$(q_0, a) \rightarrow q_0$\\
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	39	$(q_0, b) \rightarrow q_1$\\
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	40	$(q_1, b) \rightarrow q_1$
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	41	\end{tabular}
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	42	\end{center}
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	43
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	44	What is the languages recognised by this automaton?
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	45
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	46	\item Give a non-deterministic finite automaton that can recognise
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	47	the language $L(a\cdot (a + b)^* \cdot c)$.
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	48
27 0f05e90b960d added Christian Urban <urbanc@in.tum.de> parents: 23 diff changeset	49
264 4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	50	\item Given the following deterministic finite automaton over the alphabet $\{0, 1\}$,
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	51	find the corresponding minimal automaton. In case states can be merged,
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	52	state clearly which states can
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	53	be merged.
31 e22ba348b209 added hw04 Christian Urban <urbanc@in.tum.de> parents: 30 diff changeset	54
264 4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	55	\begin{center}
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	56	\begin{tikzpicture}[scale=3, line width=0.7mm]
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	57	\node[state, initial] (q0) at ( 0,1) {$q_0$};
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	58	\node[state] (q1) at ( 1,1) {$q_1$};
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	59	\node[state, accepting] (q4) at ( 2,1) {$q_4$};
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	60	\node[state] (q2) at (0.5,0) {$q_2$};
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	61	\node[state] (q3) at (1.5,0) {$q_3$};
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	62	\path[->] (q0) edge node[above] {$0$} (q1)
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	63	(q0) edge node[right] {$1$} (q2)
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	64	(q1) edge node[above] {$0$} (q4)
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	65	(q1) edge node[right] {$1$} (q2)
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	66	(q2) edge node[above] {$0$} (q3)
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	67	(q2) edge [loop below] node {$1$} ()
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	68	(q3) edge node[left] {$0$} (q4)
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	69	(q3) edge [bend left=95, looseness = 2.2] node [left=2mm] {$1$} (q0)
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	70	(q4) edge [loop right] node {$0, 1$} ()
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	71	;
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	72	\end{tikzpicture}
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	73	\end{center}
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	74
4deef8ac5d72 uodated hws Christian Urban <christian dot urban at kcl dot ac dot uk> parents: 258 diff changeset	75	\item Define the language $L(M)$ accepted by a deterministic finite automaton $M$.
31 e22ba348b209 added hw04 Christian Urban <urbanc@in.tum.de> parents: 30 diff changeset	76
23 ea594f94f85d tuned Christian Urban <urbanc@in.tum.de> parents: diff changeset	77	\end{enumerate}
ea594f94f85d tuned Christian Urban <urbanc@in.tum.de> parents: diff changeset	78
31 e22ba348b209 added hw04 Christian Urban <urbanc@in.tum.de> parents: 30 diff changeset	79
27 0f05e90b960d added Christian Urban <urbanc@in.tum.de> parents: 23 diff changeset	80
23 ea594f94f85d tuned Christian Urban <urbanc@in.tum.de> parents: diff changeset	81	\end{document}
ea594f94f85d tuned Christian Urban <urbanc@in.tum.de> parents: diff changeset	82
ea594f94f85d tuned Christian Urban <urbanc@in.tum.de> parents: diff changeset	83	%%% Local Variables:
ea594f94f85d tuned Christian Urban <urbanc@in.tum.de> parents: diff changeset	84	%%% mode: latex
ea594f94f85d tuned Christian Urban <urbanc@in.tum.de> parents: diff changeset	85	%%% TeX-master: t
ea594f94f85d tuned Christian Urban <urbanc@in.tum.de> parents: diff changeset	86	%%% End:

author	Christian Urban <christian dot urban at kcl dot ac dot uk>
	Sun, 05 Oct 2014 23:56:18 +0100
changeset 264	4deef8ac5d72
parent 258	1e4da6d2490c
child 267	a1544b804d1e
permissions	-rw-r--r--