Assignment #3: formal languages

CSC236 
Assignment #3: formal languages

The aim of this assignment is to give you some practice with formal languages, FSAs, and regular expressions.
Your assignment must be typed to produce a PDF document a3.pdf (hand-written submissions are not
acceptable). You may work on the assignment in groups of 1 or 2, and submit a single assignment for the
entire group on MarkUs
1. Let x 2 N. Prove that term(x) (below) terminates. Hint: Trace the values of x and y for a few di?erent
inputs, then devise a loop invariant that helps prove termination.
def term(x):
y = x**3
while y != 0:
x = x - 1
y = y - 3*x*x - 3*x - 1
2. Let ? = fa; bg, La = fa
k
j k 2 Ng, Lb = fb
j
j j 2 Ng, and L2 = fx 2 fa; bg

j jxj is eveng. Do not
draw the machines below. Specify them with the quintuple (Q; ? = fa; bg; ?; Q0; F), where transition
function ? is a table with symbols on the rows and states on the columns.
(a) Construct DFA Ma such that L(Ma) = La. Be sure to include all states, including dead states.
Devise a state invariant for Ma and use it to prove that Ma accepts La.
(b) Construct DFA Mb such that L(Mb) = Lb. Be sure to include all states, including dead states.
Devise a state invariant for Mb and use it to prove that Mb accepts Lb.
(c) Construct DFA M2 such that L(M2) = L2. Be sure to include all states, including dead states.
Devise a state invariant for M2 and use it to prove that M2 accepts L2.
(d) Construct DFA Majb such that L(Majb) = La [ Lb. Use the product construction from week 9
slides. Explain how you can use the proofs for Ma and Mb to establish that Majb accepts La [Lb.
(e) Construct DFA Majb even such that L(Majb even) = (La [ Lb) \ L2. Explain how you can use the
proofs for the preceding machine to establish that Majb even accepts (La [ Lb) \ L2.
3. Let ? = f0; 1; 2; 3; 4; 5; 6; 7; 8; 9g, L0 = fx 2 ?

j x represents a number equivalent to 0 mod 3 in base 10g,
L1 = fx 2 ?

j x represents a number equivalent to 1 mod 3 in base 10g, and L2 = fx 2 ?

j
x represents a number equivalent to 2 mod 3 in base 10g. Construct M0 that accepts L0 [ f"g, M1
that accepts L1 and M2 that accepts L2, being sure that each machine has exactly 3 states. Do not
draw your machines, specify them with a quintuple.
Now use the structure of your machines to explain why L0 = Rev(L0), L1 = Rev(L1), and L2 = Rev(L2)
1
4. Let RE be the set of regular expressions over the alphabet ? = f0; 1g. Use structural induction on
RE to prove:
(a)
8r 2 RE; 9r
0 2 RE; Rev(L(r)) = L(r
0
)
(b) Using the de?nition of Pre?x(L) in Exercise 11 at the end of Chapter 7:
8r 2 RE; 9r
0 2 RE;Pre?x(L(r)) = L(r
0
)
(c) If r 2 RE does not contain the Kleene star, then jL(r)j is ?nite.
5. Let ? = fa; b; cg and LR4 = fx 2 ?

j jxj = 4 ^ x = x
Rg. Prove that any DFA that accepts LR4 has at
least nine states, not including dead states. Hint: consider what happens if 2 distinct length-2 pre?xes
of strings in LR4 drive the machine to the same state. Generalize your result: what can you say about
a DFA that accepts LR = fx 2 ?

j x = x
Rg?
2