---
title: ING1 - THL
tags: EPITA
---

# Théorie des Langages - S5

## Alphabets

Langage : Ensemble de mot (infini ou pas, peut être vide)
Mot : Suite (=> Ordre important != Ensemble) finie de symbole, peut être vide
Alphabet : Ensemble de symbole fini et non vide

$\sum = \{a, b\}$ (alphabet)
$\sum^{★} = \{\epsilon, a, b, aa, ab, ba, bb, aaa,...\}$
$L^{+} = L.L^{★}$ : Ici $L^{+}$ ne contient $\epsilon$ si $L$ le contient quand $L^{★}$ le contient tout le temps

$\forall u \in \sum^{★}$, u est un mot
$\forall L \subset \sum^{★}$, L est un langage

Langage vide : Element absorbant
Langage $\{\epsilon\}$ : Element neutre

### Opérations sur les langages

- Union : $L_{1} \cup L_{2}$ ou $L_{1} + L_{2}$ : Opération associative et commutative
- Intersection : $L_{1} \cap L_{2}$ : Opération associative et commutative
- Concaténation : $L_{1}.L_{2}$ : Opération associative et non-commutative
- Auto-concaténation : $L^{n} = L.L.L.L~(n~fois)$ et $L^{0} = \{\epsilon\}$
- Fermeture de Kleene : $L^{★}$ : Tous les mots que on peut former avec le langage L
- $∅^{★} = \{\epsilon\}$
- Complémentation : $\overline{L}$
- Préfixe : $Pref(L)$ : Préfixe d'un mot (le préfixe peut être le mot en entier)
- Ajouter des entrées sur les états co-accessible
- Préserve la rationnalité
- Suffixe : $Suff(L)$ : Suffixe d'un mot (le suffixe peut être le mot en entier)
- Ajouter des entrées sur les états accessible
- Ne préserve pas forcément la rationnalité
- Sous-mot : $Sous-mot(L)$ :
- Ajout d'entrées et de sorties sur les états utiles

### Rationnalité

Soit $\sum$ un alphabet

- $\{\epsilon\}$ et $∅$ sont des langages rationnels
- $\forall a \in \sum, \{a\}$ est un langage rationnel
- Si $L_{1}$ et $L_{2}$ sont des langages rationnels, alors sont rationnels:
- $L_{1} \cup L_{2}$ ou $L_{1} + L_{2}$
- $L_{1}.L_{2}$
- $L_{1}^{★}$

Les opérations d'union ($\cup$ | $+$), de concaténation ($.$) et de l'étoile ($★$) sont rationnelles.
Les opérations la complémentation ($\overline{L}$) et l'intersection ($\cap$) ne sont pas rationnelles.
Une partie d'un langage rationnel n'est pas forcément rationnelle ($a^{n}b^{n}$ n'est pas rationnel)

### Expressions rationnelles


## Automates finis

- NFA : Automate fini non-déterministe (possibilité présence de liaison spontanées $\epsilon$)
- Compléxité : exponentielle
- DFA : Automate fini déterministe (pas de liaisons spontanées $\epsilon$)
- Complexité : linéaire
Si un mot ne se finit pas par un état possédant une sortie, alors il ne respecte pas la regex détectée par l'automate
- $(\sum, Q, I, F, \delta)$ où :
- $\sum$ : Alphabet de travail
- $Q$ : Ensemble d'états
- $I \subset Q$ : Ensemble d'états initiaux
- $F \subset Q$ : Ensemble d'états finaux
- $\delta$ : Ensemble de transition
- Un état **utile** : accessible ET co-accessible
- Transition
- Langage supportes
- Problèmes et limitations
- Thompson

### Automate de Thomson (NFA)

| Opération / Ensemble | Représentation |
| ------------------------------- | ------------------------------------ |
| ∅ $\to$ ∅ |  |
| $\{\epsilon\} \to \epsilon$ |  |
| $\forall a \in \{a\} \to a$ |  |
| Concaténation $L_{1}.L_{2}$ |  |
| Union $L_{1} \cup L_{2}$ |  |
| Etoile $L_{1}^{★}$ |  |

### Déterminisation

Pour tout les automates NFA ont peut construire un équivalent DFA.
Si l'automate NFA possède $N$ états, alors l'automate DFA résultat à au plus $2^{N}$ états
Exemple :

## Grammaire et contexte

Grammaire : Soit $\{a, b\}$ deux terminaux et $S$ un non-terminal.
$S \to aSb$
$S \to \epsilon$

### Hiérarchie de Chomsky


- Grammaire monotone : $\alpha \to \beta \Rightarrow |\alpha| \leq |\beta|$
Pour éviter que la règle ne consomme des caractères.
- Contexte-Sensitive : 
Réécrire que la partie non-terminale
- Contexte free : $X \to \alpha$
Ici $X$ (symbole non-terminal) est remplacé par $\alpha$ (symbole terminal ou non-terminal). On ne regarde pas le contexte avant de le remplacer.
- Grammaire régulière :
- Linéaire à droite : $A \to u \overrightarrow{B}$
L'élement non-terminal est situé à la fin du mot.
- Linéaire à gauche : $A \to \overrightarrow{B}u$
L'élement non-terminal est situé au début du mot.
Il existe un automate déterministe qui reconnaisse son langage
- Linéaire à droite et à gauche :
Peuvent engendrer des langages rationnels si on accepte la production $A \to \epsilon$
- Grammaire à choix finis : $A \to u$ où $A \subset N$ et $u \in \sum^{+}$
Engendre uniquement des langages finis qui ne contiennent pas le mot vide.

### Parseurs LL et LR


Parser LL : Manque d'expressivité
Parser LR : Plus compliqué à écrire à la main
Lex/Flex : Analyseur lexical
Yacc : Analyseur syntaxique LALR(1)

Précision et complexité
LR(0) < LALR(1) < SLR(1) < LR(1)

(tableau)
- LL(k)
- LR(k)
- CLR(k) : Complex LR(k)
- SLR(k) : Simple LR(k)
- LALR(k) : LookAhead LR(k) (Parser Yacc) : Langage Type <= 2
- Fusionne les états au LookAhead près par rapport à un LR(k)
- Follow
- Lookhead