% This work is licensed under the Creative Commons Attribution 3.0 Unported License.
% To view a copy of this license, visit http://creativecommons.org/licenses/by/3.0/
% or send a letter to Creative Commons, 171 Second Street, Suite 300, San Francisco, 
% California, 94105, USA.
%
% Author: Alejandro Diaz-Caro <alejandro.diaz-caro@imag.fr>
% Date: October 2010
\documentclass[12pt,a4paper]{article}

\usepackage{amsmath,amsfonts,amssymb}
\usepackage[top=1.5cm,right=1.5cm,bottom=1.5cm,left=1.5cm]{geometry}
\usepackage{vaucanson-g}

\makeindex

\title{Exercise sheet 1: Grammars and automata}
\author{Alejandro D\'iaz-Caro}
\date{2010}

\begin{document}
\begin{center}
 \textbf{\begin{large}Exercise sheet 1: Grammars and automata\end{large}}
\end{center}

\begin{enumerate}
 \item\label{ex01} Find a finite automaton for each language over the alphabet $\{0,1\}$
	\begin{enumerate}
	\item $\{00\}$
	\item $\{0,1010,110,001\}$
	\item $\{$All the strings starting and ending with $1\}$
	\item $\{$Strings with at least two consecutive zeros$\}$
	\item $\{$Strings ending with $00$ or $11\}$
	\item $\{$Strings with at least two equal consecutive symbols$\}$
	\item $\{$Strings starting with $1$ and ending with $11\}$
	\item $\{$Strings not containing the substring $001\}$
	\item $\{$Strings with an even number of zeros$\}$
	\item $\{$Strings with an even number of zeros and an odd number of ones$\}$
	\end{enumerate}

\item\label{exunion} Draw a diagram of an automaton recognizing the union of the recognized languages of the following automata:
\begin{center}\begin{VCPicture}{(0,1)(9,0)}
\State{(0,0)}{a}
\FinalState{(3,0)}{b}
\ArcR{a}{b}{a}
\ArcR{b}{a}{b}
\Initial{a}
\State{(6,0)}{x}
\FinalState{(9,0)}{y}
\ArcR{x}{y}{x}
\ArcR{y}{x}{y}
\Initial{x}
\end{VCPicture}
\end{center}

\item\label{exconcat} String concatenation is the operation of joining two character strings end-to-end. For example, the strings ``snow'' and ``ball'' may be concatenated to give ``snowball''. We write $M\circ N$l to represent the concatenation of the word $M$ with the word $N$. Language concatenation is the concatenation of all the words in one language with the words in the other. Notice that $L_1\circ L_2\neq L_2\circ L_1$.

Draw a diagram of an automaton recognizing the concatenation of the language recognized by
\begin{center}\begin{VCPicture}{(0,1)(4.5,0)}
\State{(0,0)}{a}
\FinalState{(3,0)}{b}
\ArcR{a}{b}{a}
\ArcR{b}{a}{b}
\Initial{a}
\LoopS[.75]{b}{b}
\end{VCPicture}
\end{center}
with the language recognized by
\begin{center}\begin{VCPicture}{(0,1)(4.5,-1)}
\State{(0,0)}{x}
\FinalState{(3,0)}{y}
\ArcR{x}{y}{y}
\Initial{x}
\LoopS{x}{x}
\LoopS[.75]{y}{y}
\end{VCPicture}
\end{center}

\item\label{exabc} Given the alphabet $\{a,b,c\}$, find an automaton for each language.
	\begin{enumerate}
	\item $\{$Strings with a number of $b$ being a multiple of $3$ and no starting with $a\}$
	\item $\{$Strings having at most two consecutive $b$ and not ending with $c\}$
	\item $\{$Strings with an even number of $a$ and odd number of $b\}$
	\item $\{$Strings ending with $c\}$
	\item $\{$Strings with an even number of $a$ and odd number of $b$ and ending with $c\}$
	\end{enumerate}

\item Find a regular grammar for each language of exercises \ref{ex01} and \ref{exabc}.

\item Find a regular grammar for each automaton of exercises \ref{exunion} and \ref{exconcat}.
 
\end{enumerate}

\end{document}
