ITEC 420 - Homework Assignments


Fall 2017


Updates - Last modified


DO NOT do the homeworks that have a red background!

They are from last semester.

The current homework is always in green.




Homework 1a
  • Due: Monday 9/4/17, by 4:00 p.m. Late assignments not accepted.
  • Make sure that you justify your answers, where appropriate
  • Please put your solutions in order and clearly label each with the problem number.

  • The problems are based on Appendix A of the text:
    1. Express the set A without using the cross product: A = {1, 2} x {a, b} x {d, e}. [Hint: What kinds of things are the elements of A?]
    2. Express the set B without using the cross product: B = {1, 2} x {a, b} x { }. [Hint: the last set in the cross product is empty. ]
    3. Draw a lattice that shows the proper subset relation among the 8 elements of the power set of {1,2,3}. In your lattice, if $P\subset Q$, with no proper subsets between them, then write Q somewhere above P and with a line from P to Q.
    4. Describe, in words, the set C [assume $\mathbb{N}$ is the set of natural numbers (ie the nonnegative integers)]: Your answer will start: C is the set of natural numbers x such that ... $$ C = \{x \in \mathbb{N} :\exists y \in \mathbb{N} (y \lt 12 \wedge (y+5 = x))\}$$
    5. List the elements, as a set, of the set C from the previous problem (your answer will look something like C = {19, 43, 55}.


Homework 1b
  • Due Wednesday 9/6/17, by 4:00 p.m.. Late assignments not accepted.
  • Make sure that you justify your answers.
  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

  • Some problems are based on Appendix A of the text:
    1. Define set $D=\{1, 4, 7, 10, 13, \dots\}$ where the dots represent numbers that follow the obvious pattern. Express this set in the form $D = \{x\in A : P(x) \}$ where $A$ is some set of numbers and $P(x)$ (eg the Naturals) is some property of $x$ (eg x is even). You answer will look like $\{x\in \dots : \dots \}$ where you fill in both sets of dots, as, for example, in problem 3 above.
    2. Express the set description in problem A.17.a (page 806) in English. Don't solve this problem: simply write out what the symbols mean in English (Your answer start: "The set of natural numbers ... " )
    3. Prove that the set multiples of 3 (ie ..., -6, -3, 0, 3, 6, ...) are countable.
    4. Answer in 5 or fewer symbols: $2^{60} \times 2^{4} = $
    5. Answer in 5 or fewer symbols: How many distinct numbers can be represented with 64 bits?


Homework 2
  • Due Date: Wednesday 9/13/17 at 4:00 p.m. Late assignments not accepted.

  • Make sure that you justify your answers.

  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

  • The problems are mostly from the Chapter 2 exercises, starting on page 19. The first problem is a modification of one from the text. The second problem is not in the text. The last ones are from the text.
    1. In problem 2.2 use English to describe the set of strings in the langauge L1L2. Your answer will be something "all strings with 0 or more a's ...". [Clarification: Do not do parts a, b, and c from the text. Instead, simply describe L1L2 in words.]
    2. Let L1 = {apple, pear} and L2 = {pie, cake, ε}. List the elements of L1L2 in lexicographic order.
    3. 2.6.a [N.B. Your simple English description should NOT simply restate the math; instead it should describe characteristics of strings in the language]
    4. 2.6.b [N.B. as above]
    5. 2.6.c [N.B. as above]]
    6. 2.8.b (Remember to prove your answer)
    7. 2.8.e (Remember to prove your answer)


Homework 3
  • Due Date: Wednesday 9/20/17, at 4:00. Late assignments not accepted.

  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

  • For these problems, you only need to justify your answers when the problem says to do so. Also, you are only required to refer to the formal definition in the first, second, and last problems.

  • The first three problems come from the Chapter 5 exercises on pages 121 and 122:
    1. After making the three changes listed below to the machine shown in problem 5.1, give the formal definition of the machine. In other words, give the 5-tuple that defines the machine. First, make the following three changes in the machine:
      1. State 2 should NOT be an accept state.
      2. State 5 should NOT be an accept state.
      3. Define δ(6, b) = 5

    2. Using the machine (as modified above) shown in problem 5.1, list the configurations in the computation determined by the string aabaa. State whether or not the string is accepted, and use the formal definition to justify your answer.

    3. Using the machine (as modified above) shown in problem 5.1, give a clear English description of the language accepted by the machine.

    4. Draw a DFSM that accepts the language { w ∈ {a,b}* : w begins with ab}
    5. Draw a DFSM that accepts the language { w ∈ {a,b}* : w does NOT begin with ab}
    6. Draw a DFSM that accepts the language { w ∈ {a,b}* : |w| ≥ 2 and w has different first and last letters.}
    7. Draw a DFSM that accepts the language { w ∈ {a,b}* : w contains aa somewhere}
    8. Draw a complete DFSM that accepts the language {ε}. Assume the alphabet is {a,b}.
    9. Draw a complete DFSM that accepts the language {}. Assume the alphabet is {a,b}.
    10. What must be true about a machine (ie DFSM) that accepts ε? Answer in terms of the formal definition (ie 5-tuple) that defines the language. Justify your answer.


Homework 4
  • Due Date: Wednesday 9/27/17 in class. Late assignments not accepted.

  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

  • No justification needed for this assignment. You can simply show your answers.

  • Some problems are from the Chapter 5 exercises on page 123:
    1. Give the lexicographic ordering of the concatenation of languages L1 and L2 (ie L1 L2) where L1={apple, pch, pr} and L2={ε, pi, juice}.
      • In case you're wondering, "pch", "pr", and "pi" are abbreviations for the words "peach", "pear", and "pie". You can enjoy thinking about peaches, pears, and pies while doing the assignment, but make sure that you use the abbreviations in your answer.
    2. Draw a DFSM for each of the following languages, all of which are over Σ = {a, b}:
      1. {ε, a}
      2. Σ* - {ε} [That is, all strings except the empty string]
    3. Draw a NDFSM that accepts the language { w ∈ {a,b}* : either w contains ba or w contains both aa and bb }
    4. Problem 5.9.a with one change: Add a loop transition from state q1 to itself on the symbol zero (0). Your answer should be similar to what we did in class and it should show the following:
      1. a table for the NDFA that shows, for each state q, the transitions from state q on each alphabet symbol and that also shows eps(q). Your table will have a row for each state q, and it will have 3 columns: one for Δ(q, 0), one for Δ(q, 1), and one for eps(q).
      2. a table that shows δ for the DFA (ie the transitions for all needed states and all alphabet symbols). Your table will have a row for each DFA state (ie set of NDFA states) and a column for each of the two input symbols. Hint: You do not have to show all possible DFA states, and your DFA will end up having fewer than 6 states.
      3. a diagram of the resulting DFA.


Homework 5
  • Due Date: Wednesday 10/4/17, in class. Late assignments not accepted.

  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

  • The problems are based on Chapter 6 and involve regular expressions (REs):
    1. Describe in English the languages generated by the following REs. Do not simply transcribe the RE; instead, find a concise English description of the strings in the language.
      1. (a (a ∪ bb)* )*
      2. ( (a ∪ b) a)*
    2. Give REs for each of the following languages over Σ = {a, b}:
      1. Strings containing exactly 2 b's or exactly three b's.
      2. Every string contains at least one double letter. Clarification: aaa, bbb, aaba are in the language, but a and aba are not.
      3. No string contains a double letter (ie neither aa nor bb is a substring).
      4. No string contains ab.
    3. Follow the algorithm for converting a RE to a FSM and convert b ∪ (ε ∪ b)* to a FSM. Make sure that you follow the algorithm precisely, showing any and all new epsilon transitions and new states.
    4. Do the following using the diagram below:
      1. Add an Φ (ie empty SET) transition between states 1 and 4.
      2. Use the algorithm discussed in class to rip state 2 and show the resulting machine. (Hint: make sure that you show the complete RE on ALL transitions.)




Homework 6
  • Due Date: Wednesday 10/18/17, in class. Late assignments not accepted.

  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

  • Some of the problems are from the Chapter 11 Exercises on pages 245 and 246:
    1. In Exercise 11.1 do parts i, ii, iii (but not iv) of a and c (but not b and d). [In other words, do a and c (parts i,ii,iii only). Do not do b, do not do d, and don't do any part iv.]
      • In parts i and ii, do 2 strings instead of 5.
      • In part ii, it should say "whichever is fewer".
      • In part iii, there is a right paren missing before the comma.
    2. Using the grammar from Exercise 11.3,
      1. give a leftmost derivation of the string 00 0101 1011. (Spaces are added to ease reading; they are not part of the string.)
      2. give a parse tree for the string in part a
    3. Give a CFG for the language $\{w\in\{a,b\}^*: w=w^R\}$
    4. Give a CFG for the language $\{a^mb^n: m\le n \wedge n-m \textrm{ is even}\}$
    5. Let G be the ambiguous grammar from Example 11.19 Example 11.4 (not Exercise 11.19 Exercise 11.4), except assume that productions produce the terminals {a, b, c, d} instead of id. Draw two different parse trees for the string a * b + c + d.
    6. Let G' be the unambiguous grammar from Example 11.19 (not Exercise 11.19), except assume that productions produce the terminals {a, b, c, d} instead of id. Give a leftmost derivation of the string a * b + c + d.



Homework 7a
  • Due Date: Monday 10/31/16 at 4:00 p.m.. Late assignments not accepted.

  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

  • The problems are from the Chapter 12 Exercises on pages 277 and 278:
    • 12.1.d [For this problem and 12.1.j, assume 0 ≤ m,n]
    • 12.1.j

    • 12.4.a
    • 12.4.b
    • 12.4.c


Homework 7b
  • Due Date: Wednesday 11/02/16 at 4:00 p.m.. Late assignments not accepted.

  • Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

    1. Exercise 12.5.a [Make sure that your solution is deterministic!]

    2. Show the top down parse of the string "a * b + c" using the machine defined for the non-ambiguous expression grammar, as defined in the powerpoint notes. Follow the format of the example using columns for transition, unread input, and stack. Use the same numbers for the rules as are given in the notes, and indicate which side of the stack is the top.

    3. Show the bottom up parse of the string "a * b + c" using the machine defined for the non-ambiguous expression grammar, as defined in the powerpoint notes. Follow the format of the example using columns for action, stack, unread input, and RM derivation. Use the same numbers for the rules as are given in the notes, and indicate which side of the stack is the top.