I've seen this proof before and it never made sense to me. This merely shows that a DFA with n or less states which recognizes 0^n 1^n cannot exist, but it says nothing about DFAs with more than n states. I will take CS academics' word for it, but if someone were to ask me to repeat this proof, I would not be able to do it.
hello, thanks for the good videos they help alot. my question is why are we assuming from the beginning there exists a DFA with n states when we could as well assume there is a DFA with 2n states or n^2 states which will not guarantee us the repetition the proof is based on. this assumption seems too convenient for the proof so the answer will really help me understand. thanks !
I don't understand how you repeated "this part twice". Is that to say that the amount of zeros just made it so that "the repeat part" was visited twice?
@@EasyTheory Thank you. I also had a follow up question but I think I just understood it. The question was, how do we know that there are only n 1s while there being n+1 0s. I think the answer is because we assumed the string is in the language so that means that 1 doesn't have a repeat part because it lands in an accept state. Is that correct?
Next video! Closure properties of non-regular languages: ruclips.net/video/yXSisUjz9iQ/видео.html
I've seen this proof before and it never made sense to me. This merely shows that a DFA with n or less states which recognizes 0^n 1^n cannot exist, but it says nothing about DFAs with more than n states. I will take CS academics' word for it, but if someone were to ask me to repeat this proof, I would not be able to do it.
n is an arbitrary number, thus the proof applies to all natural numbers n, not just a fixed one
hello, thanks for the good videos they help alot.
my question is why are we assuming from the beginning there exists a DFA with n states when we could as well assume there is a DFA with 2n states or n^2 states which will not guarantee us the repetition the proof is based on.
this assumption seems too convenient for the proof so the answer will really help me understand.
thanks !
Question: does the word w=0^n1^n have 2n characters? like n zeros and n ones?
I don't understand how you repeated "this part twice". Is that to say that the amount of zeros just made it so that "the repeat part" was visited twice?
Yes. The string is long enough to guarantee a repetition in a (hypothetical) DFA for this language.
@@EasyTheory Thank you. I also had a follow up question but I think I just understood it. The question was, how do we know that there are only n 1s while there being n+1 0s. I think the answer is because we assumed the string is in the language so that means that 1 doesn't have a repeat part because it lands in an accept state. Is that correct?