Scribd
Importer
7 vues2 pages

Examen sur les Langages Formels et Automates

Ce document contient des instructions pour un examen d'informatique sur les langages formels et la théorie des automates. Il énumère 6 questions avec plusieurs parties pour chaque question. Les questions couvrent des sujets tels que les formes de phrases, les dérivations, les grammaires, les automates, les automates à pile, la forme normale de Greibach, les types de grammaires et les systèmes formels. Les étudiants sont invités à répondre à la question 1 et à 3 autres questions.

Traduit par

ScribdTranslations
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
7 vues2 pages

Examen sur les Langages Formels et Automates

Ce document contient des instructions pour un examen d'informatique sur les langages formels et la théorie des automates. Il énumère 6 questions avec plusieurs parties pour chaque question. Les questions couvrent des sujets tels que les formes de phrases, les dérivations, les grammaires, les automates, les automates à pile, la forme normale de Greibach, les types de grammaires et les systèmes formels. Les étudiants sont invités à répondre à la question 1 et à 3 autres questions.

Traduit par

ScribdTranslations
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

UNIVERSITÉ NATIONALE OUVERTE DU NIGÉRIA

Village Universitaire, Zone Cadastrale 91, Autoroute NnamdiAzikwe, Jabi, Abuja


FACULTÉ DES SCIENCES
DÉPARTEMENT DE SCIENCES INFORMATIQUES
EXAMEN POP 2023_1 231

CODE DU COURS CIT 342


TITRE DU COURS : Langages Formels et Théorie des Automates
3 unités
TEMPS PERMIS : 3 heures
INSTRUCTION : Répondez à la question un (1) et à trois (3) autres questio

1a) Qu'est-ce qu'une forme propositionnelle ? (2 points)


b) Considérez la grammaire linéaire : ({S, B}, {a, b}, S, {S → aS, S → B, B → bB, B → }). Donnez
n'importe quelle quatre forme de phrase de cette grammaire(4 points)
c) Décrivez les différents composants d'une grammaire formelle. (6 points)
d) Dans le contexte deinformatique théorique, Qu'est-ce que la théorie des automates ? (3 points)
e) Que comprenez-vous par dérivation la plus à gauche et dérivation la plus à droite d'une grammaire ? Sont-elles les
pareil?(6 points)
f) Quand est une grammairedit être en forme normale de Chomsky? (4 points)

2a) Considérez la grammaire : G = ({S, A, B, C}, {a, b, c}, S, P) où


P = {S→ABC, A→aA, A→ , B→bB, B→ , C→cC, C→ }, dériver la chaîne abbcin a
i) dérivation la plus à gauche(4 points)
ii) dérivation la plus à droite (4 points)
b) Dessinez l'arbre de dérivation pour la dérivation la plus à gauche dans la question (2a) ci-dessus. (2 points)
c) Prouvez queles langages sans contexte sont fermés sous la formation d'union.
notes)

3a)In the context of automata theory, explain the following terms:


i. Langue reconnue )
ii. Courir )2 points chacun
iii. Transducteur )

b) Énumérez les différentes manières d'utiliser une grammaire. ) 5 points


c) Écrivez de courtes notes sur le concept d'ambiguïté dans les grammaires..) 4 points

4a) Que signifielangage intrinsèquement ambigu ?(2 points)


b) Faites la distinction entre un mot et un vocabulaire dans un langage formel. Illustrez votre réponse.
avec des exemples) 5 points
c) Qu'est-ce qu'un Automate à Pile (PDA) ) 4 marques
d) Prouvez que pourpour tout langage régulier, il existe un DPDA qui l'accepte (4 points)
5a) Quand dit-on qu'une grammaire est enForme normale de Greibach ?(3 points)
b) Quelles sont les caractéristiques des grammaires qui sont dansForme normale de Greibach)2 points
c) Indiquez l'utilisation (les utilisations) de la forme normale de Greibach(2 points)
d) ) 3 marques
Définir formellement la grammaire de Type 1
e) Décrivez brièvement les différents types de PDA.) 5 points

6a) Liste les trois manières différentes de définir une langue ) 3 marques
b) Un NFA est-il plus puissant qu'un DFA ? Expliquez. (4 points)
c) Énonce du théorème d'incomplétude de Gödel ) 2 points
d) Que comprenez-vous par les grammaires sensibles au contexte ?) 2 points
e) Quand dit-on qu'un système formel est :
i) Complet? )
ii) Incohérent? )2 points chacun

Vous aimerez peut-être aussi