Regular problems to be turned in) : 1. Problem 1.34 in Sipser. (Take a look at 1.33 in Sisper to familiarize yourself wi

[answerhappygod]

Regular Problems To Be Turned In 1 Problem 1 34 In Sipser Take A Look At 1 33 In Sisper To Familiarize Yourself Wi 1 (43.19 KiB) Viewed 34 times

Regular problems to be turned in) : 1. Problem 1.34 in Sipser. (Take a look at 1.33 in Sisper to familiarize yourself with the unusual alphabet in this problem.) a. Provide a DFA M such that L(M)=D, and provide an English explanation of how it works (that is, what each state represents). b. Prove (by induction on the length of the input string) that your DFA accepts the correct inputs (and only the correct inputs). Hint: your explanation in part a) should provide the precise statements that you need to show by induction. For example, you could show by induction on w that (qo, w) —*M(q0, £) iff the top row of w is equal to the bottom row of w. You would also need to prove at least one other statement in your proof by induction.