Université de Pokhara

Niveau : Maîtrise Semestre - Printemps Année 2010

Programme : CS/CE Note maximale : 100
Cours : Théorie de la computation 60
Temps 4 heures.
Les candidats sont tenus de donner leurs réponses dans leurs propres mots dans la mesure du possible.
Les chiffres dans la marge indiquent les notes complètes.
Répondez à toutes les questions.

1 a) Define decision problems, function problems and search problems with examples. 7

b) Que voulez-vous dire par ensemble régulier ? Énoncez et prouvez le lemme de pompage pour les ensembles réguliers. 8

2 a) Pouvez-vous relier les expressions régulières et la grammaire hors contexte ? Si oui, comment ? Expliquez avec un 7
exemple.

b) Pouvons-nous utiliser un graphique comme outil de résolution de problèmes ? Si oui, comment ? Quel type de problème peut être résolu en utilisant 8
arbre couvrant ? Expliquer.

3 a) Que voulez-vous dire par forme normale ? Transformez la grammaire suivante en forme normale de Chomsky. 8

b) Définir les mouvements d'un PDA. Concevoir un PDA pour le langage suivant : 7
L= {anb2n: n>0}

4 a) Qu'est-ce que la description instantanée ? Concevez une machine de Turing qui reconnaît le langage de tous les 7
chaînes de longueur paire sur l'alphabet {a, b}.

b) La théorie de la computation traite de la théorie computationnelle et de la théorie de la complexité. 8

déclaration avec des exemples

5 a) Différencier entre les langages récursifs et les langages récursivement énumérables. Ces langages fournissent-ils 8
la notion de problèmes décidables et indécidables ? Expliquez.

b) Define class P and NP problem with examples. How does P and NP class problems reflect the notion 7
d'algorithmes déterministes et non-déterministes ? Expliquer.

6 a) Un DFA peut simuler le comportement d'un NFA en augmentant le nombre d'états. 7

avec un exemple.

b) Définition de la dérivation 8

7 Rédigez des notes courtes sur deux éléments : 2*5

a) Application des expressions régulières.
b) Problèmes traitables et non traitables.
c) Quelques énigmes informatiques
 Université de Pokhara
Maîtrise Semestre Année 2012
CS/CE Note maximale : 100
Cours : Théorie de la Computation 60
Temps 4 heures.
Les candidats doivent donner leurs réponses avec leurs propres mots autant que possible.
Les chiffres dans la marge indiquent les notes complètes.
Répondez à toutes les questions.

1 La théorie de la computation traite de la théorie des automates, de la théorie de la complexité et 10

théorie de la calculabilité. Expliquer.

2 Pour chaque expression régulière, il existe un automate fini et pour chaque fini 10
automate, il existe une expression régulière. Justifiez cette déclaration avec un exemple.

3 State and proof pumping lemma for context free language. 8

4 Quand une grammaire est-elle ambiguë ? Montrez que la grammaire suivante est ambiguë. 8
AB | aabB

5 Expliquez le processus d'élimination des symboles inutiles d'une CFG. Supprimez le symbole inutile. 8
à partir de la grammaire libre de contexte donnée.
S-> aB|bX
A->Mauvais|bSX|a
B->aSB|bBX
X->SBD|aBx|ad

6 Expliquez le déplacement d'un PDA. Concevez un PDA pour le langage L = { wcw }. r 8

7 La classe de langages acceptée par les automates à pile est exactement la classe des langages contextuels. 8
langues. Justifiez cette affirmation par un exemple.

8 Définir la description instantanée. Concevoir une machine de Turing qui calcule la fonction 7
f (m) = m + 1 pour chaque m appartenant à l'ensemble des nombres naturels.

9 Un langage récursif est un langage pour lequel il existe un algorithme qui peut déterminer si une chaîne appartient ou non 10
à ce langage en un temps fini pour toutes les chaînes possibles.

langue récursivement énumérable donne la notion de langage décidable et indécidable ?

Expliquer.

10 Explain decision problem, function problem and search problem with example. 8

11 Discutez brièvement de la théorie des fonctions récursives. 7

12 Discuter de la machine de Turing déterministe et de la machine de Turing non déterministe. Comment ces 8
Les machines donnent la notion de problèmes de classe P et de classe NP ? Expliquez.
 Université de Pokhara
Maître Semestre - Automne Année 2013
Programme : CS/CE Note maximale : 100
Cours : Théorie de la computation Moyenne de passage : 60
Temps 4 heures.
Les candidats sont tenus de donner leurs réponses dans leurs propres mots autant que possible.
Les chiffres dans la marge indiquent le total des points.
Répondez à toutes les questions.

1 Define decision problem, function problem and search problem with examples. 10

2 Que voulez-vous dire par ensemble régulier ? Énoncez et prouvez le lemme de pompage pour les ensembles réguliers. 10

3 Pouvez-vous relier les expressions régulières et la grammaire hors contexte ? Si oui, comment ? Expliquez avec 10
un exemple.

4 Que voulez-vous dire par forme normale ? Changez la grammaire suivante en forme normale de Chomsky. 10
aAAb

5 Définir les mouvements d'un PDA. Concevoir un PDA pour le langage suivant. L= {anb2n: n>0} 10

6 Qu'est-ce qu'une description instantanée ? Concevez une machine de Turing qui reconnaît le langage. 10
de toutes les chaînes de longueur paire sur l'alphabet {a, b}.

7 La théorie de la computation traite de la théorie computationnelle et de la théorie de la complexité. 10

cette déclaration avec des exemples.

8 Différenciez entre les langages récursifs et les langages récursivement énumérables. Ces langages 10
provide the notion of decidable and un-decidable problems? Explain.

9 Define class P and NP problem with examples. How does P and NP class problems reflect 10
la notion d'algorithme déterministe et non déterministe ? Expliquer.

10 Un DFA peut simuler le comportement d'un NFA en augmentant le nombre d'états. 10

déclaration avec un exemple.
 Université de Pokhara
Niveau : Master Semestre–Printemps Année 2013
Programme : CS/CE Note Maximale : 100
Cours : Théorie de la computation Notes de passage : 60
Temps 4 heures.
Les candidats doivent donner leurs réponses dans leurs propres mots dans la mesure du possible.
Les chiffres dans la marge indiquent les notes complètes.
Répondez à toutes les questions.

1 Énoncez le théorème d'Arden. Comment construisez-vous une expression régulière en utilisant le théorème d'Arden ? 10
Théorème ? Expliquez avec un exemple de votre propre.

2 « Un DFA peut simuler le comportement d'un NFA en augmentant le nombre d'états ». Justifiez cela.10
déclaration avec un exemple.

3 State the closure properties of regular expression. Also state and prove pumping lemma for 10
ensembles réguliers.

4 10B, et C sont des non-terminaux et a est un terminal.

La forme normale de Chomsky (CNF) est une forme de grammaire où chaque production est soit A -> BC, soit A -> a, où A,

Construisez une grammaire équivalente en CNF et GNF.

5 Expliquez le processus d'élimination des symboles et des productions inutiles d'une CFG. Simplifiez le 10
suivant la grammaire, en éliminant à la fois les productions unitaires et les productions et symboles inutiles.
S → A | Bb
A→C|a
B → aBa | b
C → aSa

6 Quand une grammaire est-elle ambiguë ? Prouvez que la grammaire suivante est ambiguë. E E
 * 10
E E
 +E E  - E x y

7 Pourquoi la PDA est-elle fonctionnellement plus puissante que la FA ? Expliquez. Concevez une PDA qui traite le langage. 10
L contenant un nombre égal de 0 et de 1 sur å = {0,1} et vérifier si la chaîne
w=001011 est-il accepté ou non.

8 Que voulez-vous dire par Description Instantanée ? Concevez une machine de Turing qui accepte tout. 10
la chaîne de longueur paire sur   }.

9 Différenciez entre les problèmes de classe P et de classe NP avec des exemples. Réflètent-ils le 10
notion de problèmes décidables et indécidables ? Expliquer.

10 Discutez brièvement de la théorie des fonctions récursives avec des exemples. 10

 Université de Pokhara
Master Semestre Année 2014
CS/CE Total des points : 100
Cours : Théorie de la computation Notes de passage : 60
Temps 4 heures.
Les candidats sont tenus de donner leurs réponses dans leurs propres mots autant que possible.
Les chiffres dans la marge indiquent des notes complètes.
Répondez à toutes les questions.

1 Comment pouvez-vous lier les expressions régulières et la grammaire ? Expliquez avec un exemple. 8

2 « Pour chaque automate fini, il existe une expression régulière équivalente. » Justifiez cela 10
déclaration avec un exemple.

3 État et preuve des propriétés de clôture pour le langage régulier. 10

4 Define derivation tree. When is a grammar ambiguous? Show that the following grammar is 10
ambigu
S->AB|aaB
A->a|Aa
B->b

5 Pourquoi avons-nous besoin de simplifier une grammaire ? Expliquez le processus d'élimination des productions nulles.
d'une grammaire. Simplifiez la grammaire suivante.
S->AB|C
A->B
B->aB|Bb|Є|a
C->aCb

6 Comment pouvez-vous décider si une langue est une langue sans contexte ou non ? Expliquez avec un 10
exemple.

7 « Pour chaque CFG, il existe un automate à pile équivalent. » Justifiez cette affirmation.8
avec un exemple.

8 Définir une description instantanée. Comment pouvez-vous déterminer la calculabilité d'un ... 10
fonction ? Expliquer avec un exemple.

9 Define recursive and recursively enumerable language. How can distinguish 8

entre problème décidable et problème non décidable ? Expliquez.

10 Discutez brièvement de la théorie des fonctions récursives. 8

10 10
« La machine de Turing est fonctionnellement plus puissante que l'AFA et le PDA ». Justifiez. Est-ce que le
La complexité des machines de Turing joue-t-elle un rôle dans la détermination des problèmes de classe P et de classe NP ? Expliquez.
 Université de Pokhara
Maître Semestre–Automne Année 2015
Programme : CS/CE Note maximale : 100
Cours : Théorie de la computation Notes de passage : 60
Temps 4 heures.
Les candidats sont tenus de donner leurs réponses dans leurs propres mots autant que possible.
Les chiffres dans la marge indiquent les notes complètes.
Répondez à toutes les questions.

1 Définissez la machine à états finis avec un exemple. Discutez des caractéristiques opérationnelles et 10
principe de fonctionnement des automates finis avec un exemple.

2 Pourquoi devons-nous supprimer les transitions epsilon des automates finis ? Expliquez-le. 10
processus d'élimination des mouvements epsilon d'un AF donné avec un exemple.

3 Comment pouvez-vous déterminer la classe de langue des automates finis ? Expliquez. 10

4 Expliquez la hiérarchie de Chomsky de la grammaire avec leurs modèles mathématiques respectifs. Pouvez-vous ? 10
Reliez les expressions régulières et les CFG ? Si oui, expliquez avec un exemple.

5 Comment pouvez-vous simplifier une CFG ? Trouvez une grammaire réduite équivalente à la grammaire G 10
dont les productions sont-

S AB | CA|A| , B BC | |AB, A un, C aB | b

6 Que voulez-vous dire par forme normale ? Réduisez la grammaire suivante en CNF. 10
S 1A | 0B, A 1AA | 0S | 0, B 0BB | 1S |1

7 Discutez de l'application du lemme de pompage pour un langage contextuel libre avec un exemple. 10
Construisez un PDA qui acceptera toutes les chaînes sur {a, b} consistant en un nombre égal de a et
b's.

8 Différenciez entre FA, PDA et TM sur la base de l'acceptation de chaînes. Expliquez également pourquoi. 10
est-ce que le TM est considéré comme fonctionnellement plus fort parmi tous ceux-ci ?

9 Différencier entre un langage récursif et un langage récursivement énumérable. Est-ce que ces langages 10
provide the notion of decidable and un-decidable problems? Explain.

10 Discutez brièvement de la théorie des fonctions récursives. 10