CSCI435 Home Assignment 3 Solved

35.00 $ 17.50 $

Click Category Button to View Your Next Assignment | Homework

You'll get a download link with a: . zip solution files instantly, after Payment


Rate this product


  • 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 L1 and L2 is defined as

cor(L1, L2) = {w | w ÏL1 or w Ï L2, }.

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(L1 Ç L2) =h(L1) Ç h(L2) is a regular language where L1 and L2 are regular.

Q4.  Let L1 = {L(b*abb*) and L2 = L(bab*).  Find the right quotient of L1 with L2, L1/L2.

  • [5] Let M be a DFA s.t. L(M) = L(L1). By applying Thm. 4.4, construct a DFA M’ s.t. L(M’) = L1/L
  • [5] Then, give a regular expression for L(M’) = L1/L2.

Q5.  If L is a regular language, prove that the language L2 = { uv | uÎ LR , v ÎL } is also regular.


Q6.  The left quotient of a regular language L1 with respect to L2 is defined as:

L2/L1 = { y | xÎ L2 , xy ÎL1 }

Show that the family of regular languages is closed under the left quotient with a regular language.

Hint: Do NOT construct a DFA that accepts L2/L1 but use the definition of L2/L1 and the closure

properties of regular language.


Q7. [10] Disprove that L1 = L1L2/L2 for all languages L1 and L2 .  Give a counter example.

Q8. [10] A language is said to be a palindrome language if L = LR.         (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 = {anbkcn | n ³ 0, k ³ n } is not regular.
  • [10, Optional] Prove that the language L = {w | na(w) ¹ nb(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.