Examen informatique theorie des langages Théorie des la...

Théorie des langages : Examen informatique theorie des langages

Télécharger PDF

Université Mouloud MAMMERI de Tizi-Ouzou

Année universitaire : 2014/2015

Faculté de génie électrique et informatique

2ème année licence – Informatique

Département d’informatique

Module : Théorie des langages

Examen de rattrapage le 08/04/2015 – Durée 1h30 – Documents non autorisés

Exercice 1

(5 points)

1) Définition du mot x

Soit le mot x = ((acb)_R .cbaa)_R (α, où R désigne le reflet miroir de α).

1-1) Chaîne de caractères correspondant à x

Le mot x est égal à la chaîne : bbcacbaa.

1-2) Valeur de |x|

La longueur de x, notée |x|, est 8.

1-3) Préfixe propre de x contenant au moins deux lettres 'a'

Un préfixe propre de x contenant au moins deux lettres 'a' est : cbaa.

1-4) Sous-chaîne de x commençant par 'b' et se terminant par 'a'

La sous-chaîne de x qui commence par 'b' et se termine par 'a' est : bbca.

2) Propriétés des préfixes et sous-chaînes

Soit V un alphabet et w un mot de V^* de longueur n.

2-1) Nombre de préfixes de w

Le nombre de préfixes de w est n + 1 (incluant la chaîne vide).

2-2) Nombre de sous-chaînes de w (toutes lettres différentes)

Si toutes les lettres de w sont différentes, le nombre de sous-chaînes distinctes est : n(n + 1)/2.

2-3) Condition nécessaire sur n pour que toutes les lettres de w soient différentes

Pour que toutes les lettres de w soient différentes, il faut que n soit inférieur ou égal à la taille de l’alphabet V, c’est-à-dire : n ≤ |V|.

Exercice 2

(8 points)

1) Langage L₁ = { a.b²ⁿ.a / n ≥ 0 }

Grammaire pour L₁ :

S → aSb
S → aA
A → bB
B → bB
B → ε

2) Langage L₂ = { a²ⁿb^3m / n ≥ 1, m ≥ 0 }

Grammaire pour L₂ :

S → aAb
A → aa
A → aAS
B → ε
B → bB
B → b₃B

3) Langage L₃ = { aⁿb^mc^k / 0 ≤ n ≤ m ≤ k }

Grammaire pour L₃ :

S → aS | bC | cD
C → bC | cD
D → cD | ε

4) Langage L₄ = { aⁱb^jc^k / k = max(i, j) }

Grammaire pour L₄ :

S → aS | bS | c^kS₁
S₁ → aS₁ | bS₁ | ε
S₂ → aS₂ | ε
S₃ → bS₃ | ε
S → S₂S₃S₁

Exercice 3

(7 points)

1) Automate pour le langage L₁ = {a, b}^* où au moins une des deux premières lettres est 'b'

L’automate doit accepter les mots dont la première ou la deuxième lettre est 'b'.

2) Automate pour le langage L₂ = {aab, aba}

L’automate doit reconnaître exactement les chaînes aab et aba.

3) Automate pour L₁ ∪ L₂

L’automate doit accepter tous les mots de L₁ ainsi que les chaînes aab et aba.

4) Rendre l’automate de 3) déterministe

Si l’automate construit en 3) n’est pas déterministe, il faut le transformer en un automate déterministe équivalent en utilisant la méthode de la fermeture transitive.

5) Automate pour le complémentaire de L₁ ∪ L₂

L’automate doit accepter toutes les chaînes de {a, b}^* qui ne sont pas dans L₁ et qui ne sont ni aab ni aba.

FAQ

1. Qu’est-ce qu’un préfixe propre ?

Un préfixe propre d’une chaîne est une sous-chaîne qui commence par la première lettre et ne comprend pas toute la chaîne (excluant la chaîne elle-même).

2. Comment déterminer un automate déterministe à partir d’un non-déterministe ?

On utilise la méthode de la fermeture transitive pour fusionner les états non-déterministes en un seul état déterministe.

3. Que signifie "reflet miroir" dans le contexte des chaînes ?

Le reflet miroir d’une chaîne α est la chaîne obtenue en inversant l’ordre des lettres de α (ex. : miroir de abc est cba).