diff options
| -rwxr-xr-x | misc/quiz-extract-automata.pl | 53 | ||||
| -rw-r--r-- | quiz-20220602.tex | 432 |
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} |