5.2.2 Prove by induction that if w is any string of a's and b's and contain k a's, where k is positive even number, then w is in the language (b*ab*ab*)*. Hint( start with k =2 and show that P(k) implies P(k+2)

5.4.3 Find a general formula for (S+T)^n where S and T are arbitrary regular expression over a one letter alphabet and n is an arbitrary natural . Prove by induction on n that your formula is correct. Repeat for (S+T+U)^n, also over a one letter alphabet

14.1.1 Build a DFA that input a binary string and accept it if and only if the natural it represents in binary notation is divisible by three. Describe it formally and determine d*(s, 01110) where s is your start state

14.1.3 Suppose that M1 and M2 are two DFA with the same input alphabet. Define the product DFA of M1 x M2 as follow. The state set is the direct product S1 x S2, the set of ordered pairs with s1 ? S1 and s2 ? S2. The start state is the pair and the final state set is F1 x F2. The new transition function take a state and a letter a to . Prove that the product DFA decides the language L(M1) n L(M2)

14.2.4 The string in {a,....,z}* is said to be panalphabetic if it contains at least one occurrence of each letter. Example of panalphabetic string

thequickbrownfoxjumpsoverthelazydog

jackdawslovemybigsphinxofquartz

Is the language of panalphabetic strings decidable by a DFA? Prove your answer

14.3.1 Describe the L-equivalence classes for the language of panalphabetic string from Problem 14.2.4.