ITEC 420 2021fall ibarland

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

CFGs and PDAs
hw04

• Due 2020-Nov-02Oct-26 (Tue) 11:00.
• Reading: §§11.1– 11.7 (but not §11.4), and §12.1
• The Chapter 11 Exercises start on p.178+15=193(pdf); the Chapter 12 Exercises start on p.202+15=217(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. Exercise 11.11.1 five strings not/in, parts (a),(d) only, and tasks (i),(ii),(iii) only.
2. Exercise 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. Exercise 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 (that is, 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.
   • Modifying the book's grammar for palindromes so that its center is not just #, but # followed by any string. That'll get two of the three phases to the right of the #.

4. Exercise 11.11.7 show ambiguity. Additionally: For this string, how many more parse trees are there (if any)?
5. Exercise 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!).
7. Let's generalize the previous problem: For any 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 .\]

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

   Give your answers as drawings.

---

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