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

Question

Пусть L - это язык, принятый DFA. Пусть L - это язык, полученный путем удаления последнего символа каждой строки L. Узнать, можно ли построить DFA, принимающий L.

Как подойти к этой конкретной проблеме?

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

Answer 1

Ваш подход имеет 2 проблемы: Существует не уникальный предшествующее состояние, может быть много и если вы сделаете их окончательным (если они не являются) вы большую часть времени perturbating исходного языка и добавление к нему дополнительных слов. Но ты на правильном пути. Решение состоит в том, чтобы удалить последнее состояние и добавить новое конечное состояние с переходами epsilon из всех предыдущих состояний в новое конечное состояние.