Борясь, чтобы понять Myhill-Nerode

Question

Я думаю, что знаю лемму о перекачке, и мне сказали, что Myhill-Nerode - очень элегантный способ показать, что что-то регулярно или не регулярно. Но у меня с этим много проблем. Возьмите это, например:

= {0 ^к, к = 2 ^п, п> 1}

Мой язык является повторением 0 до длины, что это сила 2. I хотите использовать Myhill-Nerode, чтобы показать, что это либо регулярное, либо не регулярное. Является ли это возможным?

Я знаю, как настроить это, чтобы он напоминал другие доказательства, относящиеся к Myhill-Nerode, но я не очень понимаю концепцию эквивалентности.

Я мог бы сказать, что у меня есть некоторые и где ≠ и оба имеют вид 2 ^ч и , я затем определить , и так, что:

= 0 ^J/2

= 0 ^р/2

= 0 ^J/2

Где = 0 ^{J/2 J/2} = 0 ^J в моем языке, поскольку имеет вид 2 ^п однако = 0 ^{р/2 J/2} не гарантируется на моем языке для каждого р и у, так как ≠

Answer 1

Учитывая языки L, две строки и, v 2 L являются эквивалентными, если для всех строк ш принадлежат сигмы * мы имеем, что ию принадлежит L тогда и только тогда VW принадлежит L

Рассмотрим множество {0 , 0^2,0^4,0^8 ....}, в этом случае для некоторых m и n 0^m и 0^n должны быть сопоставлены с одним и тем же классом эквивалентности, иначе были бы бесконечные классы эквивалентности, это нерегулярно по теореме Михилла-Нерода. Однако 0^m.0^m принадлежат L, но 0^n.0^m не будет .. Дело