Изменения

== 2. Контекстно-свободные грамматики (проверяются) ==# [[Формальные грамматики]]=== Базовые понятия о грамматиках ===## Пояснить пример контекстно-зависимой грамматики<ol>## Можно ещё примеров различных интересных грамматик добавить# <li value="1"> '''fixed!!!''' [[Иерархия Хомского формальных грамматикФормальные грамматики]](5) </li>#Пояснить пример контекстно-зависимой грамматики# Можно ещё примеров различных интересных грамматик добавить англоязычные термины## (и добавить ссылок ссылку на русские и английские грамматики языков программирования)# Заменить многоточия на \ldots# Оформить правильно источники. И указать конкретные страницы у уже существующегоинфрмации, либо выпилить его нафигдобавить См.также#Категория# интервики, ссылка на автоматные граммматикиВыделить в разборах жирным часть правила, например, которые есть которая раскрывается на викиданном шаге## на машину Тьюринга можно внутреннюю ссылку сделатьПримеры обозначений## Ссылку на вики Вертикальную черту заменить на ссылку примечанием\mid#В определениях скобки в Tex# Добавить интервики Интервики на другие факты (добавить См. также)рефлексивно-транзитивное замыкание#Убрать ; из определения# Добавить по примеру на каждую грамматику (примеры можно перенести из прошлого конспекта)Выводы в примерах оформить красивей# Почистить обсуждения<li> [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентностьИерархия Хомского формальных грамматик]]</li><li> [[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]] (0.5) </li>## Добавить источники информации, ссылок, интервики (на Иерархию)# ''fixed'' Категория# Почистить обсуждения# Знаки неравенств<li> [[Правоконтекстные грамматики, эквивалентность автоматам]]</li>## Англоязычные термины## Источник бесполезен без конкретного указания, где искать## Добавить интервики# '''fixed''' [[Контекстно-свободные <li> [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]</li><li> '''!!!''' [[Замкнутость КС-языков относительно различных операций]] (5) </li>## нормально оформить уже существующий источникПропущен - в КС-языках## добавить англоязычные терминыТочку в конкатенации лучше опустить## интервикиHalf некрасивый, c маленькой буквы его## Симольные скобки взять в texДобавить грамматики для дополнения к языку тандемных повторов (с доказательством) и примеру к half#Добавить примеры других грамматик# а еще тут стрелки одинаковые и в правилах (надо Добавить ссылок, см. также<texli>\to</tex>) и в выводе '''!!!''' [[Регулярная аппроксимация КС-языков]] (надо <tex>\Rightarrow7) </texli>)## пояснить, почему грамматика из первого примера неоднозначна, и привести пример аналогичной однозначной с Добавить док-вом. Написать, что есть КС-языки, для которых нет однозначных КС-грамматик, сослаться на существенную неоднозначность.во леммы## Добавить заголовковОтформатировать псевдокод## Перерисовать картинкуTex правильно оформить# '''!!!''' [[Замкнутость КС-языков относительно различных операций]]Описание перед псевдокодом перенести#Картинки убого расположены# Пропущен "свободно-контекстной грамматики" {{-- в КС-языках## Точку }} и далее встречаются баги в конкатенации лучше опуститьконспекте#Расшифровать RTN (то же с MT)# Half некрасивый, c маленькой буквы егоИсточники информации нормально оформить## Добавить грамматики для дополнения к языку тандемных повторов (с доказательством) и примеру к halfСм. обсуждения</ol>## Добавить примеры других грамматик## Добавить ссылок, см. также=== Нормальные формы КС-грамматик ===<ol># <li value="8"> '''!!!''' [[Регулярная аппроксимация КС-языковУдаление бесполезных символов из грамматики]](6) </li>#Англоязычных термины нормально оформить# Добавить док-во леммыссылок## Отформатировать псевдокодДобавить интервики## Tex правильно оформитьГрамматики оформлены криво## Описание перед псевдокодом перенестиНаписать, что такое <tex> | \Gamma | </tex>## Картинки убого расположеныНаписать, откуда берутся такие асимптотики, и как добавить очередь#Аналогично про обход в глубину# "свободно-контекстной грамматики" {{---}} и далее встречаются баги Ссылку на НФХ перенести в конспектеисточники информации#Алгоритмы оформить отдельным подзаголовком# Расшифровать RTN (то же с MT)## Источники информации нормально оформить# '''взяли''' Категория<li> [[Удаление бесполезных символов длинных правил из грамматики]]</li><li> '''!!!''' [[Удаление eps-правил из грамматики]] (6) </li>## Англоязычных термины нормально оформить## Добавить ссылок## Добавить интервики## Грамматики оформлены криво## НаписатьНехорошо, что такое <texалгоритм удаления eps-правил ссылается на алгоритм, который описан ниже {{---}} реструктуризовать конспект# Грамматику G заменить на <tex> | \Gamma | </tex>## Написать, откуда берутся такие асимптотики, и как добавить очередь## Аналогично про обход в глубину## Ссылку на НФХ перенести в источники информации## Алгоритмы оформить отдельным подзаголовком# ''fixed'' [[Удаление Написать, почему при удалении длинных правил из грамматики]]асимптотика будет линейной#Грамматики криво оформлены# Добавить источники информацииПояснить использование очереди## Подробней расписать время работыПропущены дефисы после КС местами## Лишняя запятая в алгоритме после многоточияКатегория# '''!!!''' [[Удаление eps-<li> [[Удаление цепных правил из грамматики]](3) </li>## Англоязычных Англоязычные термины оформить нормально оформить ## Нехорошо, что алгоритм удаления eps-правил ссылается на алгоритм, который описан ниже {{---}} реструктуризовать конспектПровести в алгоритме аналогию с транзитивным замыканием#Грамматика криво криво оформлена# Грамматику G заменить на <tex> \Gamma </tex>Расписать асимптотику алгоритма## Ссылку на НФХ перенести в источники информации## Написать, почему при удалении длинных правил асимптотика будет линейной## Грамматики криво оформленыКатегория<li> '''!!!''' [[Нормальная форма Хомского]] (5) </li>## Пояснить использование очередиАнглоязычные термины хорошо оформить## Пропущены дефисы после КС местамиОписать оптимальный порядок выполнения процедур нормализации (сейчас порядок не самый оптимальный, хоть всё и растёт полиномиально)# [[Удаление цепных правил из грамматики]]Константы взять в Tex#Пример грамматики криво оформлен# Англоязычные термины оформить нормальноСсылку на НФХ перенести в источники информации## Провести Заменить знаки неравенств в алгоритме аналогию с транзитивным замыканиемTex## Грамматика криво криво оформленаКатегория## Расписать асимптотику алгоритма## Ссылку на НФХ перенести в источники информации# <li> '''взяли!!!''' [[Нормальная форма ХомскогоУстранение левой рекурсии]](5) </li>## Англоязычные термины хорошо оформитьправильно#Кинуть интервики на методы нисходящего разбора (или см. также)# Описать оптимальный Написать, как выбирать порядок выполнения процедур нормализации (сейчас порядок не самый оптимальныйнетерминалов для алгоритма, хоть всё и растёт полиномиально)если можно придумать разумное правило## Константы взять в TexОтформатировать псевдокод## Пример грамматики криво оформленЗнаки неравенств заменить## Ссылку на НФХ перенести в источники Источники информациинормально оформить## Заменить знаки неравенств в TexКатегория# <li> '''!!!''' [[Устранение левой рекурсииПриведение грамматики к ослабленной нормальной форме Грейбах]](8) </li># написать, для чего она нужна# Какая асимптотика алгоритма приведения?# Добавить источники информации# Добавить примеры## Англоязычные термины нормально оформить правильно#Отформатировать псевдокод# Кинуть интервики на методы нисходящего разбора Добавить алгоритм приведения к сильной нормальной форме Грейбах (или см. такжехотя бы сказать как-нибудь подробней про неё)## Написать, как выбирать порядок нетерминалов для алгоритма, если можно придумать разумное правило<li> [[Нормальная форма Куроды]] (0.5) </li>## Отформатировать псевдокодЗаменить везде G на \Gamma## Знаки неравенств заменить</ol>## Источники информации нормально оформить# '''!!!!!''' === Алгоритмы разбора ===<ol><li value="16"> [[Приведение грамматики к ослабленной нормальной форме ГрейбахАлгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]</li>## написать, для чего она нужна<li> '''!!!''' [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]] (7) </li>#Расписать подробней и формальней# Какая асимптотика алгоритма приведения?А ещё алгоритму всё равно на eps-правила и цепные правила, надо это тоже написать## Добавить источники информацииИ желательно расписать динамики через полуинтервалы, а не отрезки## Добавить примеры## Англоязычные термины нормально Красиво всё оформить## Отформатировать псевдокод## Добавить алгоритм приведения к сильной нормальной форме Грейбах# <li> '''fixed!!!''' [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]Эрли]] (7) </li>#Отформатировать псевдокод# Аккуратно помёрджить с аналогичным конспектом первого курсаОписать понятно (гуглится ссылка, где алгоритм понятно расписан)# Доказательство плохо отформатировано# Оформить красиво источники информации<li> '''!!!''' [[Алгоритм Кока-Янгера-КасамиЭрли, модификация доказательство оценки O(n^2) для произвольной однозначной грамматики]](5) </li>#Отформатировать псевдокод# Расписать подробней и формальнейГрамматику G заменить на \Gamma#Перенести описание алгоритма перед псевдокодом# А ещё алгоритму всё равно на epsХотелось бы адекватные доказательства читать (см. обсуждения)</ol> === Опровержение контекстно-правила и цепные правила, надо это тоже написатьсвободности языка ===## И желательно расписать динамики через полуинтервалы, а не отрезки<ol># <li value="20"> '''!!!''' [[Алгоритм ЭрлиЛемма о разрастании для КС-грамматик]](6) </li>## Отформатировать псевдокод## Описать понятно (гуглится ссылкаДобавить пример не КС-языка, который удовлетворяют условию леммы, где алгоритм понятно расписан)но уже не удовлетворяет условию леммы Огдена## Доказательство плохо отформатированоИсточники нормально оформить#Добавить см. также на варианты леммы# Оформить красиво источники информацииКатегория# <li> '''!!!''' [[Алгоритм Эрли, доказательство оценки OЛемма Огдена]] (n^27) для однозначной грамматики]]</li>## Отформатировать псевдокодИсточники информации добавить## Грамматику G заменить на \GammaДобавить пример, удовлетворяющий не КС-языка, который удовлетворяет условию этой леммы## Перенести описание алгоритма перед псевдокодомКатегория## Хотелось бы адекватные доказательства читать <li> [[Существенно неоднозначные языки]] (см0. обсуждения5)</li># '''!!!''' [[Лемма о разрастании для КС-грамматик]]Англоязычные термины оформить правильно# Ссылки из См. также перенести в источники информации## Добавить пример не КСКатегория</ol> === МП-языка, который удовлетворяют условию леммыавтоматы ===## Источники нормально оформить<ol>## Добавить см. также на варианты леммы# <li value="23"> [[Лемма ОгденаАвтоматы с магазинной памятью]](0.5) </li>#Картинки увеличить# Определение жирным# ; в определении заменить на ,# Англоязычные термины правильно оформить, убрать дублирования# Источники информации добавить, См. также## '''!!!''' Сюда бы тоже неплохо пример привестиКатегория<li> [[МП-автоматы, который удовлетворяет обычной леммедопуск по пустому стеку и по допускающему состоянию, но не удовлетворяет этой эквивалентность]] (можно взять из прошлого конспекта, если там появится0.5), а так же привести пример не КС-языка, который удовлетворяет условию этой леммы</li># Добавить источники информации# Категория<li> [[Существенно неоднозначные языкиСовпадение множества языков МП-автоматов и контекстно-свободных языков]](3) </li>## Англоязычные термины Ссылки и литературу оформить правильно#Оформить доказательство красиво# Ссылки из См. также перенести в источники информацииРасписать подробней алгоритм# Категория<li> [[Автоматы Детерминированные автоматы с магазинной памятью]](0.5) </li>#В пример добавить язык автомата# Картинки увеличитьАнглоязычные термины# Категория<li> [[МП-Детерминированные автоматыс магазинной памятью, допуск до пуск по пустому стеку и по допускающему состоянию, эквивалентность]](0.5) </li>#Категория# Добавить источники информацииПалку заменить на \mid# Источники информации<li> ''''!!!''' [[Совпадение множества языков МПНормальная форма ДМП-автоматов и контекстно-свободных языковавтомата]](10) </li>## Ссылки и литературу оформить правильноНаписать!## Оформить доказательство нормально, расписать подробно алгоритм# <li> [[Детерминированные автоматы с магазинной памятьюНесовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]](2) </li>#Как-то в кучу всё в теореме. Лучше разделить совпадение по пустому стеку и по состоянию для ДМП и сравнить отдельно МП и ДМП# В пример добавить язык автомата## Англоязычные терминыДобавить источники информации# Категория# См. также<li> [[Детерминированные ДМП-автоматы с магазинной памятью, допуск по пустому стеку]]# '''!!!!!''' [[Нормальная форма ДМП-автомата]]## Написать!# [[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматаминеоднозначность]]</li>## Разве доказательство не следует из теоремы конспекта о допуске по пустому стеку?## Добавить источники информации</ol>