Description
One: Write formal descriptions using set notation for the following sets of strings
over the alphabet Σ = { 0, 1 }. It would be easy to just put the English
description in {}’s. Can you write it with fewer/no English words to make it
more mathematically precise?
a. La = All strings over Σ that change from one symbol to the other at most once
as you read the string
b. Lb = All strings over Σ that begin and end with the same symbol
Did you consider all the “corner cases”?
Two: Let Σ={ a, b, c, 0, 1 }. Let A be the set {a, b, c} and let B be the set {0, 1};
and let La and Lb be as in the previous problem.
a. List the elements of the Cartesian Product B x (La ∩ {strings of length 3})
b. List the elements of the power set P (B)
c. What is the cardinality of the power set P (A) ?
d. Postponed to next week: List the elements of the language concatenation:
B • (Lb ∩ {strings of length ≤ 2})
e. Postponed to next week: What is the language concatenation B • {} ?
f. What is the Cartesian Product {} x La ?
g. What is the Cartesian Product {ε} x A ?
2
Three: Consider the following two definitions of a rooted undirected tree:
Structural:
A rooted tree of height n (n≥0) edges is a connected undirected graph
without cycles where one node is designated as the root; and the longest
path from the root to any node is of length n edges. (There could be more
than one such path of length n.)
Recursive:
A rooted tree of height 0 edges is a graph with one node (the root) and no
edges.
A rooted tree of height n > 0 edges is a graph consisting of:
The root node,
One rooted sub-tree of height n-1,
Zero or more additional rooted sub-trees of height ≤ n-1, and
For each sub-tree there is one edge between the root of the subtree and the root of the tree.
All sub-trees are disjoint from each other.
Prove that these two definitions are equivalent. (You may want to use
induction for at least one direction of the proof.)
Inspired by Sipser Exercises: p 84:
Four: Show a fully specified DFA that recognizes the following language over the
alphabet, Σ = {a, b, c}. Specify the DFA transition function as a fully specified
state diagram, i.e., a labeled digraph as we did in class and similar to the ones
below. Be sure to clearly indicate your initial state and Accepting states.
Lfour = { w ∈ Σ
+ | w begins and ends with c }
Can you do this with 4 states?
Five: Show a fully specified DFA Give a formal definition using the 5-tuple notation for a
DFA that recognizes the following language over the alphabet, Σ = {0, 1}. Specify
the DFA transition function δusing a fully specified state diagram function table.
Be sure to clearly indicate your initial state and Accepting states.
Lfive = { w ∈ Σ* | the number of 1’s in w is evenly divisible by three }
Six: Postponed to next week: Consider the two DFAs M1 & M2 (Fig. 1.6 on p. 36 & Fig.
1.8 on p. 37, respectively of Sipser) and reproduced below for convenience. What
is the language concatenation L(M1) • L (M2) ? I.e., give a simple English
description of this language.
3
Instead: Briefly describe in English the language over ∑ = { a, b } accepted by this DFA:
eof