1679
правок
Изменения
→2. Контекстно-свободные грамматики
== 2. Контекстно-свободные грамматики ==
# [[Формальные грамматики]]
## примеры неинтересные, хотя бы какую-нибудь контекстно-зависимую грамматику надо. Станкевич рассказывал клевый пример с грамматикой 0^n 1^n 2^n, вот его надо запилить
## определение выводимости за 0 или более шагов немного неправильное, надо бы потребовать, чтобы альфа было равно первому гамма, а бета — последнему гамма. Ну и написать что это рефлексивно-транзитивное замыкание.
## заголовки здоровенные, они первого уровня (=) , а надо второго (==)
## англоязычные термины
## ссылки на английские источники
# [[Иерархия Хомского формальных грамматик]]
## добавить англоязычные термины
## добавить ссылок на русские и английские источники. И указать конкретные страницы у уже существующего, либо выпилить его нафиг.
## интервики, ссылка на автоматные граммматики, например, которые есть на вики
## на машину Тьюринга можно внутреннюю ссылку сделать
# [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]
# [[Правоконтекстные грамматики, эквивалентность автоматам]]
## Англоязычные термины
## Источник бесполезен без конкретного указания, где искать
## Внутреннюю ссылку на ДКА
# [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
## нормально оформить уже существующий источник
## добавить англоязычные термины
## интервики
## Расписать формально пример грамматики, который уже есть, указать, что именно является множеством нетерминалов, что — множеством терминалов и т.п.
## а еще тут стрелки одинаковые и в правилах (надо <tex>\to</tex>) и в выводе (надо <tex>\Rightarrow</tex>)
## пояснить, почему грамматика из первого примера неоднозначна, и привести пример аналогичной однозначной с док-вом. Написать, что есть КС-языки, для которых нет однозначных КС-грамматик, сослаться на существенную неоднозначность.
# [[Замкнутость КС-языков относительно различных операций]]
# [[Удаление бесполезных символов из грамматики]]
