Введение в схемы, автоматы и алгоритмы



             

Примеры неавтоматных языков - часть 3


Но этот язык не автоматный. Действительно, пусть
: {a, b, c}*
{0, 1 }* - это гомоморфизм, заданный как
(a)=0,
(b) = 1,
(c) =?. Тогда
(L8 \ L7) =
(L6) = L1 из примера 6.4. Так как язык L7 является автоматным, а L1 - нет, то и язык L8 не является автоматным.




Содержание  Назад  Вперед