Timeline for Proving specific prefixes of regular languages are regular

6 events

when toggle format	what		by	license	comment
Dec 6, 2015 at 23:43	history	edited	Hendrik Jan	CC BY-SA 3.0	added n-square recurrence.
Dec 6, 2015 at 22:13	vote	accept	michbad
Dec 6, 2015 at 22:13	comment	added	michbad		I think I get it! The key thing I didn't realize was that the number of possible relations was finite, but now it makes sense. I'm accepting the answer, but please explain the second problem too, if you have the time.
Dec 6, 2015 at 22:01	history	edited	Hendrik Jan	CC BY-SA 3.0	quite detailed construction for the first problem
Dec 6, 2015 at 19:10	comment	added	michbad		Thank you for your answer! Unfortunately, I still don't fully understand, so could you please clarify: - I understand the meaning of E_l, and I see how the DFA could know that set for some fixed l, but how does it compute that relation "on the fly" for different values of l? What exactly do you mean by that set squared, and how does it relate to 2^n and n^2, instead of 2n you mentioned? - I looked at the proof here: cs.stackexchange.com/questions/34006/… but what should we say to argue that we can contruct such a set of final states?
Dec 6, 2015 at 1:38	history	answered	Hendrik Jan	CC BY-SA 3.0