Детерминистички контекстно слободан језик

Из Википедије, слободне енциклопедије

Детерминистички контекстно слободан језик је формални језик који је дефинисан детерминистичким контекстно слободним граматикама. Скуп свих детерминистичких контекстно слободних језика је идентичан скупу језика које прихватају детерминистички потисни аутомати. Скуп детерминистичких контекстно слободних језика је прави подскуп контекстно слободних језика који користе одређене контекстно слободне граматике. На пример, језик палиндрома у азбуци која се састоји од симбола 0 и 1, има једноставну, одређену граматику 1S1 | ε , али не може бити анализиран детерминистичким потисним аутоматом. Језици из ове класе су од великог значаја у пракси рачунарства. Сложеност програма и извршавања детерминистичког потисног аутомата је знатно мања од недетерминистичког који мора правити копије стека за сваки недетерминистички корак.


Теорија аутомата: формални језици и формалне граматике
Хијерархија
Чомског
Граматике Језици Минимални
аутомат
Тип-0 Без ограничења Рекурзивно пребројиви Тјурингова машина
 % (без уобичајеног имена) Рекурзивни Одлучивач
Тип-1 Контекст сензитивна Контекст сензитивни Линеарно-ограничени
 % Индексирана Индексиран Угњеждени стек
Тип-2 Контекст-слободна Контекст-слободни Недетерминистички потисни
 % Детерминистичка контекст-слободна Детерминистички контекст-слободни Детерминистички потисни
Тип-3 Регуларна Регуларан Коначни
Свака категорија језика или граматика је прави подскуп категорије директно изнад ње.