ITEC 420 2021fall ibarland

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

NFAs and regexps
hw03

• Due 2021-Oct-07 (Thu) at class-time.
• Reading: §§5.4– 5.6 and §§6.1– 6.3.
• The Chapter 5 Exercises start on p.87 (pdf pp.102); the Chapter 6 Exercises start on pp.109 (pdf pp.124).
• Please put your solutions in order and clearly label each with the problem number.
• Submit a .pdf, containing any pictures and handwritten work. 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. revisit Exercise 5.13.2 (draw NFAs), parts c,j only. Give your answer as a drawing of a non-deterministic FSM.
   • For (c), 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¹.
2. revisit Exercise 5.13.2 (specify NDSFMs), part j only.
   This time, specify your answer formally (in math) for a non-deterministic FSM. Recall that for a NFA, the transition-relation Δ is expressed as a 3-tuple in K×Σ×K.
3. Exercise 5.13.9a, with one change: Add a loop transition from state q1 to itself on the symbol 0.
   Your answer should be similar to what we did in class and it should show the following:
   1. The original NDFA in table form: Your table will have a row for each state q, and it will have 4 columns: q, eps(q) (which will be a helper-column for the next table), Δ(q, 0), Δ(q, 1), Remember that eps(q) is all states that can be reached from a state q via ε-transitions (i.e. without consuming any input). That includes taking multiple ε-transitions, as well as zero (so eps(q) always includes q itself).

   2. Your DFA's table will have a row for each (reachable) DFA state Q (i.e. each set of NFA states), and 4 columns: Q, eps(Q), δ(eps(Q),0), and δ(eps(Q),1). The column eps(Q) is a helper for the other two columns; it builds on (extends) the previous table's eps(q) column.

      When creating this table,

      • Please build the rows in a breadth-first fashion as we did in class/book: that is, as soon as a new state is entered in one of the δ columns, enter that state as another row.
      • When writing a set-of-states, you can omit curly-brackets and commas (e.g. 273 for {2,3,7}), and list them in any order. (The example in the slides did this too.)

   3. A diagram of the resulting DFA. Be sure to indicate the accept-states.

   Hint: Your DFA will end up having fewer than 6 states.

   Hint: When you are done — or even as you are creating your DFA — you can double-check your answer by verifying some specific strings are either accepted by both machines, or rejected by both. I checked mine with: ε, 0, 1, 10, 11, 0*, 0(10)*, 011.

4. Slide 100 of the Ch05ab-NDFSM notes introduced the idea of a Markov Chain, and Slide 101 gave a formal definition, along with a constraint: the formula \(\forall k \in K, \sum_{q \in K}\Delta(k,q) = 1\) which (we discussed) means that the probability on all outgoing edges must sum to 1.

   Answer the following question about the formula \( \exists k \in K, \sum_{q \in K}\Delta(q,k) \le 1 \) (note the different order of the arguments to Δ).

   1. Does this formula hold for the diagram in the notes (Bull/Bear/Stagnant markets)?
   2. Must this formula hold for all Markov Chains, the way the first does?
   3. If not: Must this formula never hold for any Markov Chain?
   4. Give an english description of what that formula means.

5. For the following, indicate whether or not it's true. If so, describe the language in English; if not, give a string witnessing the difference². (For full credit, give a shortest such string.)
   1. T / F : L((a*b*)*) = L(a*b*)?
   2. T / F : L((a*b*)*) = L(a∪ b)*?
   3. T / F : L(aa*b|b) = L(a?a*?b) Here we're using standard programming-language regexp notation, with | instead of ∪, and ? to mean optional.
6. Exercise 6.5.5. If you like, you may change the 4 to 3. (You may use the book's regular-expression language, or standard programming regular-expressions without curly-brackets.)
7. Exercise Exercise 6.5.6.
8. Exercise Exercise 6.5.13a-c.
9. In the lecture slides for Chpt. 6, complete the definitions for K₀, A₀, and Δ₀ on slide 51 (FSM for Concatenation of regular expressions).
   Your answer will be similar to the answers on slides 50 and 52 (FSMs for the Union and Kleene Star of regular expressions). Recall that this section of the notes was how to construct a FSM equivalent to any regular expression, based on the definition of regular expressions (8 variants). In lecture we discussed the intuition for all cases, but didn't formalize it for that one slide.
10. Extra credit: Exercise 6.5.9.
11. [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