Please answer all questions.

This question tests your understanding of how to translate a finite automaton into a regular expression. Consider DFA M = (Q, sigma, delta, q, F) such that Q = {q_1, q_2, q_3}, q = q_i, F = {q_1, q_3}, and delta is given by: Draw the state diagram for M, and then apply the construction of Lemma 1.60 to obtain a regular expression describing L (M). This question allows you to practice proving a language is non-regular via the Pumping Lemma. Using the Pumping Lemma (Theorem 1.70), give formal proofs that the following languages are not regular: L = {www | w element {0, 1}*}. L = {1^n 0^m 1^n | m, n greaterthanorequalto 0}. L = {x | x 6 {0, 1}* is not a palindrome}. Recall a palindrome is a string that looks the same forwards and backwards. Examples of palindromes are "madam" and "racecar