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

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

Приступим к алгоритму. Построим новый автомат на базе состояний нашего НКА. Состояния нового автомата будут иметь названия составляющие все возможные сочетания из множества состояний НКА по 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 или переходить уже к другому? Данные типы автоматов называются не детерминированные конечные автоматы или просто НКА, они обладают особой приметой, то что на один и тот же принятый символ в одном состоянии есть более одного варианта перехода. И всё таки мы можем написать для него функцию перехода, добавив какие нибудь условия, например проверять не последний ли это символ. Что же получается я слукавил в прошлый раз? И да и нет, жертва для более наглядного, постепенного объяснения. Да - потому-что функцию перехода можно реализовать разными способами. Нет - потому-что это частный случай реализации детерминированных конечных автоматов или просто ДКА, когда каждый его переход однозначен. ДКА - гораздо эффективнее НКА и у меня хорошие новости:
Теорема Клини. Для каждого НКА можно построить ДКА, допускающий тот же язык.

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

Ещё вы можете найти следующую формулу:
A = (N, T, O, δ, λ, F)
Где δ - функция переходов состояния автомата и записывают её так
δ : N × T → N означает что берется пара значений, одно из множества N, а другое из множества T и возвращает значение из множества N.
И λ - функция выходов, записывается λ : N × T → O , собственно O - означает выходной алфавит, или грубо говоря переводной. Например, сочтём за символы два слова, английское Hello из принимаемого алфавита и русское Привет из выходного алфавита, и во время работы автомата при некотором состоянии («контексте предложения»), принимает Hello и переводит его в Привет, ведь вполне может что в другом состоянии («контексте предложения») он может перевести его в Здравствуйте! =) Дальше повествование будет, только о автомате распознавателе, то есть без функции выходов, который описан выше, просто общий принцип функции переходов и выходов сильно не отличается.

Возьмем грамматику, я надеюсь уже любимого, языка идентификаторов:
G: S → aB
B → aB | bB | ε
И построим её граф.

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

В таблице, жирным курсивом, отмечено состояние B, так как оно входит во множество конечных состояний и если автомат закончил принимать символы в одном из таких состояний, говорят что он принял данную цепочку. Так же вы видите состояние E, обычно его не отображают на графе, по одной просто причине, все пути веду в Рим к ошибке, когда подается символ не подходящий к состоянию или не входящий в алфавит который принимает автомат. Собственно наша функция обращается к этой таблице и переводит автомат, в то состояние которое получила из таблицы. Как-будто играет в морской бой, только с ответами ошибка, не ошибка.

Наверное вы заметили, что граф конечного автомата в прошлой статье и описанный в этой отличаются, хотя они принимают один и тот же язык? Об этом я расскажу в следующий раз, но перед этим я бы хотел показать вам программную реализацию КА на одном из языке программирования, на каком бы вы предпочли? Решение будет по результатам 3-его дня, после публикации статьи.

Опрос в vk.com у пикабушки нету =(
З. Ы. Подписывайтесь! =)

Давайте построим граф уже известного нам языка идентификаторов, только воспользуемся его эквивалентной автоматной грамматикой, так как прошлый раз мы использовали КС-грамматику. Вот смотрите:
G: S→ a
S → aB
B → a
B → b
B → aB
B → bB

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

А как же КА, спросите? Про это мы поговорим в следующий раз, но уже это должно натолкнуть вас, как он работает. Подписывайтесь, чтобы не пропустить продолжение.

Что мы наблюдаем? Первое то, что грамматика выдает для выражения x + x * x два разных дерева вывода. На изображении, ниже уже привычного нам дерева, выведены редуцированные (упрощенные) деревья, такие деревья называют семантическими деревьями. Так если мы обойдем каждый узел рекурсивно и выполним действие предписывающее нашему знаку, мы получим разные результаты. То есть будем вычислять от листьев к корню, узел x будет означать просто вернуть число, если x = 2, то первое вариант выдаст нам 8, а второй 6. Такие типы грамматик являются неоднозначными.

Грамматика называется однозначной, если любой её сентенции (предложению) соответствует единственное дерево вывода, при правостороннем и левостороннем построении.

Попробуем исправить неоднозначность, рассмотрим другую грамматику со вспомогательным символом X, который будет обозначать операнд.

G: E → X | E + X | E – X | E * X | E / X
X → x

Построим выводы для той же цепочки x+x*x

E => E * X => E + X * X => E + X * x => E + x * x => X + x * x => x + x * x

или

E => E * X => E + X * X => X + X * X => x + X * X => x + x * X => x + x * x

От неоднозначности данная грамматика избавлена, но вот семантическое дерево не верно, не соответствует общепринятому в математике, сперва умножаем потом прибавляем. Возьмем другую, где T будет означать слагаемые и М - множители.

G: E → T | E + T | E – T
T → M | T * M | T / M
M → x

Разложить выражение x + x * x в данной грамматике попробуйте сами и убедитесь в однозначности данной грамматики.

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

Грамматики называются эквивалентными, если порождают один и тот же язык.

Ту би континуе… Не забывайте подписываться. =)

Кости правил

Возьмем всю ту же самую цепочку aaabb и добавим в нашу игру ещё костей с этими символами и разложим их:

Начало игры

Вы обратили внимание на формы костей? Да, верно, наша цель, собрать дерево так чтобы подошли к нашим половинкам нужные кости правил, вот так:

Конец игры

Каким образом мы можем восстановить дерево? Ну первое что бросается в глаза, это в каком направлении мы будем подбирать кости правил. Подход решения от стартового вспомогательного символа к основным называется нисходящим разбором, в обратном же направлении восходящим разбором. И так же от левых символов левосторонним, а от правых правосторонним. Примеры:

Левосторонний нисходящий разбор.

Правосторонний восходящий разбор.

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

Значение слова детерминация происходит от лат. determinatio — предел, заключение, определение, что означает определенность, однозначность, в нашем случае мы говорим о завершённых ходах, о том что всякое поставление кости на своём месте.

На этом тема закрыта, в следующий раз расскажу почему же бывает так, что 2+2*2 = 8?