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