[General boards] [Fall 2018 courses] [Summer 2018 courses] [Winter 2018 courses] [Older or newer terms]

Prove L(NFA) = L(DFA) = L(RegExp)


Hi class,

For Question 5 of the August 2016 final exam (image below), we are asked to come up with a DFA and a regular expression that is equivalent to a given NFA, and we asked to rigorously justify our response using structural induction.

My question is: would it be considered adequate to give an argument along the lines of “my DFA is equivalent to the NFA because it was created using the proven-correct algorithm known as subset construction. Furthermore, the DFA is equivalent to the regular expression because … [state invariant, structural induction, yadda yadda ]”?

I’m mainly asking because I do not see a clear way to go from “this state invariant is correct” to “this DFA is equivalent to this NFA”, so it seems like we would need to take for granted either the equivalence of the NFA with the regular expression, or the equivalence of the NFA with the DFA.