Regular Languages and Model Theory 6: The Myhill-Nerode Theorem
Вставка
- Опубліковано 16 жов 2024
- The Myhill-Nerode Theorem provides us with an abstract way of reasoning about what information an automaton needs to keep track of, allowing us to both minimize the memory usage of our automata and determine what languages are regular: what languages can be recognized if we only have the ability to keep track of finite amounts of information.
Public Domain image of an equivalence relation from Wikimedia Commons: commons.wikime...
If you have questions or something didn't make sense to you, please let me know in the comments below.
dude, your videos are EXACTLY what i've been looking for. an abstract algebra approach to something with graphs or computability or really just something outside of the normal rings and groups. please please please keep it up, especially the heavy pure mathematics in computer science!!
Excellent, Thomas! This video finally explained me what the nature of the Myhill-Nerode Theorem and how is it related to minimization and regularity of the languages The fact that equivalence between words just means that the words have same futures is the most important idea of the video for me. Thank you!
A very clear explanation. Some minor drawback - the picture is not synchronized with the audio
Perfectly explained. Tnq so much
Good video! Really helped me understand the concept
Very nice tutorial👍
Awesome video!!
Thank you so much
16:00 “THE minimal FSA” is it ever possible to have two different minimal FSA recognizing the same language?
The minimal automaton is unique up to isomorphism! If two automata are equivalent, each reachable state of one has to be "Myhill-Nerode equivalent" (have the same future) to a state of the other. If there's only one state for each Myhill-Nerode equivalence class, this matching forms an isomorphism between the two automata.
@@trkern Thanks!