# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1412549778 -3600
# Node ID 4deef8ac5d72877b5b0851ba07f97f1e6da6362e
# Parent 92e6985018ae12892f750d5fc07bd4043b34b80f
uodated hws
diff -r 92e6985018ae -r 4deef8ac5d72 graphics.sty
--- a/graphics.sty Mon Sep 29 00:45:38 2014 +0100
+++ b/graphics.sty Sun Oct 05 23:56:18 2014 +0100
@@ -2,6 +2,7 @@
\usepackage{pgf}
\usetikzlibrary{positioning}
\usetikzlibrary{calc}
+\usetikzlibrary{automata}
\usepackage{graphicx}
\usepackage{pgfplots}
diff -r 92e6985018ae -r 4deef8ac5d72 hws/hw03.pdf
Binary file hws/hw03.pdf has changed
diff -r 92e6985018ae -r 4deef8ac5d72 hws/hw03.tex
--- a/hws/hw03.tex Mon Sep 29 00:45:38 2014 +0100
+++ b/hws/hw03.tex Sun Oct 05 23:56:18 2014 +0100
@@ -1,8 +1,6 @@
\documentclass{article}
-\usepackage{charter}
-\usepackage{hyperref}
-\usepackage{amssymb}
-\usepackage{amsmath}
+\usepackage{../style}
+\usepackage{../graphics}
\begin{document}
@@ -31,20 +29,50 @@
$\textit{zeroable(r)} \;\text{if and only if}\; L(r) = \varnothing$
\end{center}
-\item Define the tokens and regular expressions for a language
- consisting of numbers, left-parenthesis $($,
- right-parenthesis $)$, identifiers and the operations $+$,
- $-$ and $*$. Can the following strings in this language
- be lexed?
+\item Given the alphabet $\{a,b\}$. Draw the automaton that has two states, say $q_0$ and $q_1$.
+The starting state is $q_0$ and the final state is $q_1$. The transition
+function is given by
+
+\begin{center}
+\begin{tabular}{l}
+$(q_0, a) \rightarrow q_0$\\
+$(q_0, b) \rightarrow q_1$\\
+$(q_1, b) \rightarrow q_1$
+\end{tabular}
+\end{center}
+
+What is the languages recognised by this automaton?
+
+\item Give a non-deterministic finite automaton that can recognise
+the language $L(a\cdot (a + b)^* \cdot c)$.
+
-\begin{itemize}
- \item $(a + 3) * b$
- \item $)()++ -33$
- \item $(a / 3) * 3$
-\end{itemize}
+\item Given the following deterministic finite automaton over the alphabet $\{0, 1\}$,
+find the corresponding minimal automaton. In case states can be merged,
+state clearly which states can
+be merged.
-In case they can, can you give the corresponding token
-sequences.
+\begin{center}
+\begin{tikzpicture}[scale=3, line width=0.7mm]
+ \node[state, initial] (q0) at ( 0,1) {$q_0$};
+ \node[state] (q1) at ( 1,1) {$q_1$};
+ \node[state, accepting] (q4) at ( 2,1) {$q_4$};
+ \node[state] (q2) at (0.5,0) {$q_2$};
+ \node[state] (q3) at (1.5,0) {$q_3$};
+ \path[->] (q0) edge node[above] {$0$} (q1)
+ (q0) edge node[right] {$1$} (q2)
+ (q1) edge node[above] {$0$} (q4)
+ (q1) edge node[right] {$1$} (q2)
+ (q2) edge node[above] {$0$} (q3)
+ (q2) edge [loop below] node {$1$} ()
+ (q3) edge node[left] {$0$} (q4)
+ (q3) edge [bend left=95, looseness = 2.2] node [left=2mm] {$1$} (q0)
+ (q4) edge [loop right] node {$0, 1$} ()
+ ;
+\end{tikzpicture}
+\end{center}
+
+\item Define the language $L(M)$ accepted by a deterministic finite automaton $M$.
\end{enumerate}
diff -r 92e6985018ae -r 4deef8ac5d72 hws/hw04.pdf
Binary file hws/hw04.pdf has changed
diff -r 92e6985018ae -r 4deef8ac5d72 hws/hw04.tex
--- a/hws/hw04.tex Mon Sep 29 00:45:38 2014 +0100
+++ b/hws/hw04.tex Sun Oct 05 23:56:18 2014 +0100
@@ -1,13 +1,11 @@
\documentclass{article}
-\usepackage{charter}
-\usepackage{hyperref}
-\usepackage{amssymb}
-\usepackage{amsmath}
+\usepackage{../style}
+
\usepackage{tikz}
\usetikzlibrary{automata}
-\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
+%%\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
\begin{document}
@@ -21,6 +19,21 @@
\item If a regular expression $r$ does not contain any occurrence of $\varnothing$,
is it possible for $L(r)$ to be empty?
+\item Define the tokens and regular expressions for a language
+ consisting of numbers, left-parenthesis $($,
+ right-parenthesis $)$, identifiers and the operations $+$,
+ $-$ and $*$. Can the following strings in this language
+ be lexed?
+
+\begin{itemize}
+ \item $(a + 3) * b$
+ \item $)()++ -33$
+ \item $(a / 3) * 3$
+\end{itemize}
+
+In case they can, can you give the corresponding token
+sequences.
+
\item Assume that $s^{-1}$ stands for the operation of reversing a
string $s$. Given the following \emph{reversing} function on regular
expressions
@@ -67,48 +80,6 @@
that can recognise any character, and a regular expression \texttt{NOT} that recognises
the complement of a regular expression.)
-\item Given the alphabet $\{a,b\}$. Draw the automaton that has two states, say $q_0$ and $q_1$.
-The starting state is $q_0$ and the final state is $q_1$. The transition
-function is given by
-
-\begin{center}
-\begin{tabular}{l}
-$(q_0, a) \rightarrow q_0$\\
-$(q_0, b) \rightarrow q_1$\\
-$(q_1, b) \rightarrow q_1$
-\end{tabular}
-\end{center}
-
-What is the languages recognised by this automaton?
-
-\item Give a non-deterministic finite automaton that can recognise
-the language $L(a\cdot (a + b)^* \cdot c)$.
-
-
-\item Given the following deterministic finite automaton over the alphabet $\{0, 1\}$,
-find the corresponding minimal automaton. In case states can be merged,
-state clearly which states can
-be merged.
-
-\begin{center}
-\begin{tikzpicture}[scale=3, line width=0.7mm]
- \node[state, initial] (q0) at ( 0,1) {$q_0$};
- \node[state] (q1) at ( 1,1) {$q_1$};
- \node[state, accepting] (q4) at ( 2,1) {$q_4$};
- \node[state] (q2) at (0.5,0) {$q_2$};
- \node[state] (q3) at (1.5,0) {$q_3$};
- \path[->] (q0) edge node[above] {$0$} (q1)
- (q0) edge node[right] {$1$} (q2)
- (q1) edge node[above] {$0$} (q4)
- (q1) edge node[right] {$1$} (q2)
- (q2) edge node[above] {$0$} (q3)
- (q2) edge [loop below] node {$1$} ()
- (q3) edge node[left] {$0$} (q4)
- (q3) edge [bend left=95, looseness = 2.2] node [left=2mm] {$1$} (q0)
- (q4) edge [loop right] node {$0, 1$} ()
- ;
-\end{tikzpicture}
-\end{center}
%\item (Optional) The tokenizer in \texttt{regexp3.scala} takes as
@@ -124,7 +95,7 @@
% explain what is a context-free grammar and the language it generates
%
%
-% Define the language L(M) accepted by a deterministic finite automaton M.
+%
%
%
% does (a + b)*b+ and (a*b+) + (b*b+) define the same language