Обсуждение:Построение по НКА эквивалентного ДКА, алгоритм Томпсона

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

В доказательстве слишком много тире. Там половину надо просто удалить. В другой половине тире стоит из-за кривизны фразы, соответственно, фразу надо перестроить Например: «Рассмотрим последовательность состояний НКА, когда принимали слово — блаблабла» — тут надо нормально писать, как в доказательствах пишут: «Рассмотрим слово w …», затем с помощью пар в треугольных скобочках и «штопора» надо ввести последовательность состояний НКА, соответствующую переходам по символам этого слова; откуда ты в той же строчке взял последовательность состояний ДКА — загадка, ведь цель доказательства, по сути, построить эту последовательность. Короче, ты написал доказательство так, как рассказываешь у доски, когда есть аудитория с фидбэком и всё такое. Здесь же письменное творчество — изложи, пожалуйста, всё чётко и последовательно.

Обязательно нужен пример преобразования какого-нибудь простенького (но, разумеется, нетривиального) автомата с картинками. Без этого никак.

Мне страшно представить, что ты курил, чтобы так ввести стрелочки в псевдокоде. Во-первых, все нормальные люди, когда показывают добавление в очередь или извлечение из неё, очередь пишут слева, соответственно, стрелочки надо в другую сторону. Во-вторых, Кормен, например, использует такие стрелочки для присвоения. Зачем нам лишняя путаница? У очереди (как АТД) есть интерфейс: push и pop. Ну ведь если использовать эти слова, то гораздо ситабельнее псевдокод становится.

Кирилл Елагин

В общем и целом

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

Если нет, то тебе нужно просто прислать кому-нибудь из нас недостающую картинку.

Евгений Лукьянец

Псевдокод алгоритма немного странный

А именно, он ничего не дает на выходе. Просто что-то вычисляет, а чего куда зачем -- непонятно.--Roman Kolganov 19:03, 23 января 2012 (MSK)

Доказательство тяжелое, n не введено вообще (используется в асимптотике) --Demid.Kucherenko 17:19, 1 января 2017 (MSK)