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

The homomorphism h is defined by h(a) = 01 and h(b) = 10. What is h(%%1%%2%%3%%4)?
Use the Pumping Lemma to show the following language L is NOT regular. L= {w E (a, b, c}* ; where w has equal number of a's, b's, and c's}
Rewrite BNF to EBNF BNF: → + Kexpr> - → * / | → ** → () id
Define a NPDA for the language L= {uv € {a, b}*||u|l = |v| and u # v*}. Another way to interpret L is that it is the set of all cven length strings that are not a palindrome.
∑ = {C,A,G,T}, L = { w : w = CAjGnTmC, m = j + n }. For example, CAGTTC ∈ L; CTAGTC ∉ L because the symbols are not in the order specified by the characteristic function; CAGTT ∉ L because it does not end with C; and CAGGTTC ∉ L because the number of T's do not equal the number of A's plus the number of G's. Prove that L ∉ RLs using the RL pumping theorem.
Implement the following two functions that allow breaking a string into non-empty tokens using a given delimiter in c language . For example, ● For a string “abc-EFG-hi”, and a delimiter ‘-’ : the list of tokens is [“abc”, “EFG”, “hi”] ● For a string “abc-EFG---hi-”, and a delimiter ‘-’ : the list of tokens is [“abc”, “EFG”, “hi”] ● For a string “abc”, and a delimiter ‘ ’ : the list of tokens is [“abc”] ● For a string “++abc++”, and a delimiter ‘+’ : the list of tokens is [“abc”] That is, we break the string using the given delimiter, and the tokens are only the non-empty substrings.
Implement the following two functions that allow breaking a string into non-empty tokens using a given delimiter in c language . For example, ● For a string “abc-EFG-hi”, and a delimiter ‘-’ : the list of tokens is [“abc”, “EFG”, “hi”] ● For a string “abc-EFG---hi-”, and a delimiter ‘-’ : the list of tokens is [“abc”, “EFG”, “hi”] ● For a string “abc”, and a delimiter ‘ ’ : the list of tokens is [“abc”] ● For a string “++abc++”, and a delimiter ‘+’ : the list of tokens is [“abc”] That is, we break the string using the given delimiter, and the tokens are only the non-empty substrings. The function count_tokens gets a string str, and a char delim, and returns the number of tokens in the string separated by delim. int count_tokens(const char* str, char delim); For example● count_tokens("abc-EFG--",'-')needstoreturn2. ● count_tokens("++a+b+c",'+')needstoreturn3.● count_tokens("***",'*')needstoreturn0.The function get_tokens gets a string str, and a char delim, and returns the…
The language Balanced over E = {(,)} is defined recursively as follows 1. ЛЄ Вalanced. 2. Vx, y € Balanced, both xy and (x) are elements of Balanced. A prefix of a string x is a substring of x that occurs at the beginning of x. Prove by induction that a string x belongs to this language if and only if (iff) the statement B(x) is true. B(x): x contains equal numbers of left and right parentheses, and no prefix of x contains more right than left.
Construct a CFG and PDA for the language B={w| w is a string over {a,b} with the same count of a's and b's}. For example, abba € B, abab e B,aabb € B, babbbaaaba € B, that is, there is no particular order in which a's and b's appear in w as long as there is the same amount of them.
Given: Language L1 = {aa, b, bc}Determine: 3th Power of L1 = L1^3Hint: The Power of L is the set of all subsets of L
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. I want a CFG
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.