ITEC 420  Homework Assignments
Fall 2017
Updates  Last modified
 2017 Sep 28 02:23:30 PM: Updated Homework 5
 2017 Sep 22 08:50:42 AM: Updated Homework 4
 2017 Sep 14 03:15:10 PM: Updated Homework 3
 2017 Sep 11 10:22:43 AM: Extended HW 2 from class to 4:00 p.m.
 2017 Sep 05 01:56:31 PM: Updated colors for HW 1a and 9
 Updated Homework 1 for Fall 17
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:
 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?]
 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. ]
 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.
 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))\}$$
 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:
 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.
 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 ... " )
 Prove that the set multiples of 3 (ie ..., 6, 3, 0, 3, 6, ...) are countable.
 Answer in 5 or fewer symbols: $2^{60} \times 2^{4} = $
 Answer in 5 or fewer symbols: How many distinct numbers can be represented with 64 bits?
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:
 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 5tuple that defines the machine.
First, make the following three changes in the machine:
 State 2 should NOT be an accept state.
 State 5 should NOT be an accept state.
 Define δ(6, b) = 5
 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.
 Using the machine (as modified above) shown in problem 5.1,
give a clear English description of the language accepted by the machine.
 Draw a DFSM that accepts the language { w ∈ {a,b}* : w begins with ab}
 Draw a DFSM that accepts the language { w ∈ {a,b}* : w does NOT begin with ab}
 Draw a DFSM that accepts the language { w ∈ {a,b}* : w ≥ 2 and w has different first and last letters.}
 Draw a DFSM that accepts the language { w ∈ {a,b}* : w contains aa somewhere}
 Draw a complete DFSM that accepts the language {ε}. Assume the alphabet is {a,b}.
 Draw a complete DFSM that accepts the language {}. Assume the alphabet is {a,b}.
 What must be true about a machine (ie DFSM) that accepts ε? Answer in terms of the formal definition (ie 5tuple) 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:
 Give the lexicographic ordering of the concatenation of languages
L_{1} and L_{2}
(ie L_{1} L_{2})
where L_{1}={apple, pch, pr}
and L_{2}={ε, 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.
 Draw a DFSM for each of the following
languages, all of which are over Σ = {
a, b
}:
 {ε,
a
}
 Σ*  {ε} [That is, all strings except the empty string]
 Draw a NDFSM that accepts the language
{ w ∈ {a,b}* : either w contains ba
or w contains both aa and bb
}
 Problem 5.9.a with one change: Add a loop transition
from state q_{1} to itself on the symbol zero (0).
Your answer should be similar to what we did in class and it
should show the following:

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).

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.
 a diagram of the resulting DFA.
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:
 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.
 Using the grammar from Exercise 11.3,
 give a leftmost derivation of the string
00 0101 1011
.
(Spaces are added to ease reading; they are not part of the string.)
 give a parse tree for the string in part a
 Give a CFG for the language $\{w\in\{a,b\}^*: w=w^R\}$
 Give a CFG for the language $\{a^mb^n: m\le n \wedge nm \textrm{ is even}\}$
 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
.
 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 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.
 Exercise 12.5.a [Make sure that your solution is deterministic!]
 Show the top down parse of the string "
a * b + c
" using the
machine defined for the nonambiguous
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.
 Show the bottom up parse of the string "
a * b + c
" using the
machine defined for the nonambiguous
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.
Homework 7c
 Note: We are not doing this assignment in Fall 2016.
 Due Date:
Monday 11/4/13 or Wednesday 11/6/13, 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 from the Chapter 13 Exercises on pages 310 and 311:
 13.1.a
 13.1.b
 13.1.d
 13.1.g
 Hints:
 In 13.1.{a,b,d,g}, there is at least one from each category.
 To show that a language is regular, use the regular techniques (pun intended);
to show that a language is not CF, use the regular pumping theorem;
to show that a language is CF but not regular, use the regular
techniques for showing that a language is CF AND the regular pumping theorem.
In the previous sentence, the word "regular" is
used in both it's technical sense and its normal (ie regular), English sense.
 13.1.c: Think about this one, and we'll discuss it briefly in class.
Homework 09
 Due Date:
Wednesday 12/7/16, 4:00 p.m.
Monday 12/5/16, 4:00 p.m.
(Assuming that we get through the material this week.)
Late assignments not accepted.
 This is (probably) the final homework for Fall 2016!
 Please make sure that you number all problems (eg 1.1, 1.2) and put them in order.

The problems are from the Chapters 20 and 21 Exercises on page
446  447 and 483:
 20.9
 21.1.a
 21.1.b
 21.1.c
 21.1.k
 For Exercise 20.9 make sure that you look at the Printing subroutine
P that is described in
Section 20.5.1 and in Exercise 8.

For problems 21.1.{1,b,c,k} you can simply justify, rather than prove, your
answers.
In other words, briefly explain what makes you think that the
language falls into its category.
Of these 4 languages at least one is in each of the three
categories, and thus one category contains exactly two of the languages.