Problem 1 a Homomorphism Is a Function H from Strings to Strings Such That for Any Two

Larry Bush Due:October 23, 2001

email: ,

Student ID: 660 220 742

Home Work 3 - Computability and Complexity (CSCI-6050)

Instructor: Prof. Goldberg

Problem 1

A homomorphism is a function h from strings to strings such that for any two strings u and v, h(uv) = h(u) h(v).(Note that h(w) =e is possible even if .)

Problem 1 - a.)

Show that if L is a context-free language and is a homomorphism, then h[L] is context-free.

ANSWER:

By definition, h(uv) = h(u)h(v) for all strings u and v.

h : E* -> E*

h is a function with a string over E as its input and a string over E as its output.

If L is a CFL, then there is a CFG that produces it.

Therefore, we will show that this grammer can be converted systematically into a grammer that produces the language h[L], thereby proving that h[L] is CF which will prove the above statement.

Let G = (V, , R, S) be a CFG grammer that generates L.

where V is the set of variables for G,

S is the start variable for the grammer and is contained in V,

E contains a finite set of terminals, and

R is a set of production rules for G with each rule having a single variable on the left hand side and a string of variables and terminals on the right hand side.

Convert G to Gh the Grammer that produces h[L]:

h[L] = the language produced by applying homomorphism h to L.

Let Gh = (Vh, , Rh, S) be a grammer that generates h[L].

In order to convert G to Gh,

1. make all a’s and b’s on the right hand side of the production rules in G into Variables A and B.
2. add the two production rules:
3. A -> aa
4. B -> a

Vh = V U { A, B}

Rh = R U (A -> aa, B -> a)

The resulting grammer is context free because the new production rules follows the rules of a context free grammer (each rule having a single variable on the left hand side and a string of variables and terminals on the right hand side), Rfollows the rules of a context free grammer and therefore, Rh, which is the union of R and the two new rules, also follows the rules of context free grammers. Therefore, this proves that h[L] is also CF.

Problem 1 - b.)Use the above to prove is not context-free.

ANSWER:

Consider a homomorphism h defined by :

.

And language:

By applying h to L we produce the language:

h[L] = { a(aa)1a(aa)2a...a(aa)na : n 0 }

The description of this language can be simplified as follows:

Since -the summation of 1 to n = n(n+1)/2 and

-we know that there were (n+1) b’s in the original language (each converted to a single ‘a’) then:

h[L] = { (aa)n(n+1)/2a(n+1) : n 0 }

={an(n+1)a(n+1) : n 0 }

={a(n^2+n)a(n+1) : n 0 }

= {a(n^2+n)+(n+1) : n 0 }

= { a(n^2+2n+1) : n 0 }

h[L] = { a(n+1)^2 : n 0 }

If h[L] is a context-free language, then there is a number p (the pumping length) where, if S is any string in L of length at least p, then S may be divided into 5 pieces, (S = uvxyz) where:

1. for each i 0, uvixyiz is contained in L
2. |vy| > 0, and
3. |vxy| p

Proof:

Assume that L is context-free.

We know that if L is context-free, then any string s in L can be pumped and remain in L.

Therefore, we wish to find a string s, in L that cannot be pumped and still remain in L.

Let p be the pumping length given by the pumping lemma.

Let s = a(n+1)^2: where n = p

Our string s is in L because our string contains only a’s and is of length |a| = (n+1)^2

And n1 because n = p

We know that s must exist if L is context free.

We will now show that s cannot be pumped for all relevent cases, so as to contradict the assumption that L is context-free.

Since s consists of only a’s, we are not concerned with where in the string the pumped substrings v and y are, nor are we concerned with which characters they contain because they may only contain a’s. (Also note that one of them may also contain e.)

We are only concerned with how many a’s v and y contain so as to determine if s will still be in h[L] when s is pumped.

If s is divided up in some manner into uvxyz,

s=aaaaaaa……...…………....aaaaaaaa

u v x y z

then for each i 0, uvixyiz the resulting string must still be in L

Due to condition 3, (which says that we can pump s by dividing it into uvxyz where |vxy| p), uvxyz must be divided up as follows:

1. v and y contain a’s.
2. v contains a’s and y contains e.
3. v contains e and y contains a’s.

The 3 above cases produce essentially the same result because our main concern is how many a’s are contained in v and y. We know by condition 3 that |vxy| p. therefore, if v or y contain the empty string, it is possible for the other to contain more a’s so long as the total length of vxy is less than or equal to p.

In its initial condition (uv1xy1z), the length of our string s is :|s| = (p+1)2 = p2 + 2p +1

because n = p

Rule 3 tells us that v and y together contain no more than p a’s. therefore, if s is pumped up to:

uv2xy2z (i = 2)

then (at most) |s| = (p+1)2 + p = p2 + 2p +1 + p = p2 + 3p +1

However, this string is not in L because the next larger string in L is :

a(n+1)^2: where n = p+1

whose length is:

((p+1)+1)2 = (p + 2)2 = p2+4p+4

obviouslyp2 + 3p +1 < p2+4p+4

thus the strings are not equal, and the length of vxy is not long enough to allow s to be pumped up to the next string in h[L].

In fact the lenth of a(n+1)^2: where n = p is p2 + 2p +1

And the lenth of a(n+1)^2: where n = p+1 is p2+4p+4

So the size of v and y would have to be (p2+4p+4) – (p2 + 2p +1) = 2p + 3.

Therefore, s could not possibly be pumped up once and stay in h[L].

Similarly (and redundantly) s cannot be pumped down to

uv0xy0z (i = 0)

because its length would be =p2 + 2p +1 - p

=p2 + p +1

which is greater than p2(the lenth of a(n+1)^2 : where n = p-1).

Thus s cannot be pumped and h[L] is not a CFL.

The rule proved above states that :

if L is a context-free language and is a homomorphism, then h[L] is context-free.

This can be abbreviated as :CF(L) -> CF(h[L])

Therefore, by the contrapositive proposition:

~CF(h[L]) -> ~CF(L)

Therefore, L is not context free.

Problem 2

Show that for every pushdown automaton M, there exists an equivalent Turing Machine T, i.e. a TM T such that L(M) = L(T).

ANSWER:

Any TM can be simulated with an equivalent 2 tape TM.

For any PDA an equivalent 2-tape TM can be constructed as follows.

Now we will show that a 4 tape TM can simulate a 3 PDA.

A 2-tape TM can simulate a PDA using the following setup.

-The initial input w will be put on tape-1.

-The reading of the input string on the PDA will be simulated on the TM by reading tape-1 and moving to the right. This will be tracked by the tape-1 head. Since a PDA can only pass over the input string once, no further tracking of this by the TM is required.

-For every e read in, the TM head should stay put.

-The state changes will be simulated by equivilent states in the TM.

-Use tape 2 as the stack. Any character pushed to the stack will be simulated in the TM by writing that character to tape-2. That tape’s head will always point to the last-in character. Newly pushed characters will be written to the next space to the right.

-For any character popped from the stack in the pda, the TM should overwrite the corresponding character on tape-2 and move head-2 to the left.

-The tm should not terminate until it reaches the blank at the right of the input string on tape 1.

-The TM should also include a rule that only allows the TM to enter the accept state when tape-2 is empty. This rule (really 2 rules working together) will correspond to the rules in the pda that push the $ on the stack at the beginning of the pda, and pop the $ off the stack at the end of the pda.

This explaination shows that a PDA can be simulated by a multi-tape TM.

We know that a multi-tape TM is equivalent to a single tape TM, therefore

a PDA can be simulated by a TM.

Basically, a PDA is a simple version of a TM.

example: a pda may accept aaaabbbb which is a string in L = {anbn : n0}

In the following example, a PDA is simulated by an equivalent TM may accept it also,

L = {anbn : n0}

then M =

M

then TM =

TM

Problem 3

Show that the collection of Turing-acceptable languages is closed under the operations union, concatenation, star, and intersection.

ANSWER:

Union

Let L1 and L2 represent arbitrary turing acceptable languages that are accepted (recognized but not necessarily decided) by the Turing Machines TM1 and TM2 respectively.

To prove that L1 U L2 is closed for all turing acceptable languages we need to show that there is a Turing Machine TM-Union that will decide the language L = L1 U L2 (the language defined by the union of L1 and L2).

TM-Union can be constructed by creating a TM that non-deterministically chooses TM1 or TM2.

TM1 is defined as:

If TM1 = ( Q-1, , -1, -1, q1-1, q_accept-1, q_reject-1 )

And TM2 is defined as:

TM2 = ( Q-2, , -2, -2, q1-2, q_accept-2, q_reject-2 )

Then TM-Union is defined as:

TM2 = ( Q, , , , q0, q_accept, q_reject )

With

Q = Q-1 U Q-2 U {q0}

 = -1 U -2

 = -1 U -2 U {  (q0, e) = (q1-1, e, S),  (q0, e) = (q1-2, e, S) }

q_accept = q_accept-1 U q_accept-2

q_reject = q_reject-1 U q_reject-2

The TM behaves as follows. String w from L is input into TM-Union. The machine may proceed to either TM1 or TM2. the computation of a nondeterministic TM I a tree whose branches correspond to different possibilities for the mahcine. Therefore, although it chooses one path or the other, the total computation is represented by a tree whose branches split whenever there is a nondeterministic choice to be made. Therefore, the Tm continues with both TM1 and TM2. If one of those TMs accept, then by definition the NM-Union accepts. However, due to the nondeterministic execution of every branch of the TM-Union tree, TM-nion will accept L because L = L1 U L2 and L1 and are accepted by TM1 and TM2 respectively, therefore, every input string w, fed to TM-Union is from L and thus is from either L1 or L2, and thus is accepted by either TM1 or TM2, and consequently is nondeterministically recognized by TM-Union.

Concatenation - L1 recognizable and L2 recognizable -> L1  L2 recognizable

Let L1 and L2 represent arbitrary turing acceptable languages that are accepted (recognized but not necessarilly decided) by the Turing Machines TM1 and TM2 respectively.

To prove that L1  L2 is closed for all turing acceptable languages we need to show that there is a Turing Machine TM-Union that will recognize the language L = L1  L2 (the language defined by the concatonation of L1 and L2).

TM- can be constructed by creating a TM that non-deterministically splits the input string w (of length p) into every possible combination of 2 pieces at point n where w1 consists of the first n characters of w and w2 consits of the last p-n characters of w. Then, TM1 will be run on w1 and TM2 will be run on w2. TM- will accept w if TM1 accepts w1 and TM2 accepts w2. Since the correct non-deterministic splitting of w into w1-w2 will be recognized by TM-, then w will be recognized by TM-.

This works because L (L = L1  L2) is a language whose strings (i.e. w) consist of a string from L1 (w1) concatonated to a string from L2 (w2). Therefore, we assume that w will be broken into w1 from L1 and w2 from L2. Then w1 will be run on TM1 and recognized, and w2 will be run on TM2 and recognized. The result is that w will be recognized by TM-.

The non-deterministic splitting of w is an important part of this machine description.

w of length p will be non-deterministically split into every possible 2 pieces at point n where w1 consists of the first n characters of w and w2 consits of the last p-n characters of w. (w1 and w2). Note that this description allows for the possibility that w1 or w2 may be the empty string.

While many of these combinations will not be the w1-w2 strings contained in L1 and L2, and therefore may not be recognized by TM-, one of these combinations will be w1-w2.

Implementation:

This setup can be simulated on a 2-tape TM.

Initially, a new set of transition functions would need to be added, nondeterministically split w into w1 and w1. As it was being split, w1 would be copied onto tape 2 and that portion of tape 1 would be overwritten with a marker.

Next, we need a set of 2-tape transition functions which allow the simultaneous application of any TM-1 transition functions (on tape 1) and the application of any TM-2 transition functions (on tape 2).

Then we have TM- accept if both TM1 and TM2 accept and reject if either TM1 or TM2 reject.

To do this we would make q-accept(TM1) and q-accept(TM2) no longer accept states. Then we would create a new accept state and a new transition function that connects the two previous accept states to it.

This setup works because if L1 and L2 are recognized by TM1 and TM2, they will also be recognized by TM-.

The TM behaves as follows.

1. String w from L is input into TM- It is initially on tape 1.
2. The TM tape head 1 reads the string from left to right until the end.
3. TM tape head 1 reads p-n characters from w, writes them to tape 2 (right to left) and overwrites those characters on tape 1.
4. the TM alternately runs one transition of TM-1 on tape 1 and one transition of TM2 on tape 2. This is simulated on 2-tape TM by creating a set of 2-tape transition functions which allow the application of any TM-1 transition functions to tape 1 and the application of any TM-2 transition functions to tape 2.
5. the TM accepts if TM1 and TM2 enter the former accept states.

Note: This is done non-deterministically. Therefore, in effect, the TM tries this for every way that w can be split. If it accepts for one of these tries, then the non-deterministic variation of a TM says that it accepts.

Star

- If L1 is recognizable then L1* is recognizable

Let L1 represent an arbitrary turing acceptable language that is accepted (recognized but not necessarilly decided) by the Turing Machine TM.

To prove that L1* is closed for all turing acceptable languages we need to show that there is a Turing Machine TM-Star that will recognize the language L = L1* (the language defined by the star function of L1).

Define Target Language

If L = L1*, then L can be any language that is created by the repeated concatonation of L1 to itself or L may conatin e. L = {e, L1, L1 L1, L1 L1 L1, …}

TM-Star can be constructed by creating a TM that non-deterministically chooses to split the input string w (of length p) a bunch of new strings. Then, TM1 will be run on each of the strings. If T1 accepts for each of the sub-strings then the original string w is accepted. One final addition, is that TM-Star should also accept e (the empty string) even if the language L1 does not conatain it. To do this, the initial state of TM-Star should be an accept state. The rest of the TM should proceed as just described.

This works because L (L = L1*) is a language whose strings (i.e. w) consist of a set of strings from L1 (w1, w2, w3, …, wn  L1) concatonated together (w1w2w3…wn). Therefore, we assume that w will be non-deterministicaly broken into the appropriate w1w2w3…wn set of strings from L1. Then w1 will be input and run on TM1 and recognize, w2 will be input and run on TM1 and recognized and so on. The result is that w will be recognized by TM-Star.

Note also that TM-Star accepts w = e. this can be accomplished by and thought of as an initial state in TM-Star that is an accept state. It can aso be conceptualized as follows. When TM-Star accepts every sub-string that w was non-deterministically broken down into, TM-Star accepts. Therefore, if w is e, then this criteria is satisfied immediately.

Implementation:

This setup can be simulated on a Multi-tape TM.

Initially, a new set of transition functions would need to be added, to non-deterministically split w into w1, w2, w3, …, wn  L1. the initial string w would be on Tape 1. As it was being split, w2 would be copied onto tape 2 and that portion of tape 1 would be overwritten with a marker. Subsequently, w3 would be copied onto tape 2 and that portion of tape 1 would be overwritten with a marker. And so on until wn is copied onto tape n and that portion of tape 1 is overwritten with a marker. (This is most easily implemented by having the tape head 1 read all of the input string from left to right until the end, then non-deterministically read wn from right to left, while writing it to tape n (right to left also) and overwriting those characters on tape 1.

Next, we need a set of multi-tape transition functions which allow the simultaneous application of any TM1 transition functions on tape 1, 2, 3… In other words, a given TM1 transition may be taking place on tape-1 while a different TM1 transition is taking place on tamp-2, etc.

Then we have TM-Star accept if TM1 has accepted every string on tape-1 through tape-n and reject if any of them have been rejected.

To do this we would make q-accept(TM1 no longer an accept state). Then we would create a new accept state and a new transition function that connects each of the ‘n’ previous accept states to the new accept state. Note that the TM1 reject states remain intact, and therefore, TM-Star will reject if any of the strings on tape-1 through n are rejected.

Intersection

Let L1 and L2 represent arbitrary turing acceptable languages that are accepted (recognized but not necessarilly decided) by the Turing Machines TM1 and TM2 respectively.

To prove that L1  L2 is closed for all turing acceptable languages we need to show that there is a Turing Machine TM- that will recognize the language L = L1  L2 (the language defined by the intersection of L1 and L2).

TM- can be constructed by creating a TM that runs both TM1 and TM2 on input string w. this can be thought of as a TM that alternately runs one transition of TM-1 and one transition of TM2. This setup works because if L1 and L2 are recognized by TM1 and TM2, they will also be recognized by TM-. TM- would recognize both L1 and L2 showing that the set of turing recognizable languages are closed under intersection.

It also follows that TM- accepts if both TM1 and TM2 accept and rejects if either TM1 and TM2 reject. Although this is not required to prove closure for turing recognizable languages.

This setup can be simulated on 2-tape TM.

Initially, a new set of transition functions would need to be added, to copy the input string from tape 1 to tape 1.

Next, we need a set of 2-tape transition functions which allow the simultaneous application of any TM-1 transition functions to tape 1 and the application of any TM-2 transition functions to tape 2.

If we wish to add the last part (TM- accepts if both TM1 and TM2 accept and rejects if either TM1 and TM2 reject), although this is not required to prove closure for turing recognizable languages, we would make q-accept(TM1) and q-ccept(TM2) no longer accept states. Then we would create a new accept state and a new transition function that connects the two previous accept states to it.

This setup works because if L1 and L2 are recognized by TM1 and TM2, they will also be recognized by TM-.

The TM behaves as follows.

1. String w from L is input into TM-. It is initially on tape 1.
2. The TM tape head 1 reads the string from left to right as head 2 writes each character to tape 2.
3. the TM alternately runs one transition of TM-1 on tape 1 and one transition of TM2 on tape 2. This is simulated on 2-tape TM by creating a set of 2-tape transition functions which allow the application of any TM-1 transition functions to tape 1 and the application of any TM-2 transition functions to tape 2.
4. the TM accepts if TM1 and TM2 enter the former accept states.

End Problem 3
Problem 4

Part 1. Show that 2-PDAs are more powerful than 1-PDAs; .

First we will show that a 2-pda can accept the language:

L = {anbncn : n 1}

A 1-PDA can accept a CF language such as anbn . However, to generate or accept the non-CF language L = {anbncn : n 1} a context sensitive grammer or TM is needed because of the complexity of the ordering of the elements.

However, a 2-PDA, which is essentially equivalent to a TM can also accept this language.

For example, if

L = {anbncn : n 1}

then M =