Page 1 of 1
Regular problems to be turned in) : 1. Problem 1.34 in Sipser. (Take a look at 1.33 in Sisper to familiarize yourself wi
Posted: Tue Apr 12, 2022 10:19 am
by 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 36 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.