Comments 8
КАМП можно применять в таких местах, где может быть неограниченное количество вложений, например при разборе языков программирование или подсчету вложенных скобок в математических выражениях. Реализовать с помощью КА невозможно, ведь количество возможных состояний конечно в отличие от стэка (я понимаю, что память тоже конечна).тут не очень понятно, обычный автомат NFA или DFA справляется с задачей разбора неограниченного количества вложенных скобок без всякой памяти.
тут не очень понятно, обычный автомат NFA или DFA справляется с задачей разбора неограниченного количества вложенных скобок без всякой памяти.
Нет, не справляется.
У КА нет никакой памяти, он не может ничего запоминать, кроме как своего состояния. Можно в принципе сделать таблицу переходов на определенное количество скобок, но опять же оно будет конечно. Примерная реализация habrastorage.org/webt/8l/cq/oi/8lcqoiow02afwvibockefwvqg0c.jpeg
Скорее имелось ввиду, что с помощью DFA нельзя определить правильность расстановки скобок, на сколь угодно большом входе.
Добавлю свои пять копеек про алгоритм Томпсона. В некоторых случаях нам не нужно строить весь DFA — сразу. К примеру, имеется исходник регулярки и для разбора строки нам нужно: распарсить ее, построить NFA и затем по идее преобразовать его в DFA для разбора. Последний шаг может занять довольно продолжительное время, а потому для экономии времени используется схема при которой DFA строиться лишь для ветки по которой идет разбор, что существенно повышает скорость работы в подобных случаях.
Это до предела упрощенная модель компьютера имеющая конечное число состояний, которая жертвует всеми особенностями компьютеров такие как ОЗУ, постоянная память, устройства ввода-вывода и процессорными ядрами
Все вышеперечисленное тоже вполне себе может быть конечным автоматом.
Sign up to leave a comment.
Теория вычислений. Введение в конечные автоматы