Теория вычислений. Введение в конечные автоматы

[token]

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

тут не очень понятно, обычный автомат NFA или DFA справляется с задачей разбора неограниченного количества вложенных скобок без всякой памяти.

[GlukKazan]

тут не очень понятно, обычный автомат NFA или DFA справляется с задачей разбора неограниченного количества вложенных скобок без всякой памяти.

Нет, не справляется.

[token]

Да, извиняюсь, что то я прогнал, перепутал конечные автоматы с рекурсивным спуском.

[evigore]

У КА нет никакой памяти, он не может ничего запоминать, кроме как своего состояния. Можно в принципе сделать таблицу переходов на определенное количество скобок, но опять же оно будет конечно. Примерная реализация habrastorage.org/webt/8l/cq/oi/8lcqoiow02afwvibockefwvqg0c.jpeg

[token]

Да, все верно, у меня просто в голове все в кучу уже смешано, я эти конечные автоматы и парсеры очень часто пишу чисто для разминки )

[Deosis]

Скорее имелось ввиду, что с помощью DFA нельзя определить правильность расстановки скобок, на сколь угодно большом входе.

[token]

Добавлю свои пять копеек про алгоритм Томпсона. В некоторых случаях нам не нужно строить весь DFA — сразу. К примеру, имеется исходник регулярки и для разбора строки нам нужно: распарсить ее, построить NFA и затем по идее преобразовать его в DFA для разбора. Последний шаг может занять довольно продолжительное время, а потому для экономии времени используется схема при которой DFA строиться лишь для ветки по которой идет разбор, что существенно повышает скорость работы в подобных случаях.

[Space_Cowboy]

Это до предела упрощенная модель компьютера имеющая конечное число состояний, которая жертвует всеми особенностями компьютеров такие как ОЗУ, постоянная память, устройства ввода-вывода и процессорными ядрами

Все вышеперечисленное тоже вполне себе может быть конечным автоматом.