Langages
En informatique on manipule souvent des langages. On défini même la calculabilité avec les langages. Quelle est la théorie derrière?
Langages Rationnels
ReGeX l'idée est cool mais la flemme de te l'expliquer
Grammaires non-contextuelles
Merci Ă Noah Chomsky
$G = (N, T, S, P)$
- $N$ ensemble fini de symboles finis non terminaux
- $T$ ensemble fini de symboles terminaux
- $S$ éléments de N, symbole de départ
- $P$ ensemble fini des règles de ré-écriture
mais complexe du coup on simplifie en Forme Normale de Chomsky. Elle existe pour toute GNC. Permet aussi de résoudre le problème de décision. On dit deux grammaires équivalentes si leurs langages sont équivalents: $L(G) = L(G')$
Pour réduire une GNC:
- On recherche l'ensemble des var annulable
- On construit une GNC sans $\epsilon$-production
- On recherche l'ensemble des var actives et on supprime les productions qui contiennent des var inactives
- On cherche l'ensemble des var accessible et on supprimes les var inacessibles
GNC en FNC si sous la forme:
$A \rightarrow BC$ ou $A \rightarrow a$
Automate Ă pile
La flemme aussi