Снова здравствуйте, читатель, для нашего третьего эпизода в этой серии теории вычислений, и вау, это было долгое, но приятное (я имею в виду, я думаю, вам понравилось, верно?) путешествие, и еще раз большое всем спасибо за отзывы и за резервирование ваше время, чтобы прочитать, прокомментировать и оставить свой отзыв об этой серии, я очень рад и заставляет меня хотеть приносить сюда все больше и больше качественного контента, кстати, если вы все еще не читали предыдущую главу нажмите здесь , и прямо в точку, сегодня настал день поговорить о языках со свободным контекстом, в отличие от обычных языков, языки со свободным контекстом находятся в другой категории порядка языков Ноама Хомского.

Примером нерегулярного языка является a**nb**n, где n ≥ 1 с использованием автоматов или регулярных выражений. прочитайте и посмотрите, являются ли они одинаковыми, потому что как в NFA, так и в DFA у меня есть конечное количество состояний, а с помощью регулярных выражений я не могу гарантировать, что мои выражения, возведенные в оператор звезды, будут генерировать одинаковое количество b и a .

Итак, для решения этой проблемы требуются новые типы решений, а именно:

— Автомат выталкивания

Название звучит как что-то очень причудливое и сложное, но если вы знаете структуру данных стека, вы почти разобрались с автоматом выталкивания вниз.

Подобно DFA или NFA, у нас есть свои состояния и добавление структуры стека, в начальном состоянии мы добавляем конечный символ, такой как "$", и когда мы читаем "a ” мы добавляем символ "a" на вершину стека (push), и после того, как все "a" прочитаны, мы начинаем читать "b" и после чтения символа ab мы удаляем голову стека (pop), если были прочитаны все b и голова стека - это символ $ языка a**nb**n, где n ≥ 1, был успешно распознан

— Бесплатные контекстные грамматики

Подобно рекурсивному вызову функции, грамматики свободного контекста генерируют языки свободного контекста, и их операции довольно просты.

Чтобы сгенерировать этот язык a**n.b**n, где n ≥ 1, нам понадобятся только наши переменные и терминальные символы.

-Переменные

Вызов с использованием рекурсии, которая в конечном итоге генерирует один терминал

-Терминалы

Символы, которые не могут генерировать другие символы

S -> AB
A -> aA | a&
B -> bB | б&

Вот грамматика свободного контекста, которая генерирует язык a**nb**n, где n ≥ 1, и, как мы можем заметить, {S, A, B} являются нашими переменными, поскольку они генерируют терминалы { a, b и &(символ эпсилон или пустой строки)}

S производит (-›) A(вызывает A)B(вызывает B)
A производит (-›) либо a( терминал)A(вызывает A) или a(терминал)&(“” терминал)
B производит (-›) либо b(терминал)B(вызов B) или b(терминал)&("" терминал)

И все сгенерированные последовательности со стопроцентной уверенностью будут генерировать последовательности, содержащие одинаковое количество букв a и b, соответствующих определению языка a**nb**n, где n ≥ 1, с использованием рекурсивного метода обращения к переменным генератора.

И вот мы подошли к концу третьего эпизода этого высокоуровневого подхода к теории вычислений. Было очень весело писать об этой удивительной теме компьютерных наук, которая имеет огромное значение для того, как мы разрабатывали вычисления и современное программное обеспечение, а также современные технологии. технологии.

Еще раз большое спасибо за то, что дочитали до этого места, и еще есть много вещей, которые можно написать о теории вычислений, таких как лямбда-исчисление церквей, превращение распознаваемых и разрешимых языков, контекстно-зависимые языки, неоднозначные грамматики, токарные машины и многое другое, поэтому я очень призываю вас глубже погрузиться в теорию вычислений и увидимся :)