## Description

Q1.

- Use the construction in Theorem 4.1 to find an DFA that accept L(
*ab*a**) Ç L(*a*b*a*). - [5, Optional] Give the regular expression for the above language in 1) that is accepted by your DFA.

Q2. The ** complementary or (cor) **of two sets L

_{1}and L

_{2}is defined as

cor(L_{1}, L_{2}) = {*w* | *w* ÏL_{1} or *w* Ï L_{2}, }.

Show that the family of regular languages is ** closed **under

*cor.*Q3. The family of regular languages are closed under arbitrary ** homomorphism**.

Prove or disprove h(L_{1} Ç L_{2}) =h(L_{1}) Ç h(L_{2}) is a regular language where L_{1} and L_{2} are regular.

Q4. Let L_{1} = {L(*b***abb**) and L_{2 }= L(*bab**). Find the ** right quotient** of L

_{1}with L

_{2}, L

_{1}/L

_{2}.

- [5] Let M be a DFA s.t. L(M) = L(L
_{1}). By applying Thm. 4.4, construct a DFA M’ s.t. L(M’) = L_{1}/L - [5] Then, give a regular expression for L(M’) = L
_{1}/L_{2}.

Q5. If L is a regular language, prove that the language L_{2} = { *uv* | *u*Î L^{R} , *v* ÎL } is also regular.

Q6. The ** left quotient** of a regular language L

_{1}with respect to L

_{2}is defined as:

L_{2}/L_{1 }= { *y* | *x*Î L_{2} , *xy* ÎL_{1} }

Show that the family of regular languages is ** closed** under the

**with a regular language.**

*left quotient*Hint: Do NOT construct a DFA that accepts L_{2}/L_{1 }but use the definition of L_{2}/L_{1} and the closure

properties of regular language.

Q7. [10] Disprove that L_{1} = L_{1}L_{2}/L_{2 }for all languages L_{1 }and L_{2 }. Give a counter example.

Q8. [10] A language is said to be a ** palindrome** language if L = L

^{R}. (4.2-3)

Show that there exists an ** algorithm** for determining if a given regular language is a palindrome language.

Q9. [20] Pumping Lemma

- [10] Prove that the language L = {
*a*|^{n}b^{k}c^{n}*n*³ 0,*k*³*n*} is.*not regular* - [10, Optional] Prove that the language L = {
*w*|*n*(_{a}*w*) ¹*n*(_{b}*w*)} is.*not regular* - [10] Prove or disprove that L1 È L2 is not regular language if L1 and L2 are not regular languages.

Q10 [10, optional] The ** min** of a language L is defined as

** min**(L) = {

*w*ÎL | there is no

*u*ÎL,

*v*ÎS

^{+}, such that

*w*=

*uv*}.

Show that the family of regular languages is closed under the ** min** operation.