Задан язык L содержащийся в X (X - множество всевозможных слов на каком-то конкретном алфавите ). Пусть f - гомоморфизм моноида X на какой-нибудь конечный моноид М, причем f удовлетворяет условию
для любых p,q принадлежащих Х: Если р принадлежит L, а q непринадлежит L, то f(p) не равно f(q).
Построить конечный автомат разпознающий L.
|