1 About This Assignment
This assignment can be completed by groups of up to three students and is due by 11:59 pm
on Friday, February 11. The instructions for submission of CPSC 331 assignments is available
for other general information about assignments, and these instructions should be followed for
this assignment.
Problems To Be Solved
- Let
Σ =
0
0
0
,
0
0
1
,
0
1
0
,
0
1
1
,
1
0
0
,
1
0
1
,
1
1
0
,
1
1
1
,
so that each symbol in Σ has the form
a
b
c
where a, b, c ∈ {0, 1}, and all eight symbols of this form are included.
Every string ω ∈ Σ
⋆
represents three nonnegative whole numbers αω, βω, γω ∈ N. In
particular
• If ω = λ, the empty string, then αω = αλ = 0, βω = βλ = 0, and γω = γλ = 0 as
well.
1
• If ω ∈ Σ
⋆
is a nonempty string with length n ≥ 1 — so that ω has the form
ω =
a0
b0
c0
a1
b1
c1
. . .
an−1
bn−1
cn−1
where ai
, bi
, ci ∈ {0, 1} for 0 ≤ i ≤ n − 1, then
αω =
nX−1
i=0
ai
· 2
i
, βω =
nX−1
i=0
bi
· 2
i
, and γω =
nX−1
i=0
ci
· 2
i
.
For example, if ω is the following string with length 4,
ω =
1
0
1
0
1
1
1
1
1
0
0
1
,
then
• a0 = 1, a1 = 0, a2 = 1 and a3 = 0, so that αω = 1 × 1 + 0 × 2 + 1 × 4 + 0 × 8 = 5.
• b0 = 0, b1 = 1, b2 = 1 and b3 = 0, so that βω = 0 × 1 + 1 × 2 + 1 × 4 + 0 × 8 = 6,
and
• c0 = 1, c1 = 1, c2 = 1 and c3 = 1, so that γω = 1 × 1 + 1 × 2 + 1 × 4 + 1 × 8 = 15.
Design a deterministic finite automaton M = (Q, Σ, δ, q0, F) for the language
LSum = {ω ∈ Σ
⋆
| αω = βω + γω}
and explain why your answer is correct. Your answer should include a description of the
set
Sq = {ω ∈ Σ
⋆
| δ
⋆
(q0, ω) = q}
for each of the states q ∈ Q that can help a reader to understand why M really does
have the language Lsum.
Hint: This problem is not as hard as it might seem — as long as you follow a reasonable
design process and think about what what you need to remember (about the digits or
bits already processed) when you are adding numbers together, by hand, yourself. - The reversal ω
R of a string ω ∈ Σ
⋆
is the string obtained by reversing the order of the
symbols in ω. That is, if
ω = σ1σ2 . . . σn
where n ≥ 0 and σ1, σ2, . . . , σn ∈ Σ, then
ω
R = σn . . . σ2σ1.
2
This can also be defined “inductively” as follows: For every string ω ∈ Σ
⋆
,
ω
R =
(
λ if ω = λ,
τ · µ
R if σ = µ · τ for µ ∈ Σ
⋆ and τ ∈ Σ.
The reversal L
R of a language L ⊆ Σ
⋆
is the set of reversals of the strings in L, that is,
L
R = {ω
R | ω ∈ L}.
Prove that (for every language L ⊆ Σ
⋆
) L is a regular language if and only if L
R is a
regular language. - Once again, let Σ be the alphabet considered in Question #1. It is possible to define
another three nonnegative integers ρω, µω and νω for every string ω
⋆
.
• If ω = λ, the empty string, then ρω = ρλ = 0, µω = µλ = 0, and νω = νλ = 0.
• If ω ∈ Σ
⋆
is a nonempty string with length n ≥ 1 — so that ω has the form
ω =
a0
b0
c0
a1
b1
c1
. . .
an−1
bn−1
cn−1
where ai
, bi
, ci ∈ {0, 1}, then
ρω =
nX−1
i=0
ai
· 2
n−1−i
, µω =
nX−1
i=0
bi
· 2
n−1−i
, and νω =
nX−1
i=0
ci
· 2
n−1−i
.
Consider the language
LRSum = {ω ∈ Σ
⋆
| ρω = µω + νω}.
If you study the above definitions carefully then you should be able to confirm the following.
• a0a1 . . . an−1 is a binary representation of the integer ρω (with the lowest-order bit
on the right, as usual);
• b0b1 . . . bn−1 is a binary representation of the integer µω (with the lowest order bit
on the right, as usual);
• c0c1 . . . cn−1 is a binary representation of the integer νω (with the lowest order bit
on the right, as usual).
Sample Solution