# HG changeset patch # User Christian Urban # 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