COMS 331: Theory of Computing, Spring 2021 Homework Assignment 4
Due at 10:00PM, Wednesday, February 24, on Gradescope.
Problem 22. Call a string x ∈ {0, 1}∗ prefix-balanced if, for every prefix w of x, |#(0, w) − #(1, w)| ≤ 1.
Design a DFA M such that
L(M ) = {x ∈ {0, 1}∗ | x is prefix-balanced and #(0, x) = #(1, x)}.
Problem 23. Design a DFA M that decides the language
A = {x ∈ {0,1}∗ |#(1,x) is odd and (bnum(x) is a multiple of 2 or a multiple of 3)}.
Define a finite-state compressor (FSC) to be a 4-tuple
C = (Q,δ,ν,s),
where
• Q is a finite set of states;
• δ : Q × {0, 1} −→ Q is the transition function;
• ν:Q×{0,1}−→{0,1}∗ istheoutputfunction; • s ∈ Q is the start state.
Define the extended transition function δˆ : Q × {0, 1}∗ −→ Q as for DFAs. Define the output from state q ∈ Q on input string w ∈ {0, 1}∗ to be the string νˆ(q, w) defined by the recursion
ν(q,λ) = λ
ν(q, wb) = νˆ(q, w)ν(δˆ(q, w), b)
1
for all q ∈ Q, w ∈ {0,1}∗, and b ∈ {0,1}.
Finally, define the output of the FSC C on input w ∈ {0, 1}∗ to be the string
Example
C(w) = νˆ(s, w).
1/11
0/0, 1/10001
03 1/1001
1/101 0/λ
12 0/λ
0/λ
The diagram above denotes the FSC C = (Q, δ, ν, s), where
• Q = {0,1,2,3};
• δ(q,0)=(q+1)mod4forallq∈Q; • δ(q,1)=0forallq∈Q;
λ, ifq≤2 0, ifq=3
• ν(q,0)=
• ν(q,1)=10q1forallq∈Q.
Note that each transition arrow is labeled by b/y, where b is the input bit producing the transition and y is the output string produced by the transition.
Intuitively, an FSC compresses an input string w if |C(w)| is significantly less than |w|.
Problem 24. For the specific example FSC C above, give formulas for |C(0n)| and |C(1n)| in terms
of n. Intuitively, what kinds of strings does C compress?
Problem 25. For the specific example FSC C above, assume that C(w) = 00101. 2
(a) What are the possible values of δˆ(s, w)?
(b) For each of the states in (a), what is the value of w?
An FSC C = (Q, δ, ν,s) is information lossless (IL) if the function g : { 0 , 1 } ∗ −→ { 0 , 1 } ∗ × C
defined by
is one-to-one.
Problem 26.
g(w) = (C(w), δˆ(s, w))
(a) Explain why our example FSC is IL.
(b) Give an example of an FSC that is not IL.
Problem 27. Give an example of an IL FSC C such that |C(w)| < |w| holds for every string w ∈ {0,1}+.
Problem 28. Prove that, for every IL FSC C = (Q,δ,ν,s) and every n ∈ N, there is an input string w ∈ {0, 1}n such that |C(w)| ≥ n − log2 |Q|.
3