*! Exercise 4.2.2: If L is a language, and a is a symbol, then L/a, the quotient
ID: 3869747 • Letter: #
Question
*! Exercise 4.2.2: If L is a language, and a is a symbol, then L/a, the quotient of L and a, is the set of strings w such that wa is in L. For example, if L = {a, aab, baa), then LJa = {e, ba). Prove that if L is regular, so is L/a. Hint: Start with a DFA for L and consider the set of accepting states. ! Exercise 4.2.3: If L is a language, and a is a symbol, then aL is the set of strings w such that aw is in L. For example, if L = {a, aab, baa}, then aL = fe, ab). Prove that if L is regular, so is aL. Hint: Remember that the regular languages are closed under reversal and under the quotient operation of Exercise 4.2.2.Explanation / Answer
4.2.2)
Let m be the DFA of L. Let F be the final states of m. Let us consider all the transition functions which lead to the final states, let us call them T'. Out of T', now to construct L/a, we only retain the transition functions which has 'a' alphabet, and we remove the rest of the transition functions. Now in all of these transition functions which are left in T', they will be of the form (Si,Sj,a), now let us make Si's as final states and remove all the transition functions in T'.
We remove all the states which cannot be reached and the final DFA will be L/a.
4.2.3)
Let m be the DFA of L. Let m' be the DFA of reverse of L. Now repeat the same thing that has been done above and create a final DFA for L/a and let us call it m''. The final DFA for a/L is reverse of m''.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.