%% 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{12 juin 2020} \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{question} Soit $w$ un mot quelconque sur un alphabet $\Sigma$. Le langage formé 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 formé 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} % % % \begin{question} Lequel des mots suivants appartient au langage dénoté par l'expression rationnelle $(ab|ba){*}$ ? \rightanswer $abbaab$ \answer $abaabb$ \answer $aaabbb$ \answer $abbbba$ \end{question} % % % \begin{qvar} \begin{question} Quel langage dénote l'expression rationnelle $(aa{*}){*}$ sur l'alphabet $\Sigma := \{a\}$ ? \rightanswer l'ensemble $\Sigma^*$ de tous les mots \answer l'ensemble $\{w\in\Sigma^* : |w|\geq 1\}$ des mots non vides \answer l'ensemble $\{w\in\Sigma^* : |w|\geq 2\}$ des mots de longueur au moins deux \answer l'ensemble $\{w\in\Sigma^* : |w|\in 2\mathbb{N}\}$ des mots de longueur paire \end{question} \begin{question} Quel langage dénote l'expression rationnelle $aa{*}(aa{*}){*}$ sur l'alphabet $\Sigma := \{a\}$ ? \rightanswer l'ensemble $\{w\in\Sigma^* : |w|\geq 1\}$ des mots non vides \answer l'ensemble $\Sigma^*$ de tous les mots \answer l'ensemble $\{w\in\Sigma^* : |w|\geq 2\}$ des mots de longueur au moins deux \answer l'ensemble $\{w\in\Sigma^* : |w|\in 2\mathbb{N}\text{~et~}|w|>0\}$ des mots de longueur paire non nulle \end{question} \end{qvar} % % % \begin{qvar} \begin{question} Quel langage dénote l'expression rationnelle $(ba{*}){*}$ sur l'alphabet $\Sigma := \{a,b\}$ ? \rightanswer l'ensemble des mots qui sont soit le mot vide soit commencent par un $b$ \answer l'ensemble $\Sigma^*$ de tous les mots \answer l'ensemble $\{w\in\Sigma^* : |w|\geq 1\}$ des mots non vides \answer l'ensemble $\{(ba)^i : i\in\mathbb{N}\}$ des répétitions arbitraires du mot $ba$ \answer l'ensemble des mots commençant et finissant par un $b$ \answer l'ensemble des mots commençant par $b$ et finissant par $a$ \end{question} \begin{question} Quel langage dénote l'expression rationnelle $a{*}(ba{*}){*}$ sur l'alphabet $\Sigma := \{a\}$ ? \rightanswer l'ensemble $\Sigma^*$ de tous les mots \answer l'ensemble des mots qui sont soit le mot vide soit commencent par un $b$ \answer l'ensemble $\{w\in\Sigma^* : |w|\geq 1\}$ des mots non vides \answer l'ensemble $\{(ba)^i : i\in\mathbb{N}\}$ des répétitions arbitraires du mot $ba$ \answer l'ensemble des mots commençant et finissant par un $a$ \answer l'ensemble des mots finissant par $a$ \end{question} \end{qvar} % % % \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 $abbbba$ \answer $aaabbb$ \answer $abbaab$ \answer $abaabb$ \end{question} \end{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} % % % \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 \answer non semi-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 \answer non semi-décidable \end{question} % % % \begin{question} Soit $L := \{w \in \Sigma^* : |w|\geq 42\}$ l'ensemble des mots sur $\Sigma := \{a,b\}$ dont la longueur est supérieure ou égale à $42$. 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 \answer non semi-décidable \end{question} % % % \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} % % % \begin{qvar} \begin{question} Soit $\mathscr{A}$ 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,b$} (q1); \draw [->] (q1) to node[auto] {$a$} (q2); \draw [->] (q2) to node[auto] {$b$} (q3); \end{tikzpicture} \end{center} Le nombre d'états de l'automate canonique (= automate fini déterministe complet ayant le nombre minimum possible d'états) équivalent à $\mathscr{A}$ vaut : \rightanswer trois ($3$) \answer un ($1$) \answer deux ($2$) \answer quatre ($4$) \end{question} \begin{question} Soit $r := (a|b){*}ab$, expression rationnelle sur l'alphabet $\Sigma := \{a,b\}$. Le nombre d'états de l'automate canonique (= automate fini déterministe complet ayant le nombre minimum possible d'états) reconnaissant le langage $L(r)$ dénoté par $r$ vaut : \rightanswer trois ($3$) \answer un ($1$) \answer deux ($2$) \answer quatre ($4$) \end{question} \begin{question} Soit $L := \Sigma^*\{ab\} = \{wab : w\in\Sigma^*\}$, le langage des mots sur l'alphabet $\Sigma := \{a,b\}$ ayant $ab$ pour suffixe. Le nombre d'états de l'automate canonique (= automate fini déterministe complet ayant le nombre minimum possible d'états) reconnaissant le langage $L$ vaut : \rightanswer trois ($3$) \answer un ($1$) \answer deux ($2$) \answer quatre ($4$) \end{question} \end{qvar} % % % \begin{qvar} \begin{question} Soit $\mathscr{A}$ 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 node[auto] {$a$} (q2); \draw [->] (q2) to node[auto] {$b$} (q3); \draw [->] (q3) to[loop above] node[auto] {$a,b$} (q3); \end{tikzpicture} \end{center} Le nombre d'états de l'automate canonique (= automate fini déterministe complet ayant le nombre minimum possible d'états) équivalent à $\mathscr{A}$ vaut : \rightanswer quatre ($4$) \answer trois ($3$) \answer un ($1$) \answer deux ($2$) \end{question} \begin{question} Soit $r := ab(a|b){*}$, expression rationnelle sur l'alphabet $\Sigma := \{a,b\}$. Le nombre d'états de l'automate canonique (= automate fini déterministe complet ayant le nombre minimum possible d'états) reconnaissant le langage $L(r)$ dénoté par $r$ vaut : \rightanswer quatre ($4$) \answer trois ($3$) \answer un ($1$) \answer deux ($2$) \end{question} \begin{question} Soit $L := \{ab\}\Sigma^* = \{abw : w\in\Sigma^*\}$, le langage des mots sur l'alphabet $\Sigma := \{a,b\}$ ayant $ab$ pour préfixe. Le nombre d'états de l'automate canonique (= automate fini déterministe complet ayant le nombre minimum possible d'états) reconnaissant le langage $L$ vaut : \rightanswer quatre ($4$) \answer trois ($3$) \answer un ($1$) \answer deux ($2$) \end{question} \end{qvar} % % % \begin{question} Lequel des langages suivants sur $\Sigma := \{a,b\}$ \emph{n'est pas} rationnel ? \rightanswer l'ensemble des mots dont le nombre total de $a$ vaut au moins $6$ de plus que le nombre total de $b$ \answer l'ensemble des mots dont la longueur est multiple de $6$ \answer l'ensemble des mots dont le nombre total de $a$ est multiple de $6$ \answer l'ensemble des mots commençant par $6$ fois la lettre $a$ \answer l'ensemble des mots dont le nombre total de $a$ vaut au moins $6$ \end{question} % % % \begin{question} Lequel des langages suivants sur $\Sigma := \{a\}$ est rationnel ? \rightanswer l'ensemble des mots dont la longueur est multiple de $42$ et supérieure ou égale à $1729$ \answer l'ensemble des mots dont la longueur est une puissance $42$-ième (c'est-à-dire de la forme $i^{42}$ pour $i\in\mathbb{N}$) \answer l'ensemble des mots dont la longueur est un nombre premier \answer l'ensemble des mots dont la longueur est une puissance de $42$ (c'est-à-dire de la forme $42^i$ pour $i\in\mathbb{N}$) \end{question} % % % \begin{qvar} \begin{question} Lequel des langages suivants sur $\Sigma := \{a,b,c\}$ est rationnel ? \rightanswer l'ensemble des mots de longueur $\geq 6$ dont le suffixe de longueur $6$ coïncide avec le préfixe de longueur $6$ (c'est-à-dire que les six dernières lettres sont les mêmes que les six premières, dans le même ordre) \answer l'ensemble des mots qui sont des palindromes, c'est-à-dire $\{w\in\Sigma^* : w = w^{\textsf{R}}\}$ (où $w^{\textsf{R}}$ désigne le mot miroir de $w$) \answer l'ensemble des mots qui sont des carrés, c'est-à-dire $\{w^2 : w\in\Sigma^*\}$ \answer l'ensemble des mots ayant le même nombre total de $a$ que de $b$ que de $c$ \end{question} \begin{question} Lequel des langages suivants sur $\Sigma := \{a,b,c\}$ est rationnel ? \rightanswer l'ensemble des mots de longueur $\geq 6$ dont le suffixe de longueur $6$ est le miroir du préfixe de longueur $6$ (c'est-à-dire que les six dernières lettres sont les mêmes que les six premières, mais dans l'ordre inverse) \answer l'ensemble des mots qui sont des palindromes, c'est-à-dire $\{w\in\Sigma^* : w = w^{\textsf{R}}\}$ (où $w^{\textsf{R}}$ désigne le mot miroir de $w$) \answer l'ensemble des mots qui sont des carrés, c'est-à-dire $\{w^2 : w\in\Sigma^*\}$ \answer l'ensemble des mots ayant le même nombre total de $a$ que de $b$ que de $c$ \end{question} \end{qvar} % % % \begin{question} Quel langage reconnaît 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 (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] {$b$} (q4); \draw [->] (q1) to node[auto] {$b$} (q3); \draw [->] (q2) to node[auto] {$a$} (q4); \draw [->] (q2) to[loop right] node[auto] {$a,b$} (q2); \draw [->] (q3) to[loop left] node[auto] {$a,b$} (q3); \end{tikzpicture} \end{center} \rightanswer le langage formé des mots de longueur $\geq 2$ dont la dernière lettre est égale à la première \answer le langage formé des mots comportant au moins deux $a$ et comportant au moins deux $b$ \answer le langage formé des mots comportant (quelque part) deux lettres identiques consécutives \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} Quel langage reconnaît 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 (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] {$b$} (q4); \draw [->] (q1) to node[auto] {$b$} (q3); \draw [->] (q2) to node[auto] {$a$} (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 comportant (quelque part) deux lettres identiques consécutives \answer le langage formé des mots de longueur $\geq 2$ dont la dernière lettre est égale à la première \answer le langage formé des mots comportant au moins deux $a$ et 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} Quel langage reconnaît 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 (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] {$b$} (q4); \draw [->] (q1) to node[auto] {$a$} (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 ayant $ab$ comme facteur \answer le langage formé des mots comportant (quelque part) deux lettres identiques consécutives \answer le langage formé des mots de longueur $\geq 2$ dont la dernière lettre est égale à la première \answer le langage formé des mots comportant au moins deux $a$ et 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 rien du tout car ce n'est pas un automate fini valable \end{question} % % % \begin{question} Le langage sur $\Sigma = \{a,b\}$ engendré par la grammaire hors-contexte $S \rightarrow aSa\;|\;bSb\;|\;\varepsilon\;|\;a\;|\;b$ est... \rightanswer l'ensemble des mots qui sont des palindromes, c'est-à-dire $\{w\in\Sigma^* : w = w^{\textsf{R}}\}$ (où $w^{\textsf{R}}$ désigne le mot miroir de $w$) \answer l'ensemble des mots qui sont des carrés, c'est-à-dire $\{w^2 : w\in\Sigma^*\}$ \answer l'ensemble des expressions bien-parenthésées si $a$ désigne une parenthèse ouvrante et $b$ une parenthèse fermante \answer l'ensemble des mots ayant le même nombre total de $a$ que de $b$ \answer l'ensemble $\Sigma^*$ de tous les mots sur $\Sigma$ \end{question} % % % \begin{qvar} \begin{question} Le langage sur $\Sigma = \{a,b\}$ engendré par la grammaire hors-contexte $S \rightarrow aSbS\;|\;\varepsilon$ est... \rightanswer l'ensemble des expressions bien-parenthésées si $a$ désigne une parenthèse ouvrante et $b$ une parenthèse fermante \answer l'ensemble des mots qui sont des palindromes, c'est-à-dire $\{w\in\Sigma^* : w = w^{\textsf{R}}\}$ (où $w^{\textsf{R}}$ désigne le mot miroir de $w$) \answer l'ensemble des mots qui sont des carrés, c'est-à-dire $\{w^2 : w\in\Sigma^*\}$ \answer l'ensemble des mots ayant le même nombre total de $a$ que de $b$ \answer l'ensemble $\Sigma^*$ de tous les mots sur $\Sigma$ \end{question} \begin{question} Lequel des mots suivants appartient au langage sur $\Sigma = \{a,b\}$ engendré par la grammaire hors-contexte $S \rightarrow aSbS\;|\;\varepsilon$ ? \rightanswer $abaaabbabb$ \answer $abbaabbaab$ \answer $aaabbabbba$ \answer $aaaaabbbab$ \end{question} \end{qvar} % % % \begin{question} Le langage sur $\Sigma = \{a,b\}$ engendré par la grammaire hors-contexte dont les règles sont $S \rightarrow TT$ et $T \rightarrow aT\;|\;bT\;|\;\varepsilon$ est... \rightanswer l'ensemble $\Sigma^*$ de tous les mots sur $\Sigma$ \answer l'ensemble des mots qui sont des palindromes, c'est-à-dire $\{w\in\Sigma^* : w = w^{\textsf{R}}\}$ (où $w^{\textsf{R}}$ désigne le mot miroir de $w$) \answer l'ensemble des mots qui sont des carrés, c'est-à-dire $\{w^2 : w\in\Sigma^*\}$ \answer l'ensemble des expressions bien-parenthésées si $a$ désigne une parenthèse ouvrante et $b$ une parenthèse fermante \answer l'ensemble des mots ayant le même nombre total de $a$ que de $b$ \end{question} % % % \begin{question} Supposons fixé un modèle standard de calculabilité, par exemple la machine de Turing. L'ensemble des couples $(e,n)$ formés d'un programme $e$ et d'un entier naturel $n$ et vérifiant la propriété « l'exécution du programme $e$ termine en exactement $n$ étapes » est-il : \rightanswer décidable \answer semi-décidable mais non décidable \answer non semi-décidable \end{question} % % % \begin{question} Supposons fixé un modèle standard de calculabilité, par exemple la machine de Turing. L'ensemble des programmes $e$ dont l'exécution ne termine jamais est-il : \rightanswer non semi-décidable \answer décidable \answer semi-décidable mais non décidable \end{question} % % % \begin{question} Supposons fixé un modèle standard de calculabilité, par exemple la machine de Turing, et soit $\Sigma := \{a,b,c\}$. L'ensemble des couples $(r,w)$ formés d'une expression rationnelle $r$ sur $\Sigma$ et d'un mot $w$ sur $\Sigma$ vérifiant $r$ (c'est-à-dire appartenant au langage dénoté par $r$) est-il : \rightanswer décidable \answer semi-décidable mais non décidable \answer non semi-décidable \end{question} \end{qcm} % % % \end{document}