Формалки 11

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

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

Сперва поговорим про разные формы грамматик. Такое дело обычно называется формой Бэкуса — Наура, просто BNF. Это классическая штука без излишеств. Вот это иногда туда включают, иногда нет, но тем не менее. Дальше существует куча разных нормальных форм других. Роль некоторых из них примерно такая же, как в... Не знаю, с чем вы знакомы, с нормальными формами чего. От логики у вас была. Значит, конъюнктивную нормальную форму, дизъюнктивную нормальную форму, по крайней мере, слышали. Вот примерно такая же история. То есть мы хотим привести грамматику к некоторому достаточно строгому виду. Зачем? Ну, иногда только тем, чтобы что-нибудь там доказывать было проще. Иногда это действительно полезно для некоторых алгоритмов. Соответственно, исходя из таких соображений, нормальных форм разных их на самом деле много, каждая просто под свои нужды подгонялась. Мы поговорим лишь

Первая из рассматриваемых форм — это нормальная форма Хомского, или по-русски её обычно так и сокращают, НФХ, а по-английски это Chomsky Normal Form, соответственно, тот самый Хомский. И здесь уже начинаются некоторые приключения с её определением даже.

В большинстве случаев все разговоры будут лишь о том, как правило выглядит, то есть они не будут полностью четверку выписывать, а в нашем случае будут интересовать внешний вид правил. Здесь мы говорим о том, что правила точно бывают двух видов. Первое — это какой-то нетерминал в какой-то терминал ($A \to a$). Второе — это какой-то нетерминал в два других нетерминала ($A \to BC$).

А дальше начинается разница. Нам будет удобно говорить следующим образом: $\varepsilon$ может быть выводим только из стартового символа, и стартовый не встречается в правых частях правил. То есть для вот этого всего верно, что нетерминалы в правой части не равны $S$. Значит, еще раз, у нас правила в итоге бывают на самом деле трех видов: либо нетерминал в терминал, либо нетерминал в два нетерминала, где ни один из правых нетерминалов не равен $S$, и из $S$ выводим $\varepsilon$.

В чем разница может быть с другими определениями? Я думаю, что если вы даже Харриса откроете — классическая книжка по теории [формальных языков], она там у меня даже на страничке висит, упоминается один из материалов, — там будет в ней такое определение иметь место быть. Нормальную форму Хомского такоковую как определяют для языка, в котором нету $\varepsilon$-цепочек. То есть сначала говорят, что типа ребят, мы, значит, будем рассматривать языки, в которых $\varepsilon$-цепочки не лежат, поэтому у вас вот этого [правила для $\varepsilon$] нету. То есть говорится у вас просто, что грамматика вот с такими правилами [первого и второго видов]. А потом говорят, что любой, ну да, язык можно привести к нормальной форме с поправкой, ну, что вот придется что-нибудь вот такое добавить.

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

Грамматику можно задать в нормальной форме Хомского, и в этом смысле это действительно просто нормальная форма, способ записи. Она не делает класс уже, не делает класс шире, так же, как с конгруэнтной нормальной формой — её можно просто взять и переписать. Существуют алгоритмы преобразования грамматики в форме Бэкуса-Наура в нормальную форму Хомского. Алгоритм классический, полностью пересказывать его не нужно — его можно найти в Википедии или спросить у нейросети. Стоит обратить внимание лишь на несколько моментов, которые от источника к источнику немножко варьируются, но неплохо бы понимать, что вообще происходит.

Общие шаги алгоритма следующие. Первый шаг — это удаление длинных правил. История очень простая: мы нарезаем правую часть правила на кусочки до тех пор, пока длина правой части не станет не больше двух. Условно говоря, просто потихоньку откусываем по одному символу и вводим новые нетерминалы. Единственное, что важно: этот новый нетерминал является новым, раньше он нигде не использовался, поэтому никаких нехороших пересечений не возникло.

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

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

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

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

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

Далее, после того как мы убрали эпсилоны и нарезали правила, у нас при [неясный фрагмент]

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

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

Теперь у нас уже почти совсем все хорошо, у нас остались правила вида уже совсем хорошего, и здесь важный момент. Часто следующим шагом делают очень простую вещь. Если у вас в грамматике остались правила вида: два терминала, ну, короче, терминал где-то в правой части длины 2 остался, ну, значит, надо заводить новые нетерминалы, сказать, что у меня там есть какой-нибудь, давайте большими буквами, $T_i$, $T_j$, соответственно. Ну, и это все дело преобразовать. В принципе, правда, но есть нюанс, который

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

Недостижимый нетерминал — это нетерминал, который в процессе вывода никогда не может встретиться в нашей цепочке. Буквально, если у вас есть грамматика, где что-нибудь задано, а потом есть еще что-нибудь, тривиальный случай показывает, что некий нетерминал никак недостижим из стартового символа и никогда в выводе не встретится. Вот это мы и называем недостижимыми нетерминалами.

Непорождающие нетерминалы — это нетерминалы, из которых никогда не может получиться терминальная цепочка. То есть это нетерминалы, которые фактически будут приводить к тем печальным случаям, которые мы рассматривали ранее, когда у нас на ленте осталась цепочка, мы ничего переписать уже не можем, но в ней все еще есть нетерминалы. Это ровно они, ситуация в духе рекурсивного вызова, когда нетерминал у нас достижимый, но он всегда будет оставаться на ленте, никогда в терминал не перепишется — беда-печаль. Это всё относится к одному и тому же нетерминалу, когда в грамматике присутствуют, например, стартовый символ $S$ и некоторый нетерминал $n$.

Соответственно, такие конструкции могут остаться в грамматике после всех предыдущих преобразований. С одной стороны, формально по определению они ничему не мешают, будут выглядеть определенным образом, и все вроде бы хорошо. Но в процессе дальнейших рассуждений — если доказывается что-то про нормальную форму Хомского либо строятся какие-то алгоритмы — эти случаи оба как минимум бесполезны, а иногда могут мешать. Мешать хотя бы тем, что придется их в доказательстве отдельно рассматривать, утверждать, что они либо ни на что не влияют, либо, не дай бог, на что-нибудь повлияют. Поэтому из-за того, что мы заранее понимаем, что на язык, задаваемый грамматикой, они никак не влияют, их нужно удалить. По-хорошему, этот процесс можно назвать чисткой грамматики, а именно — удаление недостижимых и непорождающих нетерминалов.

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

Здесь, на что стоит обратить внимание, когда мы выполняем операции «удалить недостижимые» и «удалить непорождающие», важен порядок этих действий. Этот вопрос оставляется на подумать, чтобы вы нашли правильный порядок, так как это факт известный, и немного заморочились. История заключается в том, чтобы получить такой порядок, при котором достаточно запустить каждую чистку ровно один раз. Если порядок выбран неправильно, то может возникнуть ситуация, когда вы, допустим, удалили недостижимые, потом удалили непорождающие, и у вас снова появились недостижимые, из-за чего их придется чистить заново. Такой ситуации хочется избежать, хочется найти порядок, при котором один раз удалили непорождающие, потом удалили недостижимые, и всё — гарантированно получили чистую грамматику. Самое простое, что можно сделать, это попробовать придумать примерчик, где один из порядков работает, а другой нет. Пример из трех-четырех правил вполне сочиняется, так что можно немного поразмять мозги и пофантазировать.

Фактически мы выполняем завершающий шаг приведения в порядок, борясь с ситуациями, когда в длинных правых частях правил содержатся терминалы. Для этого мы вводим еще пачку новых нетерминалов, чтобы избавиться от терминалов в таких длинных правых частях, заменяя их на нетерминалы. После этого наша грамматика остается совсем-совсем хорошей, в ней не остается ничего лишнего, и все правила выглядят так, как нам надо. На всякий случай мы удалили всякое лишнее, и в общем-то грамматика у нас получилась в нормальной форме.

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

В текущем примере у нас остались только непорождающие символы, а в предыдущем примере, который уже был стерт, рассматривались недостижимые символы. Например, если сделать вот так [неясный фрагмент].

Соответственно, дальше нам нужны будут вариации на тему нормальной формы Хомского. Значит, первое и самое, наверное, общее — это так называемая 2NF, бинарная нормальная форма, наверное, по-русски двоичная. История о том, что мы, грубо говоря, вот это преобразование не делаем. У нас вот здесь вместо вот этого просто вот так вот, где длина этого в точности двойка.

То есть у нас либо нетерминал в терминал, либо там что-то с эпсилоном, либо правая часть ровно двойка. То есть фактически всё, кроме вот этого шага. Ну и цепные тоже удалили, поэтому я не стал объединять всё и писать не больше двойки, чтобы такие товарищи не попадали.

— Просто заменяем вторую продукцию на вот это? — Да, второе ограничение на вот это заменяем. Ну, вместе с вот этим. Фактически вот такая конструкция получается.

Значит, еще раз, это в каком-то смысле обобщение, ну не обобщение, да, ослабление, наверное, нормальной формы Хомского. У нас, правда, будет ослабленная нормальная, поэтому так, наверное, лучше не говорить. Но тем не менее, вариация на тему нормальной формы Хомского, когда мы вот это требование оставляем, вот это оставляем, а вот это правило заменяем на требование, чтобы правая часть была в точности 2. То есть у нас не два нетерминала, а просто два каких-то символа. Все остальное точно так же остается. Поэтому я говорю, что это все то же самое, без этого шага, где мы терминалы поназаменяли. Здесь у нас могут быть в правой части терминал-нетерминал, два терминала, ну и все. Нетерминал-терминал еще может быть, у нас же порядок есть. Вот, соответственно, и еще

Одна вещь, которая нам нужна будет, это так называемая ослабленная нормальная форма Хомского, она же WCNF. Значит, это нормальная форма Хомского без вот этого вот требования, и на самом деле без вот этого требования. Да, то есть буквально вот такая штука и всё. То есть мы избавляемся от ограничения со стартовым нетерминалом, и просто эпсилон может быть из любого нетерминала. Соответственно, в этом смысле вот здесь еще надо будет дописать, что у вас возможно появление эпсилон-правила для любого нетерминала, то есть у вас эпсилон может выводиться из любого нетерминала, а не только из стартового. И вот такую историю про то, что в правой части не может быть стартового нетерминала, вы тоже убираете. Получается просто грамматика вот с такими тремя историями, и вот это у нас WCNF.

Соответственно, наверное, это примерно всё на тему вариаций нормальной формы Хомского, что нам потребуется. Более-менее понятно, что нормальная форма Хомского здесь, наверное, самая сильная, поэтому если к ней привести можно, то к всему остальному можно, просто опустив какие-то шаги. Поэтому про это отдельно говорить вообще не буду. Но важный факт заключается в том, что любой контекстно-свободный язык можно задать грамматикой в одной, второй, третьей нормальной форме. То есть тут никаких ограничений в общем-то нет.

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

Вы прям хакеры. Давайте попробуем для начала действовать, как нас просили. Скажем, что у нас есть такая штука — это, видимо, что-то вот такое, и вот это, видимо, что-то вот такое. Предложенный вариант, видимо, был примерно вот такой: видимо, $AS$, да, $NO$ — это $BS$. Ну, здесь пока тоже я еще не до конца причесал. Естественно, дальше, что перспективно хочется действительно сделать, — ввести два нетерминала. То есть сказать, что есть что-то вот такое, есть что-то вот такое, соответственно, вот так и вот так. Ну, здесь, соответственно, история тоже про делов: что здесь $A$, а здесь $Б$, да? Единственное, что почти хорошо, единственное, что вот у нас $S$ и тут, и тут в правых частях встретились. Прошу про это не забывать, то есть если речь идет все-таки об аккуратной нормальной форме Хомского, это ограничение. Поэтому нужно еще немножко пожонглировать всем этим делом, не забывая про вот эту продукцию. Давайте я здесь напишу, чтобы она была перед глазами.

Как будто вот эта вот резка, которая у нас справа, третья строчка. Так, вы сейчас про вот этот вариант, да, говорите? Что здесь поставить? Еще раз, вот так, сейчас подождите, вы получили опять длинные правила. Ну да, но тут уже нету запереваривания [возможная ошибка распознавания]. Ну хорошо, видимо, значит, я вот здесь тоже могу, должен что-то сделать вот такое по вашей логике. Ну и у вас $n_1$ и $n_2$ превратились в непорождающие нетерминалы. Поздравляю вас. Ага, и вы получите нетерминалы, которые вводят эпсилоны, которые не стартовые. Да. Так что давайте я пока изначальный верну вариант. Что-то вы каким-то странным путем пошли. Так, здесь эски были просто, да. Можно завести новый нетерминал, который в правилах $N_1$, $N_2$… Мне кажется, вы что-то относительно разумное предложили, но я не верю, что я до конца понял. Можете еще попробовать нарисовать, чего хотите.

Опять же, если я правильно понял, сейчас будет история такая: мы на самом деле попробуем устранить эпсилон по-хорошему, то… Ну, это да, это у нас было. Не совсем, не совсем. У вас по-хорошему... Смотрите, еще да, то есть вы... В общем-то, да, вы действительно. Вы фактически попробовали убрать вот этот эпсилон отсюда, а это заменить, ну, соответственно... Останутся у вас еще варианты типа $n_1$ в $y$ и $n_2$ в $b$. В самом деле, сейчас я не понимаю, как терминировать. То есть как бы конкретно сейчас у вас плохо то, что у вас $k$ [возможная ошибка распознавания] превратился в непорождающий. Еще одно правило для $k$ такое. Не для $k$. Смотрите, давайте, я понял, садитесь сейчас. Мысль отчасти верная. Давайте.

Поступим следующим образом. Давайте сперва попробуем. Сейчас я подумаю, что мы сперва попробуем. Ну да, давайте так и сделаем. Значит, давайте скажем, что мы просто... Сейчас, а как мы тут? Так. Сейчас. То есть да, короче, давайте сперва это правильный ответ, видимо, примерно вот такой. Для данного случая. Ну, на самом деле, потом устранить цепные [возможная ошибка распознавания: цепные правила], получить что-то вот такое. Как он получился? Сейчас попробую объяснить. Значит, возможно, по шагам. Фактически да, мы сделали копию на самом деле полную [нетерминалов], чтобы оставить стартовый нетерминал в покое и дальше с ним не делать. Потом мы взяли и как бы устранили вот это правило, да, у нас осталось два варианта, равно, как я говорил, либо мы предполагаем, что кашка [нетерминал] у нас не пустая, либо мы предполагаем, что кашка у нас пустая. Ну, то, что я стер, да, там, нетерминалы когда были. И соответственно, получилось вот то, что получилось, то, всё есть теперь у нас более-менее честно, да. Вот здесь давайте сотру просто аккуратно, напишу, что это кашки. Ну и всё, да, то есть у нас зачем... [неясный фрагмент]

Дальше лектор продолжает рассуждать у доски, обращаясь к аудитории: мы должны сейчас... У вас получится какая-то странная история, у вас получится, ну да, бесконечная грамматика получится, и зачем нам это счастье, так она и уже в нормальной форме Хомского нет. Сейчас, еще раз, во-первых, алфавиты у нас все конечные, мы с этого начинали, это ограниченность и конечность — две разные вещи, да. Вы можете взять это, очень большой в этом смысле, он не ограничен ничем, да, но он конечный, и нет, эта такая идея тут не очень работает.

Так, еще давайте вот этим развлекаемся, если этим путем пойдем, что у нас получится? Тут немножко веселее, хотя история примерно такая же, судя по всему. Так, я здесь уже за... [неясный фрагмент] Что у нас здесь получится? На самом деле, прям такая же история, допишите этот вариант тоже до конца, попробуйте. Что у нас тоже нам, видимо, понадобится ввести какой-то нетерминал дополнительный. Да, соответственно, здесь у нас появятся две кашки. Вот, и еще у нас появятся цепные правила [возможная ошибка распознавания], типа вот такого, [нетерминал] в B. Соответственно, вот этот сразу в B. Ну а вот этот, соответственно, у нас либо в B, либо в BK. Такое должно получиться. Да, то есть у нас была как раз цепочка, мы подтянули правый конец. По-моему, так.

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

С нормальной формой Хомского на этом более-менее всё, она понадобится в дальнейшем, а сейчас лекция переходит к обсуждению других представлений.

Значит, следующая вещь, это то, что называется [неясный фрагмент].

Говоря об Extended Backus-Naur Form (EBNF), или расширенной форме Бэкуса — Наура, стоит сразу отметить одну тонкость. Существует специальный ISO-шный стандарт, который стандартизует то, что в нем называется расширенной формой Бэкуса — Наура, включая синтаксис и то, как выглядят правила. Однако мы не будем говорить об этом стандарте. Более того, существует масса других названий, которые на самом деле говорят об одном и том же, например, regular EBNF и другие — их существует около пяти разных вариантов, и сейчас станет понятно, почему они появились.

Под EBNF мы будем понимать следующее, если говорить только про правила. Правила у нас будут следующего вида: нетерминал переходит в некоторую регулярку над смешанным алфавитом. Фактически у вас правило представляет собой нетерминал, переходящий в некоторую регулярку. Как уже говорилось ранее, когда мы только начинали говорить про грамматики, еще в обычной БНФ появилась возможность одинаковые правые части склеивать через альтернативу, и эта самая альтернатива никуда не денется. Но в действительности дело обстоит так, что вы можете в правой части правил просто писать регулярное выражение — собственно, именно поэтому EBNF так и называется. Например, в некоторых источниках просто прямо честно говорят, что правая часть регулярная, в смысле, что там написана регулярка. И хотя мы будем называть это EBNF, синтаксис будет скорее из регулярных выражений, чем из того ISO-шного стандарта. В целом, можно написать что-нибудь вот такое [неясный фрагмент]. Например — пока не важно, что это значит, но я могу написать такое. Или, не знаю, давайте напишем что-нибудь еще более хитрое, какую-нибудь альтернативу.

Самый простой способ понять, как это работает — это взять и преобразовать. Понятно, что форма Бэкуса — Наура — это частный случай вот этого дела, поэтому в одну сторону преобразовывать неинтересно, интереснее в другую. А чтобы преобразовать это в условную нормальную форму, в форму Бэкуса — Наура, нужно просто вспомнить, как по регулярному выражению и конечному автомату построить линейную грамматику: лево-линейную или право-линейную. То есть, соответственно, у вас одно и то же. Для нас это будет одним и тем же. Формально EBNF — это что-то, что в ISO прописано, но мы будем всё такое называть EBNF.

Значит, давайте, собственно, вспомним, что нам нужно. Нам нужно по конечному автомату построить леволинейную грамматику. Соответственно, у нас здесь… Давайте методом пристального взгляда построим какой-нибудь автомат. Эпсилоны нас пугают. Когда мы строим по автомату линейную грамматику, что нам от автомата надо? [неясный фрагмент] требования грамматики от автомата, что нужно? [неясный фрагмент]. Меня больше интересует начать, не бороться с переходами или не надо сейчас ваш алгоритм преобразования конечного автомата в леволинейную грамматику нормально живет со всеми переходами? Бороться с вопросами — это просто будет так. Там, где все переходы… Чего? У вас какая-то каша в голове или я вас не понимаю? А возможно, и то, и другое. А возможно, второе — следствие первого.

Ну ладно, тем не менее, значит, еще раз. Опять же, я сейчас не требую алгоритм. Мне сейчас интересно, я хочу методом пристального взгляда нарисовать автомат для этой регулярки. Мне заморачиваться над тем, чтобы звездочку нарисовать как-то аккуратно без эпсилон-переходов или забить на это, потому что все остальное без эпсилон-переходов легко рисуется, а вот со звездочкой надо аккуратно подумать, чтобы какой-нибудь ерунды не произошло? И вот, соответственно, дальше я буду этот автомат преобразовывать в леволинейную грамматику. И вот вы умеете преобразовывать автомат с эпсилон-переходами в леволинейную грамматику? У нас получается, когда мы решаем по автомату, мы не умеем. В смысле, если считаем как символ. Да, да. Ну вот, еще раз, просто регулярка над смешанным алфавитом. Да, буквально, просто символ. Нет, можем.

Еще раз. Я сейчас хочу просто взять и нарисовать автомат, не прибегая к нему, к алгоритмам. Меня просто волнует один простой вопрос: не стоит задумываться над тем, чтобы не рисовать эпсилон-переходы? Или пофигу, нарисуем и дальше будем с ним работать, не надо будет никуда трансформировать? Окей, давайте нарисуем. Значит, что у нас тут будет? У нас будет 0, 1. Так, сейчас, давайте не так. h, c, 0, 1. Это стартовый. Дальше s, дальше b. Хорошо, здесь должны быть эпсилон-переходы, чтобы со звездочкой все хорошо получилось. Вот эту часть нарисовал вообще без проблем, рисуется внутри скобочек, ну вот она какая-то такая: из нуля в три, из трех в ноль. Теперь здесь все нормально, здесь у нас никакой [возможная ошибка распознавания: так]… А финальное состояние какое? Третье. Ну ладно, хорошо, допустим, можем от этого безобразия избавиться.

Мы можем нарисовать эквивалентный конечный автомат, который задает ровно тот же язык, но без ε-переходов [возможная ошибка распознавания: общих переходов]. Лектор стирает предыдущую схему с доски и обозначает, что состояние $b$ является финальным.

Теперь вспоминаем, как по автомату построить лево-линейную грамматику или право-линейную — какую кому удобнее. Нетерминалами будут просто состояния автомата, например, какие-то $S$ и $S'$, или буквально обозначения вроде $q_0, q_1$ [возможная ошибка распознавания в тексте: 0 в А1, 0 в...]. Мы пишем правила перехода.

Вспоминаем про финальное и стартовое состояние: стартовое у нас действительно есть, а $q_0$ — финальное, его нужно финализировать. То есть теперь мы фактически говорим, что $S$ у нас — это $q_0$. Если что, лектор не гарантирует, что получится нормальная форма или что-то подобное, задача сейчас — просто построить S-грамматику [возможная ошибка распознавания: S-грамматику / эс-грамматику]. Соответственно, в этом плане мы все преобразовали и убедились в том, что EBNF случайно не оказалась более выразительной, чем какая-то нормальная форма или форма Бэкуса-Наура [в транскрипте: форма баксонала]. Соответственно, EBNF опять же...

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

Поговорим про такую штуку, как RSM, Recursive State Machine. Это еще один способ представить контекстно-свободный язык. Если совсем просто, то мы на правую часть правила смотрим сразу как на конечный автомат.

Если чуть более аккуратно, то требования к RSM следующие. Во-первых, у нас есть глобальный набор состояний, нетерминальный алфавит, терминальный алфавит и стартовый символ. Во-вторых, имеется набор боксиков — давайте назовем это так. Эта штуковина представляет собой конечный автомат для каждого нетерминала. При этом мы будем требовать, чтобы эти товарищи были уникальны: для любого нетерминала у нас не больше одного боксика, не более одной бэшки. То есть мы буквально рассматриваем пачку конечных автоматов над смешанным алфавитом.

Интуитивно это буквально автоматы, построенные по регулярному выражению в правой части, но с несколькими оговорками. Во-первых, мы говорим, что у нас для каждого нетерминала ровно один боксик, ровно один автомат. Опять же, просто чтобы избежать каких-то таких конструкций, когда здесь еще что-нибудь написано — давайте объединим через альтернативу и забудем про это всё.

Чисто технически нам будет удобно считать, что состояния везде глобальные. То есть у нас есть общее множество состояний, а здесь фактически у вас множество состояний для конкретного боксика — это подмножество кушек. При этом, естественно, они не пересекаются: для разных нетерминалов эти множества состояний дают пустое пересечение. У нас фактически состояния для автоматов задают разбиение общего множества состояний без лишних состояний. Естественно, выделен боксик для стартового нетерминала.

Что касается эквивалентности, тут немножко сложнее. Если действовать ровно так, как мы действуем — просто трактовать этот автомат как конечный автомат, построенный по правой части, то в целом мощность не сильно страдает. Но в некоторых статьях (в книжках взрослых не видел, но в статьях есть) определение RSM дается такое, что в итоге формализм оказывается чуть мощнее, чем контекстно-свободные языки. И мы этого касаться не будем, поэтому в нашем случае всё будет хорошо, всё будет эквивалентно и замечательно.

Собственно, здесь уже, в принципе, да — если буквально сделать вот так, сказать, что это автомат для нетерминала $S$, ну вот это мы RSM-ку получили по нашей вот этой грамматике.

Язык задает... Давайте я все это сотру, зачем оно надо? То есть у меня может быть какая-нибудь вот такая история. Значит, у меня для с... не знаю, да, давайте простую сейчас... Давайте какую-нибудь простую совсем вещь, неважно. Значит... давайте так. Значит, я же сам говорю, сам рисую ерунду. Значит, да, вот это — это финал. Попробуйте написать грамматику в BNF для этого дела. Для начала.

Ну, опять же, у нас внезапно могут оказаться какие-нибудь левые терминалы, для которых мы не задали правую часть, поэтому у нас может быть ноль боксиков для нетерминала. Это, конечно, экзотика, такого лучше не допускать. А в остальном для, ну, буквально каждого нетерминала ровно один автомат. Поэтому в сумме не более одного. То есть история ровно о том, чтобы не было вот такого. А здесь я написал еще, что для $N_1$ еще какой-нибудь автомат бывает. Не знаю, какой. Вот такого у нас не бывает. Опять же, мы знаем, что объединение регулярных языков — это регулярно, давайте один автомат нарисуем, и мы успокоимся, если говорить про рациональную сторону вопроса.

Ну, это, короче, вот эта история на самом деле. Ну а фактически это конечный автомат, буквально, просто в какой-то изначальной литературе он реально рисовался как прямоугольничек с автоматом, и у него были входы-выходы. Соответственно, термин оттуда прижился. В целом — просто конечный автомат, который еще и назвали именем нетерминала. Больше в этом ничего нет. Но изначально он реально был как коробочка. А в целом, в правой части, это как бы конечный автомат... В котором боксики есть? Да нет там никаких... Еще раз, я говорю, что термин «бокс» возник просто из изначальной визуальной нотации, что их рисовали как прямоугольнички, не просто конечный автомат. В целом — просто набор конечных автоматов.

Из полезных требований — два: что для каждого нетерминала не больше одного, и что все состояния глобально занумерованы [неясный фрагмент]. Нет, ну вот у нас... опять же, еще раз, про конечный автомат никто не говорил, что он должен быть связанным. Поэтому в целом вот эту историю можно трактовать как один конечный автомат, просто из двух компонент. Другое дело, что не то чтобы это для нас будет нести какой-то смысл, поэтому, в принципе, можете смотреть на это как на большой конечный автомат, в котором несколько компонент... [возможная ошибка распознавания: муки] потому что, еще раз, формально про конечный автомат никто не говорил, что он должен быть в связи. Пусть будет так. Для этого же языка записать грамматику в...

То есть опять же, можно методом пристального взгляда сразу по шагам понять, как из этого дела получить BNF, а дальше мы проворачивали только что шаги, как какую-нибудь нормальную уже грамматику получить. Либо можно, в принципе, сразу понять, что же это за язык такой будет, и попробовать для него грамматику написать. То есть задача сейчас не заставить вас формально трансформировать, скорее заставить вас понять, что же здесь за язык получился, чтобы вы его в других терминах смогли описать. Например, в терминах BNF. А дальше варианта два: либо вы посмотрели на эту картинку и поняли, что это за язык, написали грамматику, либо не сразу поняли, поэтому решили действовать по шагам. Самое простое — это выписать BNF и попробовать трансформировать, как мы только что это делали, но я стер. Регулярку вы можете сказать, только ее в BNF нету, поэтому бесполезное размещение, себе записать можете как промежуточный шаг. То есть как-то чтобы и BNF здесь записать, тут много ума не надо, да, будет тут что-нибудь вот такое звездочка 1. Это я вам и так могу написать, самый безболезненный шаг. Ну хорошо, я это сделал. Он у вас уже построен. Я не знаю, зачем вы это делали, поэтому говорю, что самый странный шаг, но можно, да, пожалуйста. Скорее вот поэтому автомату взять и провернуть построение леволинейной грамматики, условно говоря, ну по одному, второму склеить все это дело потом.

Из 0 в $\varepsilon$, из 1 в $n_1$ в 1, из 2 в $b_0$. Куда еще раз? В $b_0$. Из $n_1$ в 3, из 3 в $c_4$, из 3 в $\varepsilon$. $c_4$, $c_5$. $c_5$, ага. $c_5$ в $d_3$. В $d_3$. Ну, я надеюсь, что правильно, потому что просто по шагам провернули, пробежались. Хорошо.

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

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

Подводя итог, теперь мы знаем различные формы и способы задания грамматик и языков, которые можно выписать в виде аббревиатур. У нас бывают разные нормальные формы, такие как нормальная форма Бэкуса-Наура, нормальная форма Хомского, а также двоичная нормальная форма. Кроме того, для задания языка используются EBNF (расширенная форма Бэкуса-Наура) и RSM (рекурсивные синтаксисные диаграммы). Если предыдущие понятия относятся больше к формам самой грамматики, то последние трактуются как способы задания языка.

Как самостоятельный механизм, примерно так же, как регулярное выражение и конечный автомат, интуитивно мы понимаем, почему это одно и то же, но всё-таки рассматриваем их как разные объекты. Из того, что не звучало, но чтобы не казалось, что на этом мир заканчивается, бывает, например, нормальная форма Грейбах — тоже так, просто интереса ради можно почитать, нам она встретится просто не здесь, поэтому говорить про неё не буду. Наверняка существуют ещё какие-нибудь, точно существуют, просто опять же, поскольку мы пересекаться с ними не будем, и бог с ним.

Про преобразования между этими объектами тоже в общем-то поговорили. Соответственно, в нашем курсе всё более-менее будет эквивалентно, да, вот RSM такой со звёздочкой эквивалентен, потому что опять же в нашем курсе будет. Но вот аккуратнее с терминологией, потому что встречаются работы, в которых RSM определённым образом таким, что эквивалентность нарушается. RSM — это про просто ещё нет, это просто сейчас ещё здесь тоже нормальные формы не все, да, и БНФ нормальность — ничего не сказано, просто ещё один способ задать контекстно-свободный язык, да, просто разные способы задать контекстно-свободные языки.

Наверное, у вас сейчас как-то возникло возмущение в духе: «Куда вы делись, стековые машины?», ведь вам наверняка рассказывали про них, поэтому, наверное, ожидаемо, что они здесь будут. Но я думаю, что мы после перерыва как раз прикрутим сюда стековые машины через RSM, это достаточно естественным образом делается. Сейчас пока, наверное, более-менее всё. Соответственно, дальше мы поговорим как раз про то, где здесь берётся стек, наверное, на примере RSM это проще всего понять, и дальше поговорим уже про, видимо, лемму о накачке, ещё про какие-то формальные такие свойства, чтобы, видимо, уже на следующей неделе после летучки перейти к каким-то алгоритмам. Наверное, на этом сейчас всё, спасибо за внимание, встретимся после перерыва.