Page 1 of 1
P14.8.9 (10) Formally prove the correctness of our construction for the star operator, as follows. Let N be a /-NFA cons
Posted: Mon May 02, 2022 4:58 pm
by answerhappygod
- P14 8 9 10 Formally Prove The Correctness Of Our Construction For The Star Operator As Follows Let N Be A Nfa Cons 1 (39.57 KiB) Viewed 41 times
P14.8.9 (10) Formally prove the correctness of our construction for the star operator, as follows. Let N be a /-NFA constructed for the regular expression a, and let N' be the one constructed for a*, with two new states and four new l-moves. Let L be the language of a. (a) By induction on all naturals t, prove that if w is any string in the language L', then there are w-paths from the start state of N' to both the original final state of N and to the final state of N'. (The path to N's final state is a useful inductive hypothesis.) (b) Prove, by induction on all paths from the start state of N' to either the original start state of N, the original final state of N, or the final state of N', that the string read on the path is in the language I*.