Here we look at the Myhill-Nerode Equivalence Relation, which is another way of proving a language is not regular. Some languages cannot be shown to be regular using the pumping lemma, so we look at a "stronger" property, which is that if two different strings land in the same state, then anything read after either of them will also result in the same state. We use this on its head by considering any two different strings xz and yz that land in different states, then it must be that x and y themselves went to different states. If there are infinitely many such cases, this implies that the language cannot be regular.

If you like this content, please consider subscribing to my channel: [ Ссылка ]

▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.

свернуть