Алгоритм преобразования НКА в эквивалентный ДКА

[KvanTTT]

Недетерминированный конечный автомат (НКА) – это КА, у которого есть 2 и более переходов по одному и тому же символу.

Ну вообще это еще тот, у которого есть ε переходы.

[Maxsmile123]

Для НКА необязательно наличие ε-переходов. В примере приведён как раз НКА без них. Но обязательное условие для ДКА - отсутствие ε-переходов, про которое я забыл упомянуть в определении. Благодарю за комментарий! Исправил.

[KvanTTT]

Да, необязательное. Тут правильно использовать ИЛИ: т.е. если есть что-то одно, то это НКА.

[amarao]

Огромное спасибо за тематику, это то, что очень нужно на Хабре.

Будет очень хорошо, если в районе теоретической проблемы всегда будет показываться практическая (что не работает если не сделать..., или что станет лучше, если сделать). Многие теоретические работы это пропускают или подразумевают, что читатель сам догадается, но для полезных (с практической стороны) статей именно "проблема" является опорной (и часто оказывается в результатах поиска, потому что люди обычно ищут описание проблемы, а не решение или вводные данные).

[kzn]

Практическая ценность НКА -> ДКА (очень) быстро матчить простые регулярки например

[amarao]

Вот именно 20-30% статьи, посвящённой объяснению этого феномена, очень и не хватает. Наглядные примеры, объяснение почему, объяснение почему иначе нельзя (или сложно). Академические бумаги очень это обходят и не любят писать, а мне кажется, это основное полезное для запоминания.

[kzn]

Смутила вот эта фраза "Любой алгоритм можно представить в виде конечного автомата."

С помощью КА без памяти нельзя проверить правильность скобочной последовательности же.

[Maxsmile123]

Решил поглубже изучить данный вопрос. И да, Вы оказались правы. Речь шла про машину Тьюринга, которая является наиболее общим и мощным автоматом. Конечный автомат не обобщает вычисления, а может применяться лишь для примитивных функций. Спасибо за замечание! Если интересно, то вот неплохая статья на эту тему.