A homomorphism on an alphabet is simply a function that gives a string for each symbol in that alphabet – for example, a homomorphism \( h \) on the binary alphabet might be defined so that \( h(0) = ba \) and \( h(1) = edc \).Homomorphisms can be extended to strings and languages in the straightforward way:- If \( s = s_1s_2s_3...s_n \), then \( h(s) = h(s_1) h(s_2) h(s_3)... h(s_n) \).- If \( L \) is a language then \( h(L) = \{ h(s) \mid s \text{ is in } L \} \).**Show that the class of context free languages is closed under homomorphism** – that is, that for any context free language \( L \), and any homomorphism \( h \) on its alphabet, \( h(L) \) defined as above is context free. Analogously to regular languages you can do this by constructing either a PDA or a context-free grammar.*HINT: If your proof is very long at all, you are doing more than you need to.*

The, answer has given below:In order to prove h(L) is regular given L is regular we will construct a regular expression for h(L). We will prove this fact by defining the homomorphism operation on Regular Expressions. Define h(R) where R is a regular express to be the regular expression obtained by replacing each letter a in R with h(a). i.e. if h(0) = ab and h(1) = cd and R = 0+1, then h(R) = ab + cd Now we will prove the fact that L(h(R)) = h(L(R)) for any regular expression R. Proof is by induction on the number of operations in R Base Cases: For R = , h(R) = , L(R) = {} Hence h(L(R)) = {} and L(h(R)) = L() = {}. For R = a, h(R) = h(a), L(R) = {a). Hence h(L(R)) = h({a}) = h(a) and L(h(R)) = L(h(a)) = h(a) Hence the claim is true for the base case. Induction Case: R = R1 R2, h(R) = h(R1) h(R2) h(L(R)) = h(L(R1) L(R2)) = h(L(R1)) h(L(R2)) Now by the Induction Hypothesis h(L(R1)) = L(h(R1)) and h(L(R1)) = L(h(R1)) Hence h(L(R)) = L(h(R1) h(R2)) = L(h(R)) Similarly this holds for union and kleene star. Hence L(h(R)) = h(L(R)) Now let R be such that L = L(R). Let R' = h(R). Then h(L) = L(R') Hence h(L) is regular. Hence proved.

Engineering

Computer Science

A homomorphism on an alphabet is simply a function that gives a string for each symbol in that alphabet – for example, a homomorphism h on the binary alphabet might be defined so that h(0) = ba and h(1) = edc. Homomorphisms can be extended to strings and languages in the straightforward way: • ifs = 5,525.Sn then h(s) = h(s:) h(s2) h(s)... h(s».). - IfL is a language then h(L) = { h(s) | s is in L }. Show that the class of context free languages is closed under homomorphism – that is, that fo any context free language L, and any homomorphism h on its alphabet, h(L) defined as above is context free. Analogously to regular languages you can do this by constructing either a PDA or context-free grammar.

A homomorphism on an alphabet is simply a function that gives a string for each symbol in that alphabet – for example, a homomorphism h on the binary alphabet might be defined so that h(0) = ba and h(1) = edc. Homomorphisms can be extended to strings and languages in the straightforward way: • ifs = 5,525.Sn then h(s) = h(s:) h(s2) h(s)... h(s».). - IfL is a language then h(L) = { h(s) | s is in L }. Show that the class of context free languages is closed under homomorphism – that is, that fo any context free language L, and any homomorphism h on its alphabet, h(L) defined as above is context free. Analogously to regular languages you can do this by constructing either a PDA or context-free grammar.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

Define multiFold which folds an element of MkType returning a tuple of type (a,b). You should define this as a right fold . multiFold:: MkType a b -> (c,d) -> (a -> c -> c) -> (b -> d -> d) -> (c,d)multiFold = undefined answer in haskell form. thank you.
on A language L is called slithy if it contains at least two strings and has the following property: For every two strings x, y in L such that |x|< lyl, the string obtained by taking the first letter of y and inserting it at the start of x is also in L. For example, if L contains aaa and baaba, then it must also contain the string baaa. Prove by contradiction that every slithy language contains two strings of the same length.
For each of the following languages LS {a, b}*, show that the elements of the infinite set {a"|n 2 0} are pairwise L-distinguishable. (a) L={a"ba²"|n 2 0}
For each of the following languages Ls {a, b}*, show that the elements of the infinite set {a"|n > 0} are pairwise L-distinguishable. (b) L={a'b' a*\k > i+ j}
For each of the following languages Ls {a, b}*, show that the elements of the infinite set {a"|n > 0} are pairwise L-distinguishable. (d) L= {a'b'\j is a multiple of i}
2. What is the TG corresponding to the language of strings, over alphabet {a, b}, that are composed exactly of odd repetition of the substring ab, i.e. sample strings of this language are ab, ababab, ababab, etc.
Not handwritten Given the language L denoted by r = (a+b)* . (aa*+b) and, ∑ = {a,b} and ∏ = {c,d,x} h(b) = xd, h(a) = cdx please provide the homomorphic image of the regular expression h(r)
Let language L over alphabet Σ = { a, b } be defined as L = { a'b* }, where i is a multiple of some given n and k is a multiple of some given m, all non- negative integers. In other words: L contains all strings consisting of: o A number of a's that is a multiple of n o followed by a number of b's that is a multiple of m. Lis Using a constructive method, show that for any given values of n and m,. regular.
Consider the language L of strings over the alphabet Σ = {a, b} which contain an equal number of a’s and b’s, and the set of b’s is consecutive in the string, e.g., ab, abba, aabb, abbbaa, aaabbbbbaa, etc. Note that ε ∈ L for completeness (0 number of a’s is equal to 0 number of b’s, which are also consecutive). Show that this language is context-free by giving a context-free grammar. Please make sure to test the answers onhttps://web.stanford.edu/class/archive/cs/cs103/cs103.1156/tools/cfg/
on A language L is called slithy if it contains at least two strings and has the following property: For every two strings x, y in L such that |x|< lyl, the string obtained by taking the first letter of y and inserting it at the start of x is also in L. For example, if L contains aaa and baaba, then it must also contain the string baaa. Prove by contradiction that every slithy language contains two strings of the same length.
Prove that the following language is regular.L = {x | x ∈ {0, 1}∗, x does not contain five consecutive 0's or five consecutive 1's}Hint: You may take advantage of some closure properties.
This is an Automata and Computation question on Functions/Sets.