5, (10 points) In this problem we are going to construct one regular language ov

Question

5, (10 points) In this problem we are going to construct one regular language over alphabet 2 from another regular language over the alphabet L. First, let be any function that maps the empty string to the empty string f(e) to another function on the sets of strings over these alphabets . We can extend the function by applying the function to each character separately Here are some examples: . f* given by f : {a, b, c} U {} {0,1} U {e) where f(a) 0,f(b)-1, f(c)-e maps acó to 01. . f* given by f : {0,1} U {e) {0,1} U {} where f(1) = 1,f(0) = 1 maps the language from problem 2 to the language f"(B) {11 : 1-1} Now let f : 1 U {} 2U {} be a function where f() = . Prove that if L C 1 is a regular language then its image under f*, f*(L)-(f"(w): w L} 27, is a regular language in : Hint: show how, starting from a DFA for L, you can construct an NFA for f (L). You can use the theorem from class saying that if an NFA recognizes a language then it is regular. Created by Paint X

Explanation / Answer

The function f* described in the question is that of a homomorphic image of the function f. Let us see this with an example - let a function G be such that g(0)=hey and g(1)=chegg. Then g(0101)=heycheggheychegg. For such a function let it's image be g*. Then g*(0101)=cheggheychegghey. Now to prove that the image is also regular.

Proof:

1) From the question, we can assume that L is regular.

2) Then let M be the DFA that accepts it.

3) For each symbol, s, in the transition graph of M, label that same arc as g(s) in a generalised transition graph we aim to construct to show language defined by f* is also regular.

4) There is a path labelled w from q0 to some final state qf in the TG for M if and only if there is a path labelled f*(w) from q0 to qf in the GTG.

Therefore, if L is a reglular language, then it;s homomorphic image is also a regular language. Hence, the image of a function is closed.

--------------------------

Thank you.

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.