6. [10pt] A homomorphism is a function y: from one alphabet (E) to strings over
ID: 2258173 • Letter: 6
Question
6. [10pt] A homomorphism is a function y: from one alphabet (E) to strings over some other alphabet (T). One can extend p to operate on strings by defining Pls) = (81)(s2) . . .Plsn), where s = s1s2 . . . sn and each s/E . One can further extend to operate on languages by defining (L) = {o(w)I w E L), for any lan- guage L Prove, bv providing a formal construction, that the class of regular languages is closed under homomorphism. That is, given a DFA D that recognizes a language A and a homomorphism yo, construct a finite automaton M that recognizes (A). Is this machine M that you've constructed a DFA in every case? Explain.Explanation / Answer
Solution:
A homomorphism on alphabet is a function h : which we can extend to strings as h(a1 · · · ak) = h(a1)· · · h(ak). For any homomorphism h, prove that the set of all context-free languages over the alphabet {a, b} is closed under the function h, where h(L) = {h(w) | w L}.
If L1 and L2 are regular languages, then so are L1L2, L1L2, and L 1 . If L1 and L2 are regular, then there exists regular expressions r1 and r2 such that L1 = L(r1) and L2 = L(r2). By definition, r1 + r2, r1r2, and r 1 are regular expressions denoting the languages L1 L2, L1L2, and L 1 , respectively. Thus, closure under union, concatenation, and star-closure is immediate.
If L1 is a regular language, then so is L1. To show closure under complementation, let M = (Q, , , q0, F) be a DFA that accpets L1. Then the DFA Mˆ = (Q, , , q0, Q F) accepts L1. Remember that (q0, w) is defined for all w . Consequently either (q0, w) is a final state, in which case w L or (q0, w) Q F and w L1.
Definition
Suppose and are alphabets. Then a function h : is called a homomorphism. In words, a homomorphism is a substitution in which a single letter is replaced with a string. The domain of the function h is extended to strings in an obvious fashion; if w = a1a2 . . . an, then h(w) = h(a1)h(a2). . . h(an). If L is a language on , then its homomorphic image is defined as h(L) = {h(w) | w L}.
Example: Let = {a, b} and = {a, b, c} and define h by h(a) = ab, h(b) = bbc. Then h(aba) = abbbcab. The homomorphic image of L = {
Let h be a homomorphism. If L is a regular language, then its homomorphic image h(L) is also regular. The family of regular languages is therefore closed under arbitrary homomorphisms.
Closure properties of the family of regular languages Entry + means the language family is closed under the operation under consideration. Operation + · + + + + R + h +
***************************************************************************
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.