Йерархия на Чомски: Разлика между версии

→‎Типове в йерархията: ===Йерархия на формалните езици===
(Граматиките от тип 1 са монотонни спрямо дължината на думата)
(→‎Типове в йерархията: ===Йерархия на формалните езици===)
 
==Типове в йерархията==
 
Всеки последователен тип граматика се съдържа от предшественика си. Граматиките на Чомски и езиците, дефинирани от тях, се класифицират по следния начин. (Дефинициите се ограничават до редуктивния случай, тъй като генеративният е напълно аналогичен.)
===Тип 0===
 
Граматиките от тип 1 са [[монотония (математика)|монотонни]] спрямо дължината на думата. В тях се допуска и правилото
: <math>\varepsilon \rightarrow \langle S\rangle</math>,
ако аксиомата ''S'' не се среща от лявата страна на нито едно от правилата.
 
Езиците на тези граматики могат да се опишат и чрез [[регулярен израз|регулярни изрази]].
 
===Йерархия на формалните езици===
Йерархията на граматиките определя и съответни типове формални езици. Ако за един език ''L'' съществува граматика ''G'' от тип ''i'' с ''L=L(G)'', то за този език се казва че е от тип ''i'' и се записва:
 
:<math>L \in \mathcal{L}_i</math>.
 
Освен това важи:
 
:<math>\mathcal{L}_3 \subset \mathcal{L}_2 \subset \mathcal{L}_1 \subset \mathcal{L}_0</math>.
 
Т.е. всички регулярни езици са безконтекстни, всички безконтекстни езици са контекстни и всички контекстни езици са рекурсивно изброими.
 
==Абстрактни машини==
3280

редакции