(1) Write \graf code for a DFA M_1 that recognizes the @lang of strings over \S={a,b} such that the length of each string is congruent to 1 modulo 3. // (2) Use the @deftn of \d* to prove whether the string *{aba} is accepted by M_1. Show all of the steps of \d*. // (3) Write \graf code for a DFA M_2 that recognizes the @lang of strings over \S={a,b} that do not have 2 consecutive *{a}s. // (4) Modify the !{process from class} for taking the union of two DFAs to write \graf code for a DFA M_3 such that L(M_3)=L(M_1)\nL(M_2). What did you change about the process? Why does that work in general? // (5) Use words to describe L(M_3). // (6) Use words to describe ~{L(M_3)}. // (7) Write \graf code for a DFA M_4 that recognizes ~{L(M_3)}. How would you recognize the complement of the @lang recognized by a DFA in a generalized process? What makes your process work? // (8) Use the !{mathematical induction} and the definition (from \graf) of the *{reverse of a string} to prove the following: >< If v and w are strings over \S, then (v\.w)^{R}=w^{R}\.v^{R}.
(1) Write \graf code for a DFA M_1 that recognizes the @lang of strings over \S={a,b} such that the length of each string is congruent to 1 modulo 3. //
(2) Use the @deftn of \d* to prove whether the string *{aba} is accepted by M_1. Show all of the steps of \d*. //
(3) Write \graf code for a DFA M_2 that recognizes the @lang of strings over \S={a,b} that do not have 2 consecutive *{a}s. //
(4) Modify the !{process from class} for taking the union of two DFAs to write \graf code for a DFA M_3 such that L(M_3)=L(M_1)\nL(M_2). What did you change about the process? Why does that work in general? //
(5) Use words to describe L(M_3). //
(6) Use words to describe ~{L(M_3)}. //
(7) Write \graf code for a DFA M_4 that recognizes ~{L(M_3)}. How would you recognize the complement of the @lang recognized by a DFA in a generalized process? What makes your process work? //
(8) Use the !{mathematical induction} and the definition (from \graf) of the *{reverse of a string} to prove the following:
>< If v and w are strings over \S, then (v\.w)^{R}=w^{R}\.v^{R}.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
