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 ^{★}=\{ϵ,a,b,aa,ab,ba,bb,aaa,...\}$

$L^{+}=L.L^{★}$ : Ici

$L^{+}$ ne contient

$ϵ$ si

$L$ le contient quand

$L^{★}$ le contient tout le temps

$\mathrm{\forall }u\in \sum ^{★}$, u est un mot

$\mathrm{\forall }L\subset \sum ^{★}$, L est un langage

Langage vide : Element absorbant
Langage

$\{ϵ\}$ : 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(nfois)$ et
    $L^0=\{ϵ\}$
• Fermeture de Kleene :
  $L^{★}$ : Tous les mots que on peut former avec le langage L
  • ${\varnothing }^{★}=\{ϵ\}$
• Complémentation :
  $\bar{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

• $\{ϵ\}$ et
  $\varnothing$ sont des langages rationnels
• $\mathrm{\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 (

$\bar{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
  $ϵ$)
  • Compléxité : exponentielle
    
• DFA : Automate fini déterministe (pas de liaisons spontanées
  $ϵ$)
  • 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$ ∅
$\{ϵ\}\to ϵ$
$\mathrm{\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 ϵ$

Hiérarchie de Chomsky

• Grammaire monotone :
  $\alpha \to \beta \Rightarrow |\alpha |\le |\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 ϵ$
• 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