ITEC 420 2021fall ibarland

home—lectures—recipe—exams—hws—D2L—zoom (snow day)

DFAs
hw02

• Due 2021-Sep-17 (Fri) 23:59.
• Reading: §§5.1– 5.3 of the text.
• The problems from the Chapter 5 Exercises starting on p.87+15=102(pdf).
• Please put your solutions in order and clearly label each with the problem number.
• Submit a .pdf, containing any pictures. You are welcome to try to keep the file-size small by providing the lowest-resolution images, so long as I can still read all the transitions.

1. Exercise 5.13.1 (describe-the-machine's language).
   • The diagram's missing transtion should be δ(6,b)=5.
   • Have your answer complete the sentence:

     The language accepted by the machine is the set of all strings over {a,b} that start with                                                               , followed by                                                                                                                                                                               .

     You might, or might not, need to include further followed bys in the solution.

   hint: You should use the words even and/or odd, and might or might not need to include the phrases 0 or more or 1 or more.

   hint: My own solution has about 20 words filling in the blanks.

2. Using the machine from the previous problem:
   1. Give the computation determined by the string aabaa.

      hint: The computation consists of a sequence of six configurations, separated by the yields turnstile ⊢. Each configuration is an ordered pair: ⟨current-state, remaining-input⟩. The book's Example 5.2 has an example as its last paragraph (but omitting the ⊢s, sadly).

   2. State whether or not the string is accepted, and use the formal definitions of the machine and of accepting/rejecting a string (p.42+15=57(pdf) to justify your answer.

      hint: Your answer will begin with The string aabaa is/isn't accepted because….

3. Exercise 5.13.2 (draw DFAs), parts a,c,d,f,g,j. Give your answer as a drawing.
   • For (c),(d), ignore the no leading zeros requirement (so, e.g., you should accept 00100). But we will also consider the empty-string as denoting 0 (since it is how you'd write zero if you choose to not include any leading zeroes!). These conventions simplify the solution¹.
   • Be sure each state has |Σ| arrows leaving it, of course.
   • Be sure to use deterministic state machines — though you might note that writing a NDFA might be simpler!
4. Exercise 5.13.2 (specify DFAs), parts a,c. This time, specify your answer formally (in math), as in the second sentence of the book's Example 5.2 (pg 43 = 58-15).
5. Exercise 5.13.3 (RPS-win-by-2).
   • Be sure to follow the book's hint on (a), about each character describing the simultaneous action of both players. Use ^R_P as one element of Σ, denoting player-A playing Rock and player-B playing Paper (at the same time).

     convenience: If typing your transitions, you don't need to typeset (say) ^R_P; you can simply type it as RP and we'll understand it denotes a single character of Σ.

   • So |Σ| = 9.
   • I found it helpful to write a couple of strings in L_RPS as well strings corresponding to a loss-for-A and a string that didn't correspond to a legal match.
   • Modification: Instead of the overall winner being the first player to win two rounds, let's define it as the first player to be ahead by two. This makes the answer easier/smaller. On the other hand, games will last longer.
   • Clarification: If the players continue playing rounds after somebody wins, that is not a valid game.

   hint: I drew my answer with most states having three outgoing arrows, each of those arrow labeled with three elements of Σ.

   convenience: You may simply label an arrow Σ to denote that all inputs should follow that arrow.

6. 1. Give a DFA which accepts the language of strings starting with ba.
   2. Give a DFA which accepts the language of strings not starting with ba.

      hint: There is a no-brain solution, once you have solved part (a).

7. Draw a DFA which accepts the language \( \{ w \in \{a,b\}^* : w \textrm{ contains }{\tt aa}\textrm{ somewhere.} \} \)
8. Draw a DFA which accepts the language \( \{ w \in \{a,b\}^* : |w| ≥ 2 \textrm{ and } w \textrm{ has different first and last letters.} \} \)
9. Draw a DFA which accepts the language {ε}. Assume the alphabet is {a,b}. Be sure to include all transitions.
10. Draw a DFA which accepts the language {}. Assume the alphabet is {a,b}. Be sure to include all transitions.
11. Exercise 5.13.4 (simple property).

    hint: Your answer should be three characters long, using math notation that involves some components of the five-tuple ⟨K, Σ, δ, s, A⟩.

I strongly recommend drawing your machines by hand. (though you might well redraw your machine more neatly, once you have it figured out). But if you want to run your machine to see if it works, you may use a site like automatonsimulator.com/. Some of the not-quite-intuitive directions for that page:

• Be sure the button DFA is selected (near the upper-right), for this homework.
• Click "+" to add a state;
• click/drag a state's colored-square to create a transition
• step through with the "clock-arrow" icon,
• and when done stepping, click the "clock-stop" icon.
• Use the "accept" and "reject" boxes to store your unit-tests (cool!)
• You should save your machines; if you want to send me a link you should
  1. create a (very long) URL, and then
  2. use bit.ly to shorten it².

home—lectures—recipe—exams—hws—D2L—zoom (snow day)

This page licensed CC-BY 4.0 Ian Barland Page last generated

Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu