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)$

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:

GNC en FNC si sous la forme:
$A \rightarrow BC$ ou $A \rightarrow a$

Automate Ă  pile

La flemme aussi