Что такое отношение эквивалентности Майхилла-Нерода?

Описание: Здесь мы рассмотрим отношение эквивалентности Майхилла-Нерода, которое является ещё одним способом доказательства нерегулярности языка. Регулярность некоторых языков невозможно доказать с помощью леммы о накачке, поэтому мы рассмотрим более «сильное» свойство: если две разные строки оказываются в одном и том же состоянии, то всё, что будет прочитано после любой из них, также приведёт к тому же состоянию. Мы используем это наоборот, рассматривая любые две разные строки xz и yz, оказывающиеся в разных состояниях, и тогда следует, что x и y сами перешли в разные состояния. Если таких случаев бесконечно много, это означает, что язык не может быть регулярным.

Сайт Easy Theory: https://www.easytheory.org
GoFundMe: https://www.gofundme.com/f/easy-theor...
Patreon:   / easytheoryyt  
Fourthwall: https://easy-theory-llc-shop.fourthwa...
Канал «Решение проблем»: ⁠ @easytheoryprobsolve

Если вам нравится этот контент, подпишитесь на мой канал:    / @easytheory