задача по алгебре(формальным языкам)

valds75

Дан конечный алфавит X и регулярные языки L1,L2 в алфавите X, причем L2\in L1.
Задано сюрьективное отображение f:L1\rightarrow L2, причем f(a)=f(f(a и длина слова f(a)<=длины слова a.
Обозначим M={(a,f(a | a\in L1}.
Вопрос: всегда ли М будет регулярным языком? т.е можно ли задать множество М конечным графом(автоматом).

valds75

Up

Sanych

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

valds75

Спасибо! Да, надо наложить более сильные условия на M.
Оставить комментарий
Имя или ник:
Комментарий: