QCM - Grammaires non-contextuelles

QCM - Grammaires non-contextuelles

Question 1. Une grammaire non-contextuelle $G = (\Sigma, V, R, S)$ est composée de :

Un alphabet $\Sigma$, un ensemble de variables $V$, des règles $R$, et un symbole initial $S$Uniquement d'un alphabet et de règlesD'un automate et d'une expression régulièreD'un ensemble de mots

Question 2. Une règle de production $X \to \alpha$ signifie que :

$X$ peut être remplacé par $\alpha$ dans une dérivation$\alpha$ est toujours égal à $X$$X$ est un terminal$\alpha$ est le symbole initial

Question 3. Le langage engendré par une grammaire $G$ est :

L'ensemble des variables de $G$L'ensemble des mots $w \in \Sigma^*$ tels que $S \Rightarrow^* w$L'ensemble des règles de $G$L'alphabet de $G$

Question 4. La grammaire $S \to aSb \mid \varepsilon$ engendre le langage :

$(ab)^*$$\{a^n b^n \mid n \in \mathbb{N}\}$$a^* b^*$$\{a^n b^m \mid n \leq m\}$

Question 5. Un langage non-contextuel est :

Un langage régulierUn langage engendré par une grammaire non-contextuelleUn langage finiUn langage reconnu par un automate fini

Question 6. La relation entre langages réguliers et langages non-contextuels est :

Ils sont égauxTout langage régulier est non-contextuel, mais pas l'inverseTout langage non-contextuel est régulierIls sont disjoints

Question 7. Une grammaire est ambiguë si :

Elle ne génère aucun motIl existe un mot ayant plusieurs arbres de dérivationElle a plusieurs symboles initiauxElle génère un langage infini

Question 8. Une grammaire régulière (à droite) a des règles de la forme :

$X \to aY$ où $a$ est un terminal et $Y$ une variable (ou $\varepsilon$)$X \to YZ$ où $Y$ et $Z$ sont des variables$X \to ab$ où $a$ et $b$ sont des terminauxN'importe quelle forme

Question 9. Un langage est régulier si et seulement s'il est engendré par :

Une grammaire non-contextuelle quelconqueUne grammaire régulièreUne grammaire ambiguëAucune grammaire

Question 10. L'ensemble des langages non-contextuels est stable par :

Union, concaténation et étoile de KleeneIntersection seulementComplémentation seulementAucune opération