QCM theorie des langages

Théorie des langages
Remarque :
Plusieurs bonnes réponses pour certaines questions

Un langage rationnel est :
reconnaissable par automates à piles
reconnaissable par machine de Turing
reconnaissable uniquement par automate fini
 Un langage régulier est :
reconnaissable par automates à piles
reconnaissable par machine de Turing
reconnaissable uniquement par automate fini
Existe -il une grammaire algébrique ( non contextuelle ) qui engendre l'ensemble des mots : , où n entier.
oui non
Existe t-il un automate en 4 états reconnaissent tous les mots contenant bb au moins une fois et ne contenant pas aa.
oui   non
L'ensemble des mots de la langue arabe est :
rationnel
régulier non rationnel
reconnaissable par machine de Turing non régulier
rien de ce qui précède
L'ensemble des mots sur l'alphabet (a,b) qui contiennent deux fois plus de a que de b est :
rationnel
régulier non rationnel
reconnaissable par machine de Turing non régulier
rien de ce qui précède
  Pour tout automate fini non-déterministe, il existe un automate fini déterministe équivalent ?
vrai faux
Pour tout automate à piles non-déterministe, il existe un automate à piles déterministe équivalent ?
vrai faux

Sommaire du site Cryzalid

Omnes enim qui acceperint gladium, gladio peribunt
  Ecrire au webmestre


 

 retour à l'accueil