(12 pts.) The order of a regular nonempty language L is defined to be the smallest integer k for which L"-L"+1 if there is such a k, and oo otherwise (a) Show that the order of L is finite if and only if there is an integer k so that LkL' and in this case the order of L is the smallest k such that Lk - L* Tip: Start with part (b) of this problem to gain some intuition on what order means Once you solved that, note that this part actually asks two questions that you need to answer: (1) order is finite iff there is an integer k such that Lk- L*, and (2) if the order is finite, then it is the smallest k for which L -L. To show (1) it will help if you first show that if the order to exist, then L must contain (maybe by using proof by contradiction), which implies Ln C Ln+1 for every natural number n, and then that Lk-Lk+1 implies Ln+1-Ln+2 for every integer n k. To show (2) think about what it means that the order is k. How can you use (1) to show this? Note: To show (1) you need to show both directions separately. (b) Find the order of the regular language A} U {aa)(aaa)', and justify it Tip: Give this language a name, and compute the first few of its powers (starting with Oth power). As every string in this language can contain only a's, to describe them it is enough to describe how many a's they have. Briefly explain what strings each power of the language has, and find the smallest k satisfying the definition. (12 pts.) The order of a regular nonempty language L is defined to be the smallest integer k for which L"-L"+1 if there is such a k, and oo otherwise (a) Show that the order of L is finite if and only if there is an integer k so that LkL' and in this case the order of L is the smallest k such that Lk - L* Tip: Start with part (b) of this problem to gain some intuition on what order means Once you solved that, note that this part actually asks two questions that you need to answer: (1) order is finite iff there is an integer k such that Lk- L*, and (2) if the order is finite, then it is the smallest k for which L -L. To show (1) it will help if you first show that if the order to exist, then L must contain (maybe by using proof by contradiction), which implies Ln C Ln+1 for every natural number n, and then that Lk-Lk+1 implies Ln+1-Ln+2 for every integer n k. To show (2) think about what it means that the order is k. How can you use (1) to show this? Note: To show (1) you need to show both directions separately. (b) Find the order of the regular language A} U {aa)(aaa)', and justify it Tip: Give this language a name, and compute the first few of its powers (starting with Oth power). As every string in this language can contain only a's, to describe them it is enough to describe how many a's they have. Briefly explain what strings each power of the language has, and find the smallest k satisfying the definition