Изменения

== '''в процессе проверки''' 2. Контекстно-свободные грамматики ==# '''взяли''' [[Формальные грамматики]]## примеры неинтересные, хотя бы какую-нибудь Пояснить пример контекстно-зависимую грамматику надо. Станкевич рассказывал клевый пример с грамматикой 0^n 1^n 2^n, вот его надо запилитьзависимой грамматики## определение выводимости за 0 или более шагов немного неправильное, надо бы потребовать, чтобы альфа было равно первому гамма, а бета — последнему гамма. Ну и написать что это рефлексивно-транзитивное замыкание. ## заголовки здоровенные, они первого уровня (=) , а надо второго (==)## англоязычные термины## ссылки на английские источникиМожно ещё примеров различных интересных грамматик добавить# '''!!!''' [[Иерархия Хомского формальных грамматик]]

## Внутреннюю ссылку на ДКАДобавить интервики# '''взяли!!!''' [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]

## Расписать формально пример грамматики, который уже есть, указать, что именно является множеством нетерминалов, что — множеством терминалов и т.п.Симольные скобки взять в tex

## Добавить заголовков## Перерисовать картинку# '''взяли!!!''' [[Замкнутость КС-языков относительно различных операций]]## Че за Пропущен -в КС-? Заменить на —языках## Точку в конкатенации лучше опустить## Half некрасивый, в \mathrm c маленькой буквы его## В конкатенации что-то немного муть написана## "Необходима картинка. " — запилить!Добавить грамматики для дополнения к языку тандемных повторов (с доказательством) и примеру к half## Про разворот — доказатьДобавить примеры других грамматик## побольше внутренних Добавить ссылок, на МП-автомат там, например## проставить категориисм. также# '''взяли!!!''' [[Удаление бесполезных символов из грамматикиРегулярная аппроксимация КС-языков]]## запилить пример (уже есть)Добавить док-во леммы## англоязычных терминов где можноОтформатировать псевдокод## если есть, ссылок на википедию.Tex правильно оформить## вообще нет внутренних ссылок, надо бы добавитьОписание перед псевдокодом перенести## "нетерминалы правой части являются порождающими" — правой части правила, наверноеКартинки убого расположены## первый пример сделай чуть более интеллектуальным, добавь что"свободно-нибудь типа контекстной грамматики"D {{---> aD", напримре }} и далее встречаются баги в конспекте## Расшифровать RTN (а то какой дурак будет вводить нетерминал без правил :) же с MT)## асимптотики какие-нибудь нужны## ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. такжеИсточники информации нормально оформить# '''взяли!!!''' [[Удаление eps-правил бесполезных символов из грамматики]]## запилить пример (уже есть)Англоязычных термины нормально оформить## Добавить ссылок## Добавить интервики## англоязычных терминов где можноГрамматики оформлены криво## если естьНаписать, ссылок на википедию.что такое <tex> | \Gamma | </tex>## почти нет внутренних ссылокНаписать, откуда берутся такие асимптотики, надо бы и как добавитьочередь## Аналогично про обход в глубину## ну и надо добавить ссылку Ссылку на нормальную форму Хомского НФХ перенести в какой-нибудь См. такжеисточники информации## асимптотики какие-нибудь нужны. Вроде для произвольной Алгоритмы оформить отдельным подзаголовком# [[Удаление длинных правил из грамматики это сложно посчитать, но можно: 1. сослаться куда-нибудь на оценки асимптотики. 2. привести пример, на котором будет экспоненциальное ]]## Добавить источники информации## Подробней расписать время работы (вроде тут так можно) 3. написать, что обычно этот алгоритм запускается после удаления длинных правил, и там все полиномиально (сослаться на НФХ)## для алгоритма поиска eps-порождающих точно можно асимптотику написатьЛишняя запятая в алгоритме после многоточия# '''взяли!!!''' [[Удаление цепных eps-правил из грамматики]]## какАнглоязычных термины нормально оформить ## Нехорошо, что алгоритм удаления eps-то странно в примереправил ссылается на алгоритм, который описан ниже {{---}} реструктуризовать конспект## Грамматику G заменить на первом шаге вроде надо взять все пары (A, A), (B, B), (C, C), (D, D)<tex> \Gamma </tex>## англоязычных терминов где можноСсылку на НФХ перенести в источники информации## если естьНаписать, ссылок на википедию.почему при удалении длинных правил асимптотика будет линейной## Грамматики криво оформлены## ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. такжеПояснить использование очереди## асимптотикуПропущены дефисы после КС местами# '''взяли''' [[Удаление длинных цепных правил из грамматики]]## англоязычных терминов где можноАнглоязычные термины оформить нормально## если есть, ссылок на википедию.Провести в алгоритме аналогию с транзитивным замыканием## ну и надо добавить ссылку на нормальную форму Хомского в какой-нибудь См. такжеГрамматика криво криво оформлена## Расписать асимптотикуалгоритма## Ссылку на НФХ перенести в источники информации# '''взяли!!!''' [[Нормальная форма Хомского]]## "Несколько определений" — а определение одноАнглоязычные термины хорошо оформить## Описать оптимальный порядок выполнения процедур нормализации (сейчас порядок не самый оптимальный, выкинуть вообще этот пункт хоть всё и вынести определение НФХ растёт полиномиально)## Константы взять в заголовокTex## Пример грамматики криво оформлен## если есть, ссылок Ссылку на википедию.НФХ перенести в источники информации## такие кавычки Заменить знаки неравенств в примере мерзко как-то выглядят, надо либо прямые, либо вообще забить и писать без кавычекTex# '''!!!''' [[Устранение левой рекурсии]]# # Англоязычные термины оформить правильно## Кинуть интервики на методы нисходящего разбора (или см. также)## Написать, как выбирать порядок нетерминалов для алгоритма, если можно придумать разумное правило## Отформатировать псевдокод## Знаки неравенств заменить## Источники информации нормально оформить# '''!!!!!''' [[Приведение грамматики к ослабленной нормальной форме Грейбах]]

## какая Какая асимптотика алгоритма приведения?## ссылки на Добавить источники? --[[Участник:Dgerasimov|Дмитрий Герасимов]]информации## Добавить примеры## Англоязычные термины нормально оформить## Отформатировать псевдокод# '''!!!''' [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]# # Аккуратно помёрджить с аналогичным конспектом первого курса# '''!!!''' [[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]# # Расписать подробней и формальней# '''!!!''' [[Алгоритм Эрли]]# # Отформатировать псевдокод## Описать понятно (гуглится ссылка, где алгоритм понятно расписан)## Доказательство плохо отформатировано## Оформить красиво источники информации# '''!!!''' [[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]]# # Отформатировать псевдокод## Грамматику G заменить на \Gamma## Перенести описание алгоритма перед псевдокодом## Хотелось бы адекватные доказательства читать (см. обсуждения)# '''!!!''' [[Лемма о разрастании для КС-грамматик]]## Добавить пример не КС-языка, который удовлетворяют условию леммы## Источники нормально оформить## Добавить см. также на варианты леммы

# # Источники информации добавить## '''!!!'взяли'' Сюда бы тоже неплохо пример привести, который удовлетворяет обычной лемме, но не удовлетворяет этой (можно взять из прошлого конспекта, если там появится), а так же привести пример не КС-языка, который удовлетворяет условию этой леммы# [[Существенно неоднозначные языки]]## добавить английские Англоязычные терминыоформить правильно## добавить всякое интервики## добавить ссылок на русские и английские Ссылки из См. также перенести в источники## упомянуть то, что проверка грамматики на неоднозначность неразрешима и добавить ссылку на это.информации

# '''fixed''' # Добавить источники информации# [[Совпадение множества языков МП-автоматов и контекстно-свободных языков]]## Исправить оформление списков: нужно использовать либо точки, либо нумерацию числами/символами, но не оба способа одновременно.## Картинка. Что она означает?## Доказательства утверждений написаны непонятно.## Вообще, вся статья является сжатой копипастой из соответствующей главы ХМУ, возможно, нужно полностью переписать ее.Ссылки и литературу оформить правильно

# '''!!!!!'''[[Нормальная форма ДМП-автомата]]## написатьНаписать!