Серия «Что такое язык программирования?»

Здесь нужно остановится на понятии «магазинная память», которое использовано крайне не удачно. По идее у вас должна быть выстроена ассоциация с магазином АК-47 (или другого оружия), где пуля заряженная последней, выстреливается первой. Но дело в том, что само слово магазин обозначает просто склад и он не обязательно должен выстроен по вышеуказанному принципу, лично я вовсе подумал о продуктовом. Поэтому используем термин стог-память или просто стог, так как если из стога вытащить что-то не сверху он превратится в кучу.

Перед тем как дать формальное описание, мы сперва построим простой стог-автомат. Отобразим общее представление об автомате:

Мы видим, что автомат обращается за чтением цепочки и за чтением из стог-памяти, в стог вложен отдельный символом п обозначающий под или дно. Внутреннее устройство автомата можно представить в виде направленного графа как и конечный автомат (далее КА), только для перехода из состояния в новое состояние направленное ребро помечается по мимо принимающего символа, верхней цепочкой символов стога, которая будет заменена на новую цепочку символов в обратном порядке по очереди («первым вошёл, первым ушёл»), также входит в метку:

Выше приведены примеры переходов с отображением операций над стогом. Первых три примера прозрачны, считали символ и поменяли цепочки. В 4 и 5 используется пустая цепочка ε и здесь нужно пояснение. Между любыми двумя символами всегда лежит пустая цепочка , что является причинной почему КА с ε-переходами недетерминирован. Проверьте, зайдите https://regex101.com/, введите любой текст и регуляр (), вы получите кучу совпадений. В стог-автомате ε используется в целях внутренней работы без считывания символа принимаемой цепочки, выталкивания и помещения символов из/в стог(-а), ведь пустота означает, что нечего брать или класть.

Изобразим граф стог-автомата принимающего язык:
Я = {аⁿбⁿ | n >= 0}, где в цепочках символы а и б повторяются в равном количестве, примеры { аб, аабб, аааббб, …}.

Так же как в КА конечное состояние автомата обозначаем узлом с двойным кружком, а начальное просто стрелкой. Для того, чтобы не изображать лишних рёбер правила переходов записывают друг над другом. Формально данный стог-автомат записывается так:
М = ({С0, С1, С2},{а,б}, {А. п}, δ, С0, п, {C2})

Теперь мы готовы к общему формальному описанию, приступим:
M = {Q, Σ, Γ, δ, q0, Ζ, F}
F - множество конечных (принимающих) состояний автомата, наше {C2}.
Ζ - символ конца стога, наш п - символ под.
q0 - начальное состояние автомата, наше С0.
δ - функция переходов автомата δ: ( Q × (Σ ∪ {ε}) × Γ) → (Q × Γ*).
Γ - алфавит стога, наше {А, п}.
Σ - входной алфавит, наше {а,б}.
Q - множество состояний автомата, наше {С0, С1, С2}.

Остановимся на функции переходов δ: ( Q × (Σ ∪ {ε}) × Γ) → (Q × Γ*), она нам говорит о том, что переход зависит от текущего состояния Q, от принимаемого символа Σ с возможностью его оставить в покое ε и от верха стога Γ, в замен мы получаем новое состояние Q и новое содержимое стога Γ*. Γ* - звездочка обозначает, что наше множество разрастаемое, то есть стог заполняется символами.

Для дальнейшего объяснения предоставляю работу автомата того же языка, но построенный по его грамматике:
G: S → aSб | ε

На рисунке отображено, ещё не рассмотренное нами понятие конфигурации. Конфигурация представляет из себя набор (q, ω, γ), где q - текущее состояние, ω - цепочка ещё не рассмотренных символов, γ - содержимое стога. Символом ⊢ обозначают такт автомата, то есть переход из одной конфигурации в другую. Обозначим символом ⊢* последовательность ноль и более тактов, теперь мы можем описать условие принятия цепочки или допускаемый язык автомата:
L(M) = {ω ∈ Σ* и (q0, ω, Z) ⊢* (q, ε, Z), где q ∈ F} - то, есть когда наш стог опустошился до пода, завершился в конечном состоянии, а так же вся входная цепочка прочитана полностью. Лично у меня остался вопрос, почему везде записывают принятие по пустому стогу так:
L(M) = {ω ∈ Σ* и (q0, ω, Z) ⊢* (q, ε, ε,) где q ∈ F} - ведь никто не извлекает Z?

Так же существует соглашение условия принятия:
L(M) = {ω ∈ Σ* и (q0, ω, Z) ⊢* (q, ε, γ), где q ∈ F, γ ∈ Γ*} - то, есть когда наша цепочка полностью прочитана и мы достигли конечного состояния, а в стоге остались символы. Если мы уберём состояние С3, а С2 сделаем конечным, то становится понятно почему, такое соглашение есть.

Так же автомат можно описать таблицей, вот наш случай:

В заключении следует сказать:
Для произвольной КС-грамматики можно построить недетерминированный автомат с магазинной памятью (стог-памятью), принимающий язык, порождаемый этой грамматикой.

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

Постскриптум: Очень сильно надеюсь, что изложил тему доступным языком. Будьте мне здоровы, подписывайтесь.

Предполагаем приоритет операции, высший имеет «*» - повторение, затем сцепление и низший «|» («или»). Скобки используются для изменения порядка операций.

Зачастую при записи регулярного выражения запись ε опускают и вводится дополнительный оператор «один раз и более» обозначенный символом «⁺», что значит R⁺=RR*. Вот так это выглядит на примере языка целых чисел со знаком:

(+ | – | ) (0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 )⁺

Теорема Клини гласит: Автоматные языки являются регулярными множествами. Регулярные множества являются автоматными языками.

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

И чтобы вам было проще понять правила сделаем таблицу соответствия правил с участками рисунка порядка (синтаксической диаграммы) языка.

На этом урок окончен. В следующем мы обсудим регулярные выражения на практике и подытожим тему автоматных языков. Новоиспечённые подписываемся, с нами интересно. Дайте пятюню.

Условимся что, автомат принимает вместо пустой цепочки ε, конечный символ ⊥, который будет означать конец принимаемой цепочки. Подобным образом обрабатываются строки в языке C, в нём используется так называемый нуль-терминал или по-русски нуль-концевик.

Теперь возьмём и заменим вспомогательные символы в графе на точки, а символы основного алфавита наоборот выделим в круги.

Теперь мы можем наблюдать два столпа программирования ветвление и цикл, а так же последовательность их выполнения. На рисунке порядка они отчётливо отображены, что позволяет легко описать в коде алгоритм:

Определённо вы заметили, что этот код можно упростить, а это намекает нам и на то, что можно упростить и рисунок порядка. Что же займёмся этим:

В рисунке порядка, у нас есть центральная линия последовательности и конечные символы + и - отходят от неё и заново возвращаются, что следует расценивать как не обязательные части порождаемой (принимаемой) цепочки. Такая же ситуация и с циклом, мы не всегда в него попадаем.

На этом тема закрыта, но! Должен отметить тема синтаксических диаграмм, пока-что до конца не описана, мы её коснёмся ещё раз, но уже при рассмотрении КС-грамматик.

З.Ы, Подписывайтесь рофлов ради, али кринжов. Ну или из любопытства. Хорошего настроения.

Символ Ø обозначает, что наш автомат завершил работу и более не принимает символов. Если мы продолжаем читать из потока, тогда нам следует перезапустить автомат для обработки уже следующей цепочки.

Приступим к алгоритму. Построим новый автомат на базе состояний нашего НКА. Состояния нового автомата будут иметь названия составляющие все возможные сочетания из множества состояний НКА по k, где k у нас будет меняться от 1 до максимального кол-ва. То есть в нашем случае до 3 из множество {S, B, K } это S, B, K, SB, SK, BK, SBK.

Состояния нового автомата в чьи имена попали, обозначения конечного состояния НКА, тоже становятся конечными: K, SK, BK, SBK. А начальное состояние не меняется S.

Теперь нам остаётся задать переходы по каждому символу, соблюдая следующее: Из каждого состояния N нового автомата направим не более чем один переход, помеченный данным символом, в такое состояние, которое соответствует множеству состояний НКА, в которые есть переходы по этому символу хотя бы из одного состояния НКА, образующего N.

Вот так:

Давайте построим для него граф:

У нас получился ДКА, только в нём есть состояния в которые мы никогда не попадём. Поэтому данный ДКА следует минимизировать, алгоритма минимизации возможно коснусь в последующих статьях. Но можно выделить две вещи, когда следует минимизировать ДКА, когда у нас «мертвые» состояния и когда состояния повторяют одно и то же действие. Вот так будет выглядеть результат минимизация получившегося ДКА:

Переименуйте BK в B и узнаете уже рассмотренный нами ДКА.
З. Ы. Для построения графов в этот раз использовал эти инструменты https://www.graphviz.org/download/ и можно web-версию использовать http://www.webgraphviz.com/. Следующая статья будет посвящена синтаксическим диаграммам автоматного языка. Не забывайте подписываться, если вам это интересно.=)

Как-то не особо получается верно? Нам не совсем-то понятно когда переходить в состояние K, мы как-будто застряли в неопределенности. Когда приняли символ a оставаться в состоянии B или переходить уже к другому? Данные типы автоматов называются не детерминированные конечные автоматы или просто НКА, они обладают особой приметой, то что на один и тот же принятый символ в одном состоянии есть более одного варианта перехода. И всё таки мы можем написать для него функцию перехода, добавив какие нибудь условия, например проверять не последний ли это символ. Что же получается я слукавил в прошлый раз? И да и нет, жертва для более наглядного, постепенного объяснения. Да - потому-что функцию перехода можно реализовать разными способами. Нет - потому-что это частный случай реализации детерминированных конечных автоматов или просто ДКА, когда каждый его переход однозначен. ДКА - гораздо эффективнее НКА и у меня хорошие новости:
Теорема Клини. Для каждого НКА можно построить ДКА, допускающий тот же язык.

В следующей статье мы рассмотрим алгоритм преобразования НКА в ДКА, не забывайте подписываться. Все здоровья и удачи.