%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
%\usepackage{ucs}
\usepackage{times}
% A tribute to the worthy AMS:
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
%
\usepackage{mathrsfs}
\usepackage{wasysym}
\usepackage{url}
%
\usepackage{graphics}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,positioning}
\usepackage{hyperref}
%
\newenvironment{qcm}{\relax}{\relax}
\newenvironment{qvar}{\relax}{\relax}
\newcounter{quescnt}
\newenvironment{question}%
{\stepcounter{quescnt}\bigskip\noindent\textbf{Question~\arabic{quescnt}.}\par\nobreak}
{\relax}
\newcounter{answcnt}[quescnt]
\newcommand\answer{%
\stepcounter{answcnt}\smallskip\textbf{(\Alph{answcnt})}~}
\let\rightanswer=\answer
%
\DeclareUnicodeCharacter{00A0}{~}
\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
%
\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
%
\newif\ifcorrige
\corrigetrue
%
%
% NOTE: compile dot files with
% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot  > file.tex
\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
\tikzstyle{state}=[]
\tikzstyle{final}=[accepting by arrow]
%
%
%
\begin{document}
\ifcorrige
\title{INF105\\Contrôle de connaissances — Corrigé\\{\normalsize Théorie des langages}}
\else
\title{INF105\\Contrôle de connaissances\\{\normalsize Théorie des langages}}
\fi
\author{}
\date{(date à remplir)}
\maketitle

\pretolerance=8000
\tolerance=50000

\vskip1truein\relax

\noindent\textbf{Consignes.}

Ce contrôle de connaissances est un QCM (questionnaire à choix
multiples).  Chaque question admet une unique réponse correcte.  Les
questions sont totalement indépendantes les unes des autres.  La
sélection des questions et l'ordre ont été tirés aléatoirement et
n'obéissent donc à aucune logique particulière.

La réponse est attendue sous forme d'une liste de numéros de question
suivie de la réponse proposée : par exemple, « \verb=1A 2B 4D= » pour
signifier que la réponse proposée à la question 1 est (A), la réponse
proposée à la question 2 est (B), et la réponse proposée à la
question 4 est (D).

Une réponse incorrecte sera (deux fois) plus fortement pénalisée
qu'une absence de réponse : il est donc préférable de ne pas répondre
à une question que de répondre aléatoirement.

\medbreak

Durée : (à remplir)

\vfill

{\tiny\noindent
\immediate\write18{sh ./vc > vcline.tex}
Git: \input{vcline.tex}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}

\pagebreak

\begin{qcm}


%
%
%

\begin{qvar}

\begin{question}

Lequel des mots suivants est un sous-mot de $abcabcabc$ ?

\rightanswer
$acbac$

\answer
$abacbab$

\answer
$aabbcc$

\answer
$acbba$

\end{question}

\begin{question}

Lequel des mots suivants est un sous-mot de $abcabcbca$ ?

\rightanswer
$acbba$

\answer
$abacbab$

\answer
$aabbcc$

\answer
$acbac$

\end{question}

\end{qvar}


%
%
%

\begin{qvar}

\begin{question}

Soit $w$ un mot quelconque sur un alphabet $\Sigma$.  Le langage des
sous-mots de $w$ est...

\rightanswer
fini et rationnel

\answer
fini mais pas rationnel

\answer
rationnel mais pas fini

\answer
ni fini ni rationnel

\end{question}

\begin{question}

Soit $w$ un mot quelconque sur un alphabet $\Sigma$.  Le langage des
mots dont $w$ est un sous-mot est...

\rightanswer
rationnel mais pas fini

\answer
fini et rationnel

\answer
fini mais pas rationnel

\answer
ni fini ni rationnel

\end{question}

\end{qvar}


%
%
%

\begin{question}

Lequel des mots suivants appartient au langage dénoté par l'expression
rationnelle $(ab|ba){*}$ ?

\rightanswer
$abbaab$

\answer
$abaabb$

\answer
$aaabbb$

\answer
$abbabba$

\end{question}


%
%
%

\begin{qvar}

\begin{question}

Laquelle des expresssions rationnelles suivantes est équivalente
à $a{*}(bba{*}){*}$ ?

\rightanswer
$(a|bb){*}$

\answer
$a{*}(bb){*}a{*}$

\answer
$a{*}bba{*}$

\answer
$(abba){*}$

\end{question}

\begin{question}

Lequel des mots suivants appartient au langage dénoté par l'expression
rationnelle $a{*}(bba{*}){*}$ ?

\rightanswer
$abbabba$

\answer
$aaabbb$

\answer
$abbaab$

\answer
$abaabb$

\end{question}

\end{qvar}


%
%
%

\begin{qvar}

\begin{question}

Le langage engendré par la grammaire hors-contexte $S \rightarrow
abS\;|\;baS\;|\;\varepsilon$ est...

\rightanswer
rationnel et algébrique

\answer
rationnel mais pas algébrique

\answer
algébrique mais pas rationnel

\answer
ni algébrique ni rationnel

\end{question}

\begin{question}

Le langage engendré par la grammaire hors-contexte $S \rightarrow
abS\;|\;Sba\;|\;\varepsilon$ est...

\rightanswer
algébrique mais pas rationnel

\answer
rationnel et algébrique

\answer
rationnel mais pas algébrique

\answer
ni algébrique ni rationnel

\end{question}

\end{qvar}


%
%
%

\begin{qvar}

\begin{question}

Soit $L := \{a^{2^i} : i\in\mathbb{N}\}$ l'ensemble des mots sur
$\Sigma := \{a\}$ dont la longueur est une puissance de $2$.  Ce
langage $L$ est...

\rightanswer
décidable mais non algébrique

\answer
algébrique mais non rationnel

\answer
rationnel mais infini

\answer
fini

\answer
semi-décidable mais non décidable

\end{question}

\begin{question}

Soit $L := \{a^{12i} : i\in\mathbb{N}\}$ l'ensemble des mots sur
$\Sigma := \{a\}$ dont la longueur est multiple de $12$.  Ce
langage $L$ est...

\rightanswer
rationnel mais infini

\answer
décidable mais non algébrique

\answer
algébrique mais non rationnel

\answer
fini

\answer
semi-décidable mais non décidable

\end{question}

\end{qvar}


%
%
%

\begin{qvar}

\begin{question}

Un alphabet $\Sigma$ étant fixé, si $r$ est une expression rationnelle
sur $\Sigma$, existe-t-il toujours une expression rationnelle $r'$ qui
dénote le langage formé des mots qui \emph{ne vérifient pas} $r$ ?

\rightanswer
oui, et on dispose d'un algorithme permettant de calculer $r'$ en
fonction de $r$

\answer
oui, mais on ne dispose pas d'algorithme permettant de calculer $r'$
en fonction de $r$

\answer
non, ce langage n'est pas forcément rationnel

\end{question}

\begin{question}

Un alphabet $\Sigma$ étant fixé, si $r_1$ et $r_2$ sont deux
expressions rationnelles sur $\Sigma$, existe-t-il toujours une
expression rationnelle $r'$ qui dénote le langage formé des mots qui
vérifient \emph{à la fois} $r_1$ \emph{et} $r_2$ ?

\rightanswer
oui, et on dispose d'un algorithme permettant de calculer $r'$ en
fonction de $r_1$ et $r_2$

\answer
oui, mais on ne dispose pas d'algorithme permettant de calculer $r'$
en fonction de $r_1$ et $r_2$

\answer
non, ce langage n'est pas forcément rationnel

\end{question}

\end{qvar}


%
%
%

\begin{question}

L'automate fini sur l'alphabet $\Sigma := \{a,b\}$ représenté
ci-dessous

\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$};
\node (q2) at (70bp,0bp) [draw,circle,state] {$2$};
\node (q3) at (140bp,0bp) [draw,circle,state,final] {$3$};
  \draw [->] (q1) to[loop above] node[auto] {$a$} (q1);
  \draw [->] (q1) to node[auto] {$\varepsilon$} (q2);
  \draw [->] (q2) to node[auto] {$b$} (q3);
\end{tikzpicture}
\end{center}

\noindent est-il...

\rightanswer
un automate fini non-déterministe à transitions spontanées

\answer
un automate fini déterministe incomplet à transitions spontanées

\end{question}


%
%
%

\begin{question}

L'élimination des transitions spontanées sur l'automate fini sur
l'alphabet $\Sigma := \{a,b\}$ représenté ci-dessous

\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$};
\node (q2) at (70bp,0bp) [draw,circle,state] {$2$};
\node (q3) at (140bp,0bp) [draw,circle,state,final] {$3$};
  \draw [->] (q1) to[loop above] node[auto] {$a$} (q1);
  \draw [->] (q1) to node[auto] {$\varepsilon$} (q2);
  \draw [->] (q2) to node[auto] {$b$} (q3);
\end{tikzpicture}
\end{center}

\noindent s'obtient-elle...

\rightanswer
en supprimant la transition étiquetée $\varepsilon$ reliant $1$ à $2$
et en ajoutant une transition étiquetée $b$ reliant $1$ à $3$

\answer
en supprimant la transition étiquetée $\varepsilon$ reliant $1$ à $2$
et en ajoutant une transition étiquetée $a$ reliant $1$ à $3$

\answer
en remplaçant la transition étiquetée $\varepsilon$ reliant $1$ à $2$
par une transition étiquetée $b$ (toujours reliant $1$ à $2$)

\answer
en remplaçant la transition étiquetée $\varepsilon$ reliant $1$ à $2$
par une transition étiquetée $a$ (toujours reliant $1$ à $2$)

\end{question}


\end{qcm}
%
%
%
\end{document}