ITEC 420 2020fall ibarland

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

DFSMs
hw03

• Due 2020-Sep-11 (Fri) 23:59.
• Reading: §§5.1– 5.3 of the text.
• The problems from the Chapter 5 Exercises on pp.87–88 (pdf pp.102–103).
• You might find it more natural to complete 5.13.5 first.
• 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. Problem 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. Problem 5.13.2 (draw DFSMs), 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 NDFSM might be simpler!
3. Problem 5.13.2 (specify DSFMs), 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).
4. Problem 5.13.3 (RPS-win-by-2), part b.
   • Let ^R_P be one element of Σ, denoting player-A playing Rock and player-B playing Paper. That is, ^R_P is considered one input-character, even though it takes more than one keystroke to type.

     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 Σ.

   • 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 doesn't change who the winner is.

   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.

5. Problem 5.13.4 (simple property).
   Give your answer as (an exceedingly short bit of) math, involving some components of the five-tuple ⟨K, Σ, δ, s, A⟩ that defines a FSM.
6. Problem 5.13.5 (certain strings in the DFSMNDFSM's language?)

   clarification: The diagram is a bit poorly drawn, with the arrows’ labels all shifted to the right a bit. So from the upper-right state, input a leads either back to itself or down to the lower-right; similarly input b leads to the lower-left, not down to the lower-right.

7. [optional/0pts] Any informal feedback on this assignment?
   • Were there some problems which felt like busywork, w/o even giving a moment of "aha!" or a sense of satisfaction?
   • Were there some problems that really made a concept click?
   • Were there problems that felt unclear or ill-defined in parts?
   • Were some hints/extra-explanations more distracting/confusing than they were helpful?
   • Specific phrasing/typesetting suggestions welcome.

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