ITEC 420 2020fall ibarland

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

NDFSMs and regexps
hw05

• Due 2020-Oct-26 (Mon) 23:59.
• Reading: §§11.1– 11.7 (but not §11.4), and §12.1
• The Chapter 11 Exercises start on p. 178 + 13 = 191(pdf); the Chapter 12 Exercises start on p. 202 + 13 = 215(pdf).
• 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. 11.11.1 five strings not/in, parts (a),(d) only, and tasks (i),(ii),(iii) only.

   Note:

   • For full credit, give short-as-possible strings which are/aren't in the language.
   • Task (ii) should be whichever is fewer.
   • Task (iii) should have a close-paren before the comma.

2. 11.11.3 (S → 0S1|SS|10) Give both a parse-tree and a derivation of the strings.

   hint: Your parse tree for (b) can refer to the parse tree for (a) if you like.

3. 11.11.6 write a CFG for… parts a,b,k,m.

   hint for k: If you have two existing CFGs, it's easy to take their union: add a non-terminal that has one rule "generate anything from the first CFG", and one rule "generate anything from the second CFG".

   hint for m:

   • The # is just another character (which is handy here to demark the two parts of the string).
   • Recall the book's grammar for generating palindromes (with a center-mark (# in this case)); after all such palindromes are just a string concatenated to its reverse.
   • x is a substring of y is the same as y can be expressed as uxw, where u and w are any string.

4. 11.11.7 show ambiguity
5. 11.11.8 non-ambiguous arith-expr grammar, part (a)
6. Consider the language \( L =\{w\in\{a,b\}^*: \#_a(w) \text{ is even and } \#_b(w) \text{ is odd }\} \)
   Draw a DFSM for this language.

   hint: How many states do you need, to keep track of the parity of #a's? Hint: 2. Likewise for the #b's. To keep track of both simultaneously means 2x2 states.

   (Make sure your machine accepts aababba.)

   Create a regular grammar for this language, as follows:

   • For every state in your DFSM, have a corresponding non-terminal;
   • For every transition in your DFSM have a rule whose left-hand-side is the beginning state, and whose right-hand-side is one terminal and one non-terminal (the destination state);
   • For every final-state, make a rule whose right-hand-side is just ε.

   For your grammar, give a derivation of aababba. (That derivation should correspond to your DFSM's computation!).

   [stretch/challenge:] For a NDFSM M = (K,Σ,Δ,s,A), Give the formal specification of a regular grammar G = (V,Σ,R,S) such that L(M)=L(G).

   That is: specify what the grammar-alphabet V is, what the set of rules R is, and what the start-nonterminal S is.

   notation: Recall that if you want to build a set by looping over (say) all \(k\in K\) and union'ing the result, you can use the notation \[ \bigcup_{k\in K} \ldots .\]

7. 12.7.1, parts a,b,i,m.

   Note: These are the same languages as you wrote CFGs for in 11.11.6 — they just re-numbered that part k as part i, here.

---

8. [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