1250463759

3.2. Hierarchia języków wg N. Chomsky'ego:

- klasy języków uporządkowane relacją zawierania się zbiorów;

-języki klasy "0" nazywamy obliczalnymi, są klasą najszerszą, matematycznie są przykładem zbiorów rekurencyjnie przeliczalnych (częściowo rozstrzygalnych);

-języki klasy "1" nazywamy monofonicznymi, matematycznie są przykładem zbiorów rekurencyjnych (rozstrzygalnych);

-języki klasy "2" nazywamy bezkontekstowymi\ wyróżnia się istotne z praktycznego punktu widzenia podklasy LL i LR (generator YACC);

-języki klasy "3" nazywamy regularnymi; biorą swą nazwę od jednego z formalizmów ich definiowania zwanego wyrażeniami regularnymi;