Объясните, что такое префикс в регулярном выражение

Сообщение было отмечено VSI как решение

Решение

Один или ни один? Если один, то как это связано с условием задачи? Если ни один, то зачем строить второй автомат? Как второй автомат связан с условием задачи? Вы понимаете, что если нулей и единиц поровну, то это не означает, что ни один префикс не содержит нулей на два больше, чем единиц, или единиц на две больше, чем нулей? Например: 1100.

Любой автомат строится с помощью полного перебора. Каждому состоянию соответствует некоторая характеристика прочитанного префикса. Например, автомат может находиться в одном состоянии, если в прочитанном префиксе количество единиц на 1 больше количества нулей, и в другом состоянии, если в прочитанном префиксе единиц и нулей поровну. Для каждого состояния нужно рассмотреть все возможные символы алфавита и решить, куда делается переход при прочтении этого символа. Например, если текущее состояние говорит, что в прочитанном префиксе единиц и нулей поровну, и затем читается единица, то автомат переходит в состояние, в котором единиц на 1 больше количества нулей. Нужно добавлять новые состояния, пока не наступит насыщение, то есть все новые переходы из вновь добавленных состояний будут осуществляться в уже существующие состояния.

0