%% 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{graphics}
\usepackage[usenames,dvipsnames]{xcolor}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,positioning}
%
\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})}~}
\newcommand\rightanswer{%
\stepcounter{answcnt}\smallskip\leavevmode\llap{$\rightarrow$}\textbf{(\Alph{answcnt})}~}
%
\DeclareUnicodeCharacter{00A0}{~}
\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
%
\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
%
\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
\tikzstyle{state}=[]
\tikzstyle{final}=[accepting by arrow]
%
%
%
\begin{document}

\textbf{Questions pour INF105 pour le QCM du 2022-06-02.}

Chaque question comporte \emph{une et une seule réponse correcte}.
Elle a été indiquée par une flèche ci-dessous :


%
%
%

\begin{question}

Parmi les différents langages ci-dessous sur l'alphabet $\Sigma :=
\{a,b\}$, qui sont tous des sous-ensembles du langage rationnel $L_0
:= L(a{*}b{*}) = \{a^i b^j : i,j \in \mathbb{N}\}$, un seul est
rationnel : lequel ?

\answer
Le langage $\{a^i b^j : i=j\}$ formé des mots de $L_0$ ayant le même
nombre de $a$ que de $b$.

\answer
Le langage $\{a^i b^j : i\geq j\}$ formé des mots de $L_0$ ayant au
moins autant de $a$ que de $b$.

\answer
Le langage $\{a^i b^j : i\neq j\}$ formé des mots de $L_0$ ayant un
nombre différent de $a$ et de $b$.

\rightanswer
Le langage $\{a^i b^j : i\equiv j \pmod{12}\}$ formé des mots de $L_0$
tels que le nombre de $a$ et de $b$ soient congrus l'un à l'autre modulo $12$
(c'est-à-dire que la différence entre ces deux nombres soit multiple
de $12$).

\end{question}


%
%
%

\begin{question}

Parmi les différents langages ci-dessous sur l'alphabet $\Sigma :=
\{a,b\}$, un seul \emph{n'est pas} rationnel : lequel ?

\answer
Le langage des mots $w$ comportant exactement $42$ lettres $a$ (au
total, c'est-à-dire $|w|_a = 42$).

\rightanswer
Le langage des mots $w$ comportant exactement autant de lettres $a$
que de lettres $b$ (au total, c'est-à-dire $|w|_a = |w|_b$).

\answer
Le langage des mots qui \emph{n'ont pas} le mot “$abbab$” comme facteur.

\answer
Le langage des mots qui \emph{n'ont pas} le mot “$abbab$” comme sous-mot.

\answer
Le langage des mots qui \emph{ne sont pas} un sous-mot de “$abbab$”.

\end{question}


%
%
%

\begin{question}

Parmi les différents langages ci-dessous sur l'alphabet $\Sigma :=
\{a,b,c\}$, un seul \emph{n'est pas} rationnel : lequel ?

\answer
Le langage des mots de longueur $\geq 3$ dont la troisième lettre (à
partir du début) est identique à la troisième lettre à partir de la
fin.

\answer
Le langage des mots de longueur $\geq 3$ dont chaque troisième lettre
(c'est-à-dire la troisième, la sixième, la neuvième, etc., jusqu'à la
fin du mot) sont toutes identiques.

\rightanswer
Le langage des mots de longueur impaire dont la lettre du milieu est
un $a$.

\end{question}


%
%
%

\begin{question}

Quel langage reconnaît l'automate fini sur l'alphabet $\Sigma :=
\{a,b\}$ représenté ci-dessous ?

\begin{center} %% NAME: q4
\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 (00bp,-70bp) [draw,circle,state] {$3$};
\node (q4) at (70bp,-70bp) [draw,circle,state,final] {$4$};
  \draw [->] (q1) to node[auto] {$a$} (q2);
  \draw [->] (q3) to node[auto] {$a$} (q4);
  \draw [->] (q1) to node[auto] {$b$} (q3);
  \draw [->] (q2) to node[auto] {$b$} (q4);
  \draw [->] (q1) to[loop above] node[auto] {$a,b$} (q1);
  \draw [->] (q4) to[loop below] node[auto] {$a,b$} (q4);
\end{tikzpicture}
\end{center}

\rightanswer
Le langage formé des mots de longueur $\geq 2$ dont toutes les lettres
ne sont pas identiques.

\answer
Le langage formé des mots de longueur $\geq 2$ dont la dernière lettre
est identique à la première.

\answer
Le langage formé des mots comportant au moins deux $a$ ou bien
comportant au moins deux $b$.

\answer
Le langage formé des mots dont le nombre de $a$ et le nombre de $b$
sont tous les deux pairs.

\answer
Le langage formé des mots ayant $ab$ comme facteur.

\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} %% NAME: q5
\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 node[auto] {$a$} (q2);
  \draw [->] (q2) to node[auto] {$b$} (q3);
  \draw [->,out=270,in=270] (q3) to node[above] {$\varepsilon$} (q1);
\end{tikzpicture}
\end{center}

\noindent s'obtient-elle...

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

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

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

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

\end{question}


%
%
%

\begin{question}

Quel est le langage reconnu par l'automate ci-dessous ?

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

\rightanswer
$\{\varepsilon,a,b,ab\}$

\answer
$\{\varepsilon,ab\}$

\answer
$\{\varepsilon,a,b,ab,ba\}$

\answer
$\{\varepsilon,ab,ba\}$

\answer
$\{a,b,ab\}$

\answer
$\{ab\}$

\answer
$\varnothing$

\end{question}


%
%
%

\begin{question}

Quel est le langage reconnu par l'automate ci-dessous ?

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

\answer
$\{\varepsilon,a,b,ab\}$

\answer
$\{\varepsilon,ba\}$

\answer
$\{\varepsilon,a,b,ab,ba\}$

\answer
$\{\varepsilon,ab,ba\}$

\answer
$\{\varepsilon,a,b\}$

\rightanswer
$\{\varepsilon\}$

\answer
$\varnothing$

\end{question}


%
%
%

\begin{question}

L'automate canonique (= automate fini déterministe complet ayant le
nombre minimum possible d'états) équivalent à l'automate $\mathscr{A}$
représenté ci-dessous

\begin{center} %% NAME: q8
\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,final,accepting below] {$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] {$b$} (q2);
  \draw [->] (q2) to[loop above] node[auto] {$b$} (q2);
  \draw [->] (q2) to node[auto] {$a$} (q3);
  \draw [->] (q3) to[loop above] node[auto] {$a,b$} (q3);
\end{tikzpicture}
\end{center}

\noindent s'obtient-il...

\answer
En ne changeant rien (l'automate $\mathscr{A}$ est déjà minimal) ?

\rightanswer
En fusionnant les états $2$ et $3$ (donnant un automate minimal à deux états) ?

\answer
En fusionnant les états $1$ et $2$ (donnant un automate minimal à deux états) ?

\answer
En fusionnant tous les états (donnant un automate minimal à un seul état) ?

\end{question}


%
%
%

\begin{question}

Parmi les expressions rationnelles ci-dessous, laquelle dénote le
langage reconnu par l'automate suivant ?

\begin{center} %% NAME: q9
\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,final] {$2$};
  \draw [->] (q1) to[loop above] node[auto] {$a$} (q1);
  \draw [->,out=30,in=150] (q1) to node[auto] {$\varepsilon$} (q2);
  \draw [->,out=210,in=330] (q2) to node[auto] {$\varepsilon$} (q1);
  \draw [->] (q2) to[loop above] node[auto] {$b$} (q2);
\end{tikzpicture}
\end{center}

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

\answer
$(ab|ba){*}$

\answer
$(aa|bb){*}$

\answer
$a{*}\,|\,b{*}$

\answer
$a(a|b){*}b$

\end{question}


%
%
%

\begin{question}

Parmi les expressions rationnelles ci-dessous, laquelle dénote le
langage reconnu par l'automate suivant ?  (Note : l'expression
correcte ci-dessous est obtenue en éliminant les états dans
l'ordre $3,2,1$.)

\begin{center} %% NAME: q10
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (q1) at (0bp,0bp) [draw,circle,state] {$1$};
\node (q2) at (60bp,35bp) [draw,circle,state] {$2$};
\node (q3) at (60bp,-35bp) [draw,circle,state] {$3$};
  \draw [<-] (q1) -- ++(-20bp,20bp);
  \draw [->] (q1) -- ++(-20bp,-20bp);
  \draw [->,out=90,in=150] (q1) to node[auto] {$a$} (q2);
  \draw [->,out=330,in=30] (q2) to node[auto] {$b$} (q3);
  \draw [->,out=210,in=270] (q3) to node[auto] {$c$} (q1);
  \draw [->] (q2) to node[auto] {$a$} (q1);
  \draw [->] (q3) to node[auto] {$b$} (q2);
  \draw [->] (q1) to node[auto] {$c$} (q3);
\end{tikzpicture}
\end{center}

\rightanswer
$(cc\,|\,(a|cb)(bb){*}(a|bc)){*}$

\answer
$(a(b(cc){*}b){*}a){*}$

\answer
$(abc|cba){*}$

\answer
$(aa|b(aa|cc)b|cc){*}$

\end{question}


%
%
%
\end{document}