ITEC 420 2020fall ibarland

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

hw02

• Due 2020-Sep-01 (Wed) at the start of class.
• Reading: §§2.1– 2.3 of the text.
• The problems mostly from the Chapter 2 Exercises on pp.14–15 (pdf pp.29–30).
• Please put your solutions in order and clearly label each with the problem number.

1. Problem 2.3.2.
2. Let L₁ = {apple, pear} and L₂ = {pie, cake, ε}. List the elements of L₁L₂ in lexicographic order¹. This is just the book's #2.3.3 made a bit less-busy-ish.
3. Give two (small) languages L₁,L₂ such that |L₁L₂| < |L₁|·|L₂|. Extra credit if you have the smallest possible |L₁ ∪ L2|.
4. 2.3.6. Do not simply restate the math; instead describe, in English, the strings in each language so that an ITEC friend could understand. None of your answers should include the word prefix.

   For convenience: Your answers may take as understood that the underlying alphabet is Σ = {a,b} — you don't need to repeat that.

5. 2.3.8, only parts c–e.

   definition: If L is a language, then we define L* as the language whose strings are each 0-or-more concatenations of strings found in L. For example, if L = {hi,bye}, then hihibyehi is one element (of many) in L*.

This homework based on Dr. Okie's homework and (of course) the textbook.

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