- Если каждый класс эквивалентности RL является регулярным языком, то RL содержит класс бесконечной эквивалентности
Рассмотрим язык 0 ^ (2 ^ n) для n> = 0: 0, 00, 0000,…. Каждая отдельная строка в этом языке различима: каждый класс эквивалентности состоит из одной строки. Конечные языки всегда регулярны. Следовательно, у нас есть каждый класс эквивалентности RL как обычный язык, но ни один из классов эквивалентности RL не является бесконечным. Следовательно, требование является ложным, поскольку было опровергнуто контрпримером.
- Если L регулярный язык, то RL содержит класс бесконечной эквивалентности
Поскольку L регулярно, мы знаем, что в RL есть конечное число классов эквивалентности - действительно, мы знаем, что для каждого состояния в минимальном детерминированном конечном автомате для языка существует ровно один класс. Поскольку все бесконечно много строк в алфавите должны принадлежать одному из этих классов эквивалентности, из этого следует, что хотя бы один из классов должен содержать бесконечно много этих строк. Предположим, что это не так; тогда классы эквивалентности 1, 2,…, p содержат только строки c [1], c [2],…, c [p]. Но тогда только строки c [1] + c [2] +… + c [p] находятся в классе эквивалентности. Это число конечно, поэтому мы должны пропустить некоторые строки. Таким образом, утверждение является правдивым и доказано противоречием.