Assignment #3: formal languages Solution

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 # = f a; b g , L a = f a k j k 2 N g , L b = f b j j j 2 N g , and L 2 = f x 2 f a; b g # j j x j is even g . Do not
draw the machines below. Specify them with the quintuple ( Q; # = f a; b g ; #; Q 0 ; F ), where transition
function # is a table with symbols on the rows and states on the columns.
(a) Construct DFA M a such that L ( M a ) = L a . Be sure to include all states, including dead states.
Devise a state invariant for M a and use it to prove that M a accepts L a .
(b) Construct DFA M b such that L ( M b ) = L b . Be sure to include all states, including dead states.
Devise a state invariant for M b and use it to prove that M b accepts L b .
(c) Construct DFA M 2 such that L ( M 2 ) = L 2 . Be sure to include all states, including dead states.
Devise a state invariant for M 2 and use it to prove that M 2 accepts L 2 .
(d) Construct DFA M a j b such that L ( M a j b ) = L a [ L b . Use the product construction from week 9
slides. Explain how you can use the proofs for M a and M b to establish that M a j b accepts L a [ L b .
(e) Construct DFA M a j b even such that L ( M a j b even ) = ( L a [ L b ) \ L 2 . Explain how you can use the
proofs for the preceding machine to establish that M a j b even accepts ( L a [ L b ) \ L 2 .
3. Let # = f 0 ; 1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8 ; 9 g , L 0 = f x 2 # # j x represents a number equivalent to 0 mod 3 in base 10 g ,
L 1 = f x 2 # # j x represents a number equivalent to 1 mod 3 in base 10 g , and L 2 = f x 2 # # j
x represents a number equivalent to 2 mod 3 in base 10 g . Construct M 0 that accepts L 0 [ f " g , M 1
that accepts L 1 and M 2 that accepts L 2 , 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 L 0 = Rev ( L 0 ), L 1 = Rev ( L 1 ), and L 2 = Rev ( L 2 )
14. Let RE be the set of regular expressions over the alphabet # = f 0 ; 1 g . Use structural induction on
RE to prove:
(a)
8 r 2 RE ; 9 r 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:
8 r 2 RE ; 9 r 0 2 RE ; Pre x( L ( r )) = L ( r 0 )
(c) If r 2 RE does not contain the Kleene star, then j L ( r ) j is nite.
5. Let # = f a; b; c g and L R 4 = f x 2 # # j j x j = 4 ^ x = x R g . Prove that any DFA that accepts L R 4 has at
least nine states, not including dead states. Hint: consider what happens if 2 distinct length-2 pre xes
of strings in L R 4 drive the machine to the same state. Generalize your result: what can you say about
a DFA that accepts L R = f x 2 # # j x = x R g ?