Substitutions and Homomorphisms

Homomorphic Characterization

End

Theory of Computation
Thomas Zeugmann
Hokkaido University
Laboratory for Algorithmics
http://www-alg.ist.hokudai.ac.jp/∼thomas/ToC/

Lecture 8: CF and Homomorphisms

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Substitutions I
In this lecture we continue with further useful properties andcharacterizations of context-free languages. First, we look at
substitutions.

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Substitutions I
In this lecture we continue with further useful properties andcharacterizations of context-free languages. First, we look at
substitutions.
Definition 1
Let Σ and ∆ be any two finite alphabets. A mappingτ : Σ −→ ℘(∆∗ ) is said to be a substitution. We extend τ to be amapping τ : Σ∗ −→ ℘(∆∗ ) (i.e., to strings) by defining(1) τ(λ) = λ,(2) τ(wx) = τ(w)τ(x) for all w ∈ Σ∗ and x ∈ Σ.
The mapping τ is generalized to languages L ⊆ Σ∗ by setting[
τ(L) =
τ(w) .
w∈L

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Substitutions II
So, a substitution maps every symbol of Σ to a language over ∆.
The language a symbol is mapped to can be finite or infinite.

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Substitutions II
So, a substitution maps every symbol of Σ to a language over ∆.
The language a symbol is mapped to can be finite or infinite.
Example 1
Let Σ = {0, 1} and let ∆ = {a, b}. Then, the mapping τ definedby τ(λ) = λ, τ(0) = {a} and τ(1) = {b}∗ is a substitution.
Let us calculate τ(010). By definition,
τ(010) = τ(01)τ(0) = τ(0)τ(1)τ(0) = {a}{b}∗ {a} = ahbia ,where the latter equality is by the definition of regularexpressions.

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Substitutions III
Next, we want to define what is meant by closure of a language
family L under substitutions. Here special care is necessary. At
first glance, we may be tempted to require that for every
substitution τ the condition τ(L) ∈ L has to be satisfied.
But this is a too strong demand. Why?

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Substitutions III
Next, we want to define what is meant by closure of a language
family L under substitutions. Here special care is necessary. At
first glance, we may be tempted to require that for every
substitution τ the condition τ(L) ∈ L has to be satisfied.
But this is a too strong demand. Why?
Consider Σ = {0, 1}, ∆ = {a, b} and L = REG. Furthermore,
suppose that τ(0) = L, where L is any recursively enumerable
but non-recursive language over ∆.

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Substitutions III
Next, we want to define what is meant by closure of a language
family L under substitutions. Here special care is necessary. At
first glance, we may be tempted to require that for every
substitution τ the condition τ(L) ∈ L has to be satisfied.
But this is a too strong demand. Why?
Consider Σ = {0, 1}, ∆ = {a, b} and L = REG. Furthermore,
suppose that τ(0) = L, where L is any recursively enumerable
but non-recursive language over ∆.
Then we obviously have τ({0}) = L, too. Consequently,τ({0}) < REG. On the other hand, {0} ∈ REG, and thus we would
conclude that REG is not closed under substitution. Also, thesame argument would prove that CF is not closed undersubstitution.
Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Substitutions IV

The point to be made here is that we have to restrict the set ofallowed substitutions to those ones that map the elements of Σ
to languages belonging to L. Therefore, we arrive at thefollowing definition.

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Substitutions IV

The point to be made here is that we have to restrict the set ofallowed substitutions to those ones that map the elements of Σ
to languages belonging to L. Therefore, we arrive at thefollowing definition.
Definition 2
Let Σ be any alphabet, and let L be any language family over Σ.
We say that L is closed under substitutions if for every
substitution τ : Σ −→ L and every L ∈ L we have τ(L) ∈ L.

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Homomorphisms I
Definition 3
Let Σ and ∆ be any two finite alphabets. A mapping
ϕ : Σ∗ −→ ∆∗ is said to be a homomorphism if
ϕ(vw) = ϕ(v)ϕ(w)for all v, w ∈ Σ∗ .

ϕ is said to be a λ-free homomorphism, if additionallyϕ(w) = λimplies

w=λ

for all w ∈ Σ∗ .

Moreover, if ϕ : Σ∗ −→ ∆∗ is a homomorphism then we define
the inverse of the homomorphism ϕ to be the mapping
ϕ−1 : ∆∗ −→ ℘(Σ∗ ) by setting for each s ∈ ∆∗ϕ−1 (s) = {w | w ∈ Σ∗ and ϕ(w) = s} .
Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Homomorphisms II
So, a homomorphism is a special case of a substitution.

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Homomorphisms II
So, a homomorphism is a special case of a substitution.
That is, a homomorphism is a substitution that maps every
symbols of Σ to a singleton set. Clearly, by the definition ofhomomorphism, it already suffices to declare the mapping ϕfor the symbols in Σ. Note that, when dealing withhomomorphisms we usually identify the language containing
exactly one string by the string itself, i.e., instead of {s} weshortly write s.

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Homomorphisms II
So, a homomorphism is a special case of a substitution.
That is, a homomorphism is a substitution that maps every
symbols of Σ to a singleton set. Clearly, by the definition ofhomomorphism, it already suffices to declare the mapping ϕfor the symbols in Σ. Note that, when dealing withhomomorphisms we usually identify the language containing
exactly one string by the string itself, i.e., instead of {s} weshortly write s.
Example 2
Let Σ = {0, 1} and let ∆ = {a, b}. Then, the mapping
ϕ : Σ∗ −→ ∆∗ defined by ϕ(0) = ab and ϕ(1) = λ is ahomomorphisms but not a λ-free homomorphism. Applying ϕ to1100 yields ϕ(1100) = ϕ(1)ϕ(1)ϕ(0)ϕ(0) = λλabab = ababand to the language 1h0i1 gives ϕ(1h0i1) = habi.
Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Remarks
For seeing the importance of the notions just introduced
consider the language L = {an bn | n ∈ N}. This language iscontext-free. Thus, we intuitively know that {0n 1n | n ∈ N} isalso context-free, since we could go through the grammar andreplace all occurrences of a by 0 and all occurrences of b by 1.

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Remarks
For seeing the importance of the notions just introduced
consider the language L = {an bn | n ∈ N}. This language iscontext-free. Thus, we intuitively know that {0n 1n | n ∈ N} isalso context-free, since we could go through the grammar andreplace all occurrences of a by 0 and all occurrences of b by 1.
This observation would suggest that if we replace all
occurrences of a and b by strings v and w, respectively, we also
get a context-free language. However, it is much less intuitivethat we also obtain a context-free language if all occurrences ofa and b are replaced by context-free sets of strings V and W,
respectively.

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Remarks
For seeing the importance of the notions just introduced
consider the language L = {an bn | n ∈ N}. This language iscontext-free. Thus, we intuitively know that {0n 1n | n ∈ N} isalso context-free, since we could go through the grammar andreplace all occurrences of a by 0 and all occurrences of b by 1.
This observation would suggest that if we replace all
occurrences of a and b by strings v and w, respectively, we also
get a context-free language. However, it is much less intuitivethat we also obtain a context-free language if all occurrences ofa and b are replaced by context-free sets of strings V and W,
respectively.
Nevertheless, we just aim to prove this closure property. In thefollowing we always assume two finite alphabets Σ and ∆ as in
the definition of substitution.
Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Closure under Substitutions I
Theorem 1
CF is closed under substitutions.

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Closure under Substitutions I
Theorem 1
CF is closed under substitutions.
Proof. Let L ∈ CF be arbitrarily fixed and let τ be a substitution
such that τ(a) is a context-free language for all a ∈ Σ. We haveto show that τ(L) is context-free. We shall do this by providing
a context-free grammar G = [T , N, σ, P] such that L(G) = τ(L).

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Closure under Substitutions I
Theorem 1
CF is closed under substitutions.
Proof. Let L ∈ CF be arbitrarily fixed and let τ be a substitution
such that τ(a) is a context-free language for all a ∈ Σ. We haveto show that τ(L) is context-free. We shall do this by providing
a context-free grammar G = [T , N, σ, P] such that L(G) = τ(L).
Since L ∈ CF, there exists a context-free grammar
G = [Σ, N, σ, P] in Chomsky normal form such that L = L(G).
Next, let Σ = {a1 , . . . , an } and consider τ(a) for all a ∈ Σ. By
assumption, τ(a) ∈ CF for all a ∈ Σ. Thus, there arecontext-free grammars Ga = [Ta , Na , σa , Pa ] such that
τ(a) = L(Ga ) for all a ∈ Σ. Without loss of generality, we canassume the sets N, Na1 , . . . , Nan to be pairwise disjoint anddisjoint to all terminal alphabets considered.
Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Closure under Substitutions II
At this point we need an idea how to proceed. To get this idea, welook at possible derivations in G. Suppose we have a derivation∗

σ =⇒ x1 x2 · · · xm ,G

where all xi ∈ Σ for i = 1, . . . , m.

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Closure under Substitutions II
At this point we need an idea how to proceed. To get this idea, welook at possible derivations in G. Suppose we have a derivation∗

σ =⇒ x1 x2 · · · xm ,G

where all xi ∈ Σ for i = 1, . . . , m. Then, since G is in Chomsky
normal form, we can conclude that there must be productions(hxi → xi ) ∈ P, i = 1, . . . , m, and hence achieve the following.
∗

m

G

G

σ =⇒ hx1 hx2 · · · hxm =⇒ x1 x2 · · · xm ,(1)

where all hxi ∈ N.
Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Closure under Substitutions III

Taking into account that the image τ(x1 · · · xm ) is obtained by
calculating
τ(x1 )τ(x2 ) · · · τ(xm ) ,we see that for every string w1 w2 · · · wm in this image there
must be a derivation∗

σxi =⇒ wi
Gxi

i = 1, . . . , m .

This directly yields the idea for constructing G.

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Closure under Substitutions IV
We aim to cut the derivation in (1) when having obtained
hx1 hx2 · · · hxm . Instead of deriving x1 x2 · · · xm , all we need is togenerate σx1 · · · σxm , and thus, we have to replace theproductions (hxi → xi ) ∈ P by (hxi → σxi ) ∈ P, i = 1, . . . , m.
So we define:

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Closure under Substitutions IV
We aim to cut the derivation in (1) when having obtained
hx1 hx2 · · · hxm . Instead of deriving x1 x2 · · · xm , all we need is togenerate σx1 · · · σxm , and thus, we have to replace theproductions (hxi → xi ) ∈ P by (hxi → σxi ) ∈ P, i = 1, . . . , m.
So we define:
[
T =
Ta
a∈Σ

!
N = N∪

[

Na

a∈Σ

σ = σ
!
P =

[

Pa

∪ P[a//σa ] .

a∈ΣWe set G = [T , N, σ, P].
Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Closure under Substitutions V
It remains to show that τ(L) = L(G).
Claim 1. τ(L) ⊆ L(G).

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Closure under Substitutions V
It remains to show that τ(L) = L(G).
Claim 1. τ(L) ⊆ L(G).
∗

∗

G

Gxi

If σ =⇒ x1 · · · xm , where xi ∈ Σ and if σxi =⇒ wi , wherewi ∈ Tx∗i , i = 1, . . . , m, then we derive x1 · · · xm as follows:
∗

∗

G

G

σ =⇒ hx1 · · · hxm =⇒ x1 · · · xm ,where all hxi ∈ N. By construction, we can thus generate∗∗∗σ =⇒ hx1 · · · hxm =⇒ σx1 · · · σxm =⇒ w1 · · · wm .
G

GGHence, Claim 1 follows.
Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Closure under Substitutions VI
Claim 2. L(G) ⊆ τ(L).
∗∗Now, we start from σ ⇒ w , where w ∈ T . If w = λ, then also
σ → λ in P, and we are done.

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Closure under Substitutions VI
Claim 2. L(G) ⊆ τ(L).
∗∗Now, we start from σ ⇒ w , where w ∈ T . If w = λ, then also
σ → λ in P, and we are done. Otherwise, the construction of G
ensures that the derivation of w must look as follows.
∗∗σ =⇒ σx1 · · · σxm =⇒ w .
G

Theory of ComputationGc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Closure under Substitutions VI
Claim 2. L(G) ⊆ τ(L).
∗∗Now, we start from σ ⇒ w , where w ∈ T . If w = λ, then also
σ → λ in P, and we are done. Otherwise, the construction of G
ensures that the derivation of w must look as follows.
∗∗σ =⇒ σx1 · · · σxm =⇒ w .
GG∗

By our construction we then know that σ =⇒ x1 · · · xm as weG∗have shown in (1). Also, there are strings w1 , . . . , wm ∈ T such∗that w = w1 · · · wm and σxi =⇒ wi for all i = 1, . . . , m.
Gxi

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Closure under Substitutions VII
Consequently, wi ∈ τ(xi ). Therefore, w ∈ τ(L) and we are done.

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Closure under Substitutions VII
Consequently, wi ∈ τ(xi ). Therefore, w ∈ τ(L) and we are done.
Finally, putting Claim 1 and 2 together, we see that
τ(L) = L(G) .

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Closure under Substitutions VII
Consequently, wi ∈ τ(xi ). Therefore, w ∈ τ(L) and we are done.
Finally, putting Claim 1 and 2 together, we see that
τ(L) = L(G) .

Our Theorem allows the following nice corollary.
Corollary 2
CF is closed under homomorphisms.
Proof. Since homomorphisms are a special type of substitution,
it suffices to argue that every singleton subset is context-free.
But this is obvious, because we have already shown that every
finite language belongs to REG and that REG ⊆ CF. Thus, thecorollary follows.
Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Dyck Languages I
When we started to study context-free languages, weemphasized that many programming languages use balanced
brackets of different kinds. Therefore, we continue with a closer
look at bracket languages. Such languages are called Dyck
languages.

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Dyck Languages I
When we started to study context-free languages, weemphasized that many programming languages use balanced
brackets of different kinds. Therefore, we continue with a closer
look at bracket languages. Such languages are called Dyck
languages.
In order to define Dyck languages, we need the following
notations. Let n ∈ N+ and let
Xn = {a1 , a1 , a2 , a2 , . . . , an , an } .
We consider the set Xn as a set of different bracket symbols,
where ai is an opening bracket and ai is the corresponding
closing bracket. Thus, it is justified to speak of Xn as a set of ndifferent bracket symbols.
Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Dyck Languages II
Now we are ready to define Dyck languages.
Definition 4
A language L is said to be a Dyck language with n bracket
symbols if L is isomorphic to the language Dn generated by thefollowing grammar Gn = [Xn , {σ}, σ, Pn ], where Pn is given by
Pn = {σ → λ, σ → σσ, σ → a1 σa1 , . . . , σ → an σan } .

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Dyck Languages II
Now we are ready to define Dyck languages.
Definition 4
A language L is said to be a Dyck language with n bracket
symbols if L is isomorphic to the language Dn generated by thefollowing grammar Gn = [Xn , {σ}, σ, Pn ], where Pn is given by
Pn = {σ → λ, σ → σσ, σ → a1 σa1 , . . . , σ → an σan } .
The importance of Dyck languages will become immediatelytransparent, since we are going to prove a beautiful
characterization theorem for context-free languages by using
them.

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Chomsky-Schützenberger Theorem I

Theorem 3 (Chomsky-Schützenberger Theorem)
For every context-free language L there are n ∈ N+ , ahomomorphism h and a regular language RL such that
L = h(Dn ∩ RL ) .

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Chomsky-Schützenberger Theorem II

Proof. Consider any arbitrarily fixed context-free language L.
Without loss of generality we can assume that λ < L.
Furthermore, let G = [T , N, σ, P] be a context-free grammar in
Chomsky normal form such that L = L(G). Let T = {x1 , . . . , xm }and consider all productions in P. Since G is in Chomsky
normal form, all productions have the form hi → hi0 hi00 or
hj → x. Let t be the number of all nonterminal productions,
i.e., of all productions hi → hi0 hi00 . Note that for any two suchproductions it is well possible that some but not all nonterminal
symbols coincide.

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Chomsky-Schützenberger Theorem III
In all we have m terminal symbols and t nonterminal
productions. Thus, we try the Dyck language Dm+t over
Xm+t = {x1 , . . . , xm , xm+1 , . . . , xm+t ,xm+1 , . . . , xm+t , x1 , . . . , xm } .

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Chomsky-Schützenberger Theorem III
In all we have m terminal symbols and t nonterminal
productions. Thus, we try the Dyck language Dm+t over
Xm+t = {x1 , . . . , xm , xm+1 , . . . , xm+t ,xm+1 , . . . , xm+t , x1 , . . . , xm } .
Next, we consider the mapping χm+t : Xm+t −→ T ∗ defined asfollows.

xj , if 1 6 j 6 m ;χm+t (xj ) =λ, if m + 1 6 j 6 m + t ;and χm+t (xj ) = λ for all j = 1, . . . , m + t. We leave it as an
exercise to show that χm+t is a homomorphism.
Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Chomsky-Schützenberger Theorem IV
Now we are ready to define the following grammar
GL = [Xm+t , N, σ, PL ], where
PL = {h → xi xi | 1 6 i 6 m and (h → xi ) ∈ P}
∪ {h → xi xi xm+j hj00 | 1 6 i 6 m, (h → xi ) ∈ P, 1 6 j 6 t}
∪ {hj → xm+j hj0 | 1 6 j 6 t} .
Clearly, GL is a regular grammar. We set RL = L(GL ), and aim
to prove thatL = χm+t (Dm+t ∩ RL ) .
This is done via the following claims and lemmata.

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Chomsky-Schützenberger Theorem V
Claim 1. L ⊆ χm+t (Dm+t ∩ RL ).
The proof of Claim 1 is mainly based on the following lemma.
Lemma 4
Let G be the grammar for L fixed above, let GL be the grammar for RL
and let h ∈ N. If
1

1

1

1

1

G

G

G

G

G

h =⇒ w1 =⇒ w2 =⇒ · · · =⇒ wn−1 =⇒ wn ∈ T ∗∗then there exists a q ∈ Dm+t such that h =⇒ q andGLχm+t (q) = wn .
Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Chomsky-Schützenberger Theorem VI

The lemma is shown by induction on the length n of thederivation. For the induction basis let n = 1. Thus, ourassumption is that1h =⇒ w1 ∈ T ∗ .
GSince G is in Chomsky normal form, we can conclude that(h → w1 ) ∈ P. So, by the definition of Chomsky normal form,
we must have w1 = x for some x ∈ T .

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Chomsky-Schützenberger Theorem VII∗

We have to show that there is a q ∈ Dm+t such that h =⇒ qGLand χm+t (q) = x. By construction, the production h → xx
belongs to PL (cf. the first set of the definition of PL ). Thus, we
can simply set q = xx. Now, the induction basis follows, since
the definition of χm+t directly yields
χm+t (q) = χm+t (xx) = χm+t (x)χm+t (x) = xλ = x .

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Chomsky-Schützenberger Theorem VIII
Assuming the induction hypothesis for n > 1, we are going toperform the induction step to n + 1. So, let
1

1

1

1

G

G

G

G

h =⇒ w1 =⇒ · · · =⇒ wn =⇒ wn+1 ∈ T ∗be a derivation of length n + 1.

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Chomsky-Schützenberger Theorem VIII
Assuming the induction hypothesis for n > 1, we are going toperform the induction step to n + 1. So, let
1

1

1

1

G

G

G

G

h =⇒ w1 =⇒ · · · =⇒ wn =⇒ wn+1 ∈ T ∗be a derivation of length n + 1.
Because of n > 1, and since the derivation has length at least 2,
we can conclude that the production used to derive w1 must beof the form h → h 0 h 00 , where h, h 0 , h 00 ∈ N. Therefore, there
must be a j such that 1 6 j 6 t and h = hj as well as w1 = hj0 hj00 .

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Chomsky-Schützenberger Theorem IX
The latter observation implies that there must be v1 , v2 such thatwn+1 = v1 v2 and∗hj0 =⇒ v1
G∗

and hj00 =⇒ v2 .
G

Since the length of the complete derivation is n + 1, both thegeneration of v1 and of v2 must have a length smaller than orequal to n.
Hence, we can apply the induction hypothesis. That is, there
are strings q1 and q2 such that q1 , q2 ∈ Dm+t andχm+t (q1 ) = v1 as well as χm+t (q2 ) = v2 .

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Chomsky-Schützenberger Theorem X
Furthermore, by the induction hypothesis we additionallyknow that∗∗hj0 =⇒ q1 and hj00 =⇒ q2 .
GLGL

hj0 hj00 ) ∈ P we know by

Taking into account that (hj →construction that hj → xm+j hj0 is a production in PL . Thus,
1

∗

GL

GL

h = hj =⇒ xm+j hj0 =⇒ xm+j q1
is a regular derivation. Moreover, the last step of this derivationmust look as follows:1

xm+j q10 hk =⇒ xm+j q10 xx .
GL

where hk → xx is the rule applied and where x is determinedby the condition q1 = q10 xx.
Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Chomsky-Schützenberger Theorem XI
Now, we replace this step by using the production
hk → xxxm+j hj00 which also belongs to PL . Thus, we obtain
1

∗

GL

GL

h = hj =⇒ xm+j hj0 =⇒ xm+j q1 xm+j hj00∗=⇒ xm+j q1 xm+j q2 =: q ∈ Dm+t .
GL

The containment in Dm+t is due to the correct usage of thebrackets xm+j and xm+j around q1 and the fact that q2 ∈ Dm+t
as well as by the definition of the Dyck language. Finally, thedefinition of χm+t ensures that χm+t (xm+j q1 xm+j q2 ) = v1 v2 .
This proves the lemma and Claim 1 immediately follows for
h = σ.
Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Chomsky-Schützenberger Theorem XII
Claim 2. L ⊇ χm+t (Dm+t ∩ RL ).
Again, the proof of the claim is mainly based on a lemma which
we state next.
Lemma 5Let G be the grammar for L fixed above, let GL be the grammar for RL
and let h ∈ N. If
1

1

1

GL

GL

GL

h =⇒ w1 =⇒ · · · =⇒ wn ∈ Dm+t∗

then h =⇒ χm+t (wn ).
G

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Chomsky-Schützenberger Theorem XIII
The lemma is shown by induction on the length of thederivation. We perform the induction basis for n = 1. Consider
1h =⇒ w1 ∈ Dm+t .
GLHence, we must conclude that (h → w1 ) ∈ PL . So, there must
exist xi xi such that w1 = xi xi , 1 6 i 6 m and (h → xi xi ) ∈ PL .
By the definition of PL we conclude that (h → xi ) ∈ P. Hence1h =⇒ xi = χm+t (xi xi ) = χm+t (w1 ) .
GThis proves the induction basis.
Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Chomsky-Schützenberger Theorem XIV

The induction step is provided in the book.
Again, Claim 2 is a direct consequence of the latter lemma forh = σ.
Claim 1 and Claim 2 together imply the theorem.

Theory of Computationc Thomas Zeugmann

Substitutions and Homomorphisms

Homomorphic Characterization

End

Thank you!

Theory of Computationc Thomas Zeugmann