In this question you will show that DFAs and NFAs are extremely limited as computing devices. They cannot even compute multiplication and iterated exponentiation (although it is easy to compute each of these on a general-purpose computer).

5. (10 Points) In this question you will show that DFAs and NFAs are extremely limited as computing devices. They cannot even compute multiplication and iterated exponen- tiation (although it is easy to compute each of these on a general-purpose computer (a) Let -{a,b,c} and consider the task of multiplication encoded in the language _ {anbenk : n 0, K 0}. Prove that L is not regular using the pumping emma. (b) Let f(n) denote iterated exponentiation with base 2. Formally, it is defined as follows ifn=0 2f(n-) if n 2 1 2 For your intuition, consider f(1) - 2, f(2) -22, f (3) - 222, f(4) - 222" , and so on. In words, f(n) is a tower of height n of powers of 2. (b.1) Prove by induction that 2" 2 2n and argue that it implies f(m+1) 2 2f(m) (b.2) Prove by induction that f(n) > n (b3) Let {a): Prove that L {af(n) : n-0} is not regular using the pumping lemma Hint: you may structure your proof similar to the proof of (a" : n 20} being not regular from lectures and use (b.1) and (b.2) 5. (10 Points) In this question you will show that DFAs and NFAs are extremely limited as computing devices. They cannot even compute multiplication and iterated exponen- tiation (although it is easy to compute each of these on a general-purpose computer (a) Let -{a,b,c} and consider the task of multiplication encoded in the language _ {anbenk : n 0, K 0}. Prove that L is not regular using the pumping emma. (b) Let f(n) denote iterated exponentiation with base 2. Formally, it is defined as follows ifn=0 2f(n-) if n 2 1 2 For your intuition, consider f(1) - 2, f(2) -22, f (3) - 222, f(4) - 222" , and so on. In words, f(n) is a tower of height n of powers of 2. (b.1) Prove by induction that 2" 2 2n and argue that it implies f(m+1) 2 2f(m) (b.2) Prove by induction that f(n) > n (b3) Let {a): Prove that L {af(n) : n-0} is not regular using the pumping lemma Hint: you may structure your proof similar to the proof of (a" : n 20} being not regular from lectures and use (b.1) and (b.2)