Отношения эквивалентности и классы
У меня есть пара проблем, которые я не знаю, как решить. Я знаю, что отношение эквивалентности - это набор отношений, который соответствует свойствам: рефлексивный, симметричный, антисимметричный и транзитивный.
1) Рассмотрим алфавит Σ = {a,b}. Для каких языков L отношение эквивалентности RI имеет ровно один класс эквивалентности?
2) Пусть L- язык (не обязательно регулярный) над алфавитом. Покажите, что если класс эквивалентности, содержащий пустую строку [ε], не равен {ε}, то он бесконечен.
3) Рассмотрим язык L над алфавитом Σ = {a, b}, описываемым как L = {x ∈ Σ: |na(x) = nb(x)}. Напомним, что na (x) = число a в x.
(1) Покажите, что если na (x) - nb (x) = na (y) - nb (y), то xRIy.
(2) Покажите, что если na (x) - nb (x) не = na (y) - nb (y), то x и y L-различимы.
(3) Опишите все классы эквивалентности RI.