ДКА с маленькой деталью

[arseniiv]

Как-то давно мне пригодилось такое маленькое обобщение ДКА — кроме переходов по символу из каждого состояния допускалось до одного перехода по пустой строке, который делался (обязательно), если никакой переход по символу не получился; автомат остаётся детерминированным при понятно каких условиях. Наверняка такие автоматы где-то уже описаны и названы. Подскажите, кто знает.

P. S. Переход по пустой строке, конечно, не должен сопровождаться и никакими выходными символами, если автомат их выдаёт.

-- Сб сен 19, 2015 08:27:11 --

А, вот у Хопкрофта и др. во «Введении в теорию языков и вычислений» НКА с ε-переходами ($\varepsilon$ здесь обозначение пустой строки) называются просто ε-НКА. По аналогии мои автоматы можно звать ε-ДКА, видимо. Но всё равно от комментариев не откажусь.

[iifat]

Ну, помнится, все НКА эквивалентны стандартным ДКА. Ваши, как мне кажется, посредством их (НДКА) вполне реализуются. Так что для практических целей могут быть удобнее, но каких-то принципиальных теоретических последствий не должны бы нести, не?

[arseniiv]

Да, всё реализуется, и даже ДКА — это одновременно и частный случай НКА. А ε-ДКА мог бы быть так же частным случаем ε-НКА, но нет: мы не можем пойти куда-то параллельно из состояния 2, в которое попали по ε-переходу из состояния 1, и самого 1 — в результате получится несогласие с описанием, т. к. мы в моём случае никогда не перейдём из 2 по символам, по которым можем перейти из 1. (Чувствую, проще было бы нарисовать картинку, чем сейчас городить этот словесный огород, но пока немного лень. Надеюсь, не слишком непонятно получилось.)

Из ε-ДКА эквивалентный ДКА мы, конечно, как и из [ε-]НКА, получить можем, и даже ещё проще, чем с [ε-]НКА; это просто самое простое сокращение некоторых ДКА, которое приходит в голову. Так что принципиальных теоретических последствий я тоже не вижу. Но, как показано выше в этом посте, ДКА : НКА ≠ ε-ДКА : ε-НКА, так что мне не нравится название, которое я здесь сам и дал, и хотелось бы чего-то получше.