Write another short quiz.

2 files changed, 485 insertions, 0 deletions

diff --git a/misc/quiz-extract-automata.pl b/misc/quiz-extract-automata.pl
new file mode 100755
index 0000000..8327ce3
--- /dev/null
+++ b/misc/quiz-extract-automata.pl
@@ -0,0 +1,53 @@
+#! /usr/local/bin/perl -w
+
+use strict;
+use warnings;
+
+my $inputfile = $ARGV[0];
+die "please pass input file as argument" unless defined($inputfile);
+my $outputdir = "/tmp/automata";
+
+my $f;
+
+open $f, "<", $inputfile or die "can't open $inputfile: $!";
+my %automata;
+my $thisname;
+while (<$f>) {
+    $thisname = undef if defined($thisname) && /^\\end\{center\}/;
+    $automata{$thisname} .= $_ if defined($thisname);
+    $thisname = $1 if /^\\begin\{center\}\s*\%+\s*NAME:\s*(\S+)/;
+}
+close $f;
+
+my $prologue = <<'__EOF__';
+\documentclass[crop,tikz]{standalone}
+%
+%
+%
+\usepackage{tikz}
+\usetikzlibrary{arrows,automata,positioning}
+%
+\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
+\tikzstyle{state}=[]
+\tikzstyle{final}=[accepting by arrow]
+%
+%
+%
+__EOF__
+
+mkdir $outputdir;
+
+foreach my $name (keys(%automata)) {
+    chdir $outputdir;
+    print "Processing $name\n";
+    open $f, ">", "${outputdir}/${name}.tex";
+    print $f $prologue;
+    print $f "\\begin{document}\n\n";
+    print $f $automata{$name};
+    print $f "\n\\end{document}\n";
+    close $f;
+    system "pdflatex", "${name}.tex";
+    system "pdf2svg", "${name}.pdf", "${name}.raw.svg";
+    system "scour", "-i", "${name}.raw.svg", "-o", "${name}.svg";
+    system "rsvg-convert", "${name}.svg", "-d", "300", "-p", "300", "-b", "white", "-o", "${name}.png";
+}
diff --git a/quiz-20220602.tex b/quiz-20220602.tex
new file mode 100644
index 0000000..7e8ab0a
--- /dev/null
+++ b/quiz-20220602.tex
@@ -0,0 +1,432 @@
+%% 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 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}