Обсуждение:Примеры неразрешимых задач: однозначность грамматики

☑ как-то сразу прыгаем в решение задачи, надо бы хоть написать, что хотим выполнить m-сведение в начале док-ва, а не в конце. Написать в начале, что доказываем от противного и предполагаем, что такой алгоритм существует.

☐ англоязычные термины, ссылки на англоязычные источники

Ambiguous — это "неоднозначный". "post correspondence problem" убрать (этот термин должен появиться в конспекте по ПСП). --Мейнстер Д. 03:06, 15 января 2013 (GST)

☑ что за символы z_1 .. z_n, произвольные или что? Надо пояснить.

☑ по-моему, грамматику можно сделать проще, написать, что S -> A | B

☑ не "пусть есть правила", а, наверное, зададим грамматику такими-то правилами.

☑ Поскольку [math]\forall i, j : i \ne j[/math] [math]z_{i} \ne z_{j}[/math] — вот это вообще что-то непонятное. В какой последовательности здесь рассматриваются индексы? Если в алфавите, достаточно это написать словами.

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

--Дмитрий Герасимов 12:49, 9 декабря 2012 (GST)

Это еще не все

Не забываем об орфографии, пунктуации и прочих немаловажных вещах:

☐ при записи грамматики корректнее использовать [math] \rightarrow [/math], а не [math] \Rightarrow [/math]

☐ номера правилa

☐ причем, если

☐ сказать, однозначна

☐ то значит, то значит или то, значит,

☐ однозначна, и не существует два выводадвух выводов

☐ "постовской системы соответствия" — тогда уж "экземпляра ПСП"

☐ Хорошо бы также разбить громоздкий абзац текста после определения грамматики на более мелкие.

По содержанию претензий нет. --Мейнстер Д. 03:06, 15 января 2013 (GST)