- (a) L = { 0n1n2n | n a nonnegative integer }.
Suppose L is regular and hence satisfy the PLP. Let p be as in the PLP.
Take s = 0p1p2p, which is in L, and has length
at least p. The Pumping Lemma says that s = xyz for strings x, y, z satisfying
certain properties. One of these is that the length of xy does not exceed p.
But s begins with p zeros. So xy must consist entirely of zeros. Since y is not
the empty string, must have y = 0k for some postitive integer k.
Then xz = 0p-k1p2p. The Pumping Lemma says this
must be in L. But clearly this is not in L (since p-k is not equal to p). This
contradiction means that L is not regular.
- (b) L = { www | w in {a,b}* }. Suppose L is regular and hence satisfies the PLP. Let p be as in the PLP. Take s = apbapbapb. This is clearly in L (by using apb for w). Again, PLP means that s = xyz with .... Again xy has length <= p and y is not empty forcing y = ak for positive integer k. So xz = ap-kbapbapb. The Pumping Lemma says this is in L, but clearly it is not. Etcetera.
- Let's consider the strings are produced in Exercise 2.3.
X becomes either a or b.
T becomes any string.
S becomes any string that starts with a and ends with b, or vice-versa.
R becomes any string that has a string as just described somewhere in the
middle (with same amount of padding on either side). In other words,
R becomes any NON-palindrome.
The variable symbols here are R, S, T and X. The implication is that R is the starting symbol. The terminal symbols are a and b. Please please don't regard epsilon as a symbol in this game. It is not a terminal symbol. It is not a variable symbol.
The true/false answers go like this: F T F T T F T T F.
- Here are my answers for Exercise 2.4:
- Part (a) S -> T1T1T1T , T -> epsilon | T0 | T1
- Part (b) S -> 0T0 | 1T1 , T -> epsilon | T0 | T1
- Part (c) S -> 0 | 1 | 0S0 | 0S1 | 1S0 | 1S1
- Part (d) S -> 0 | 0S0 | 0S1 | 1S0 | 1S1
- Part (e) S -> T1T | S1T | T1S | S1S
T -> epsilon | 01T | 10T | 0T1 | 1T0 | T01 |T10 - Part (f) S -> epsilon | 0 | 1 | 0S0 | 1S1
- Part (g) (no transition rules - please don't say S -> epsilon)
- Exercise 2.6 is pretty tricky. Here are some premininary thoughts
followed by my solutions:
- Let A be some alphabet. We know that the set of strings
{ wwR | w in A* } is a context-free language.
It consists of the set of even-length palindromes over A,
and we looked at it in class. A CFG for it is easy to cook up.
It is also possible to envision how a PDA could be built to
recognize it, although non-determinism is important here because
we don't know where the midpoint of the string is that we're processing.
Basically, our PDA would begin by simply pushing input symbols
onto the stack as they arrives. At some (nondeterministic) moment
it would stop doing that, and instead would read input symbols
and simultaneously pop symbols off the stack, and compare them,
etcetera.
- But what about the related language { ww | w in A* }, which is
even a bit easier to describe in set-theory notation. The language
consist of even-length strings whose two halves are the same. Is
this a context-free language? This is much less clear! However,
there is a version of the Pumping Lemma for context-free languages
(more complicated than the Pumping Lemma for regular langages!),
and this can be used to show that the language in question here is
NOT a context-free language. (See Example 2.22 on page 119.)
- Part (a) of Exercise 2.6 is not too bad. Start by noticing that epsilon
is a string in this language (zero times two equals zero), so have a
rule that says S ---> epsilon. Then think about the example I gave you
for "well-formed parentheses expressions". The rules basically said that
if you had one or two of these you could build another putting parentheses
around one such, or by putting two such side-by-side. You can do something
similar here.
- Part (b) is tricky. In class, we saw how to hook up CFGs via union,
concatenation and star, to form other CFGs. We'll do part (b) as the union
of three other CFGs.
The alphabet is {a,b}. There are probably several ways to do this one. Here is what comes to my mind. Consider first the regular language given by the regular expression a*b*. The complement of a regular language is always regular. The complement of the language described by a*b* is in fact (a|b)*ba(a|b)* , which you should be able to see. Since this is a regular language, it is context-free. Call this language L1. It's straightforward to cook up a CFG for this.
Next consider a sublanguage of the language given by a*b*, namely the language {ambn | 0 <= m < n }. The strings here consist of several a symbols followed by a greater number of b symbols. This is not regular, but it is context-free. Call this language L2. You should be able to produce a CFG for it based on the CFG for the language {anbn | 0 <= n }. Likewise, let L3 be {ambn | 0 <= n < m }. You should be able to get a CFG for it.
Now the language in part (b) is just the union of L1, L2 and L3. You have CFGs for each of these, so you should be able to produce a CFG for the union of these languages.
- Part (c). We need a CFG for the language
{ w#x | wR is a substring of x, and x is in {0,1}* } .Notice that the set of terminal symbols is {0,1,#}. Here is a possible solution:
S ---> T | T0 | T1 T ---> U | 0T0 | 1T1 U ---> # | U0 | U1(Note: I got tired of coloring coding from here.) First notice what you can derive from U: all strings of the form #(0|1)*. Then notice what you can derive from T: all strings of the form w#(0|1)*wR , where w is of the form (0|1)*, i.e. w is in the set {0,1}*. Finally, notice what you can derive from S: all strings of the form w#(0|1)*wR(0|1)*. This is what we want.
- Part (d). (No patience left for this one.)
- Let A be some alphabet. We know that the set of strings
{ wwR | w in A* } is a context-free language.
It consists of the set of even-length palindromes over A,
and we looked at it in class. A CFG for it is easy to cook up.
It is also possible to envision how a PDA could be built to
recognize it, although non-determinism is important here because
we don't know where the midpoint of the string is that we're processing.
Basically, our PDA would begin by simply pushing input symbols
onto the stack as they arrives. At some (nondeterministic) moment
it would stop doing that, and instead would read input symbols
and simultaneously pop symbols off the stack, and compare them,
etcetera.
- Exercise 2.9.
S ---> T | U T ---> X | Tc X ---> epsilon | aXb U ---> Y | aU Y ---> epsilon | bYcYes, it is ambiguous. I can easily find two deifferent left-derivations of the string abc.
There is an important technical point here. Suppose that N has p states and that there are k input symbols. I claim that no node of the configuration tree can have more than 3kp child nodes. This is because, given a configuration, the next configuration is determined by deciding which state to transition to, which symbol to write onto the tape, and which way (L, R or S) to more the read-write head. Let n = 3kp. We can assume that n tape symbols are used for D's third tape: tau1, tau2, ..., taun. Now if a string like tau5 tau1 tau4 is recorded on the 3rd tape, the interpret this as representing the node (configuration) on the configuration tree arrived at by starting at the root, going to the root's 5th child node, then going to that node's 1st child node, and then going to that node's 4th child node. It is not difficult to arrange for D to process such strings on its 3rd tape so as to sequence through the nodes of the configuration tree in a breadth-first fashion.
D's emulation of N on a given input string now proceeds as follows. D repeatedly does this: (1) determine the string representation on the 3rd tape for the next node in the tree, (2) copy the input string from the 1st tape to the 2nd tape, (3) read the characters on the third tape from left to right so as to represent moving along a path in the configuration tree from the root to the node currently being visited, and (4) in so doing, emulate the behavior of N following this path by altering tape two accordingly along the way. Now if D ever encounters an accepting configuration, then D should stop processing and go into its own accept state. Otherwise, it should keep visiting new nodes and processing as described here, unless it runs out of nodes to visit. If this happens (and no accepting configurations were found) then D should go into its reject state,
If N is not a deciding NTM then there is no reason why D should be deciding either. Its processing of a configuration tree might go on forever because the configuration tree might go on forever and might not contain any accepting configurations. But if N IS a deciding NTM, then all of its configuration trees must be finite, that is, all paths through it must terminate. Clearly D will always halt in this case. Either it accepts because it finds an accepting configuration, or else it eventally runs out of nodes to visit, and so rejects. Therefore any language that is the language of a deciding non-deterministic Turing machine is also the language of a deciding deterministic Turing machine, that is, it is a Turing-decidable language.
- 7.1: T, F, F, T, T, T.
- 7.6:
- Complement is easy. Just reverse accept and reject states.
- Union? This is not as obvious! However, since both languages
are decidable, you could hook up a deciding DTM that first emulates
a DTM that decides about the first language. If the input string is
in the first language, then the emulator would halt accepting. But
if the input string was not in the first language, then it would
emulate a DTM to decide if the string is in the second language.
It would accept if so, otherwise it would reject. Since both DTMs
for the two original languages will decide in polynomial time, and
since the emulator is essentially just a variation on the concatenation
of these two machgines, the emulator will decide in polynomial time
as well.
Now, I originally thought about this in terms of parallel processing instead of serial (sequential) processing. Here is the story for a parallel approach. By allowing lots of tape symbols, we can use one tape to simulate two tapes on two TMs. We need to "mark" spots where the heads of each TM are. The TM that simulates two other TMs must first simulate one of the original two TMs by locating where its head should be and then acting accordingly. It must then simulate the other TM by locating its head and acting accordingly. So it seems to me that the number of steps required to execute a single step on both of the original two TMs is not any worse than a constant times the size of the portion of the tape that is being used, i.e. ignore the end of the tape that is filled with blanks. This is bound by a polynomial in the length of the input string. Here is my argument laid out more carefully:
- Suppose M1 (M2) is a deciding DTM that has L1 (L2) as its language. Suppose too that each of these halts in time bounded by C np. (We can use the same C and p for both DTMs. Why???)
- So it is very clear that the length of the used portion of the tape for either of these two DTMs can never exceed C np.
- Now, let M be the new DTM that will simulate both M1 and M2 "at the same time". M's tape will reflect the other two tapes by means of extra tape symbols. So the used portion of M's tape will never exceed length C np.
- Now to simulate a single step of M1, need to first find the "marker" that indicates where M1's head is located. This will take no longer than C np steps. Then the single step of M1 can be emulated on M. This will only take a couple steps on M, one to change a tape symbol to reflect a tape symbol change on M1's tape, and one change a tape symbol on M to reflect the head movement in M1. So emulating the one step of M1 required at most C np + 2 steps on M. Now ditto this for emulating a single step on M2. This also requires at most C np + 2 steps. Together this means 2C np + 4 steps to emulate a single step on both machines. Now both machines halt within C np steps. Therefore the simulator M can be built to halt within C np ( C np + 2 ) = C2 n2p + 2 C np steps. This is a polynomial in n. Of course we arrange for M to accept if and only if at least one of M1 and M2 accept. So the language of M is the union of L1 and L2. We see too that M is a deciding DTM that halts in polynomial time. So L is in the class P.
- Composition? This is pretty easy. Do something similar to my serial approach for the union.
- Complement is easy. Just reverse accept and reject states.
- 7.7: Very much like above, but NTMs instead of DTMs. Also, notice
that the argument for complementing fails. You should understand why at this
point. Remember that at NTM accepts if and only if one of the paths through
the configuration tree leads to an accepting configuration.
Switching accepting state and rejecting state doesn't produce the complementary
language in general.
- 7.8: Following my hint, we take an input string that looks like
1111111...111 and extend it to look like
1111111...111 11 by adding a blank followed by two ones, and then color the initial ones of both strings of ones to get
1111111...111 11. Then do the usual stuff to advance both to get
1111111...111 11. Then detect that you hit the end of the string on the right. So reset things for the right string while advancing in the left string to get
1111111...111 11. Then advance both again to get
1111111...111 11. And so forth. In this way, you will discover if the length of the original string is divisible by 2. If not, then add another 1 to the end of the right string to get
1111111...111 111. Use this to figure out if the length of the input string is divisible by 3. So the testing would proceed something like this:
1111111...111 111
1111111...111 111
1111111...111 111
1111111...111 111
1111111...111 111
1111111...111 111
and so forth. If the input string's length is not divisible by 3, then go on to test divisibility by 4 (I know a waste of time, but do so to keep things simple). And so forth. As soon as the length of the right string equals the length of the left string, and assuming that the length of the left string has not been found to be divisible by the length of the right string at any point prior to this, halt accepting. If any divisibility has been detected, then halt rejecting instead. Now if the length of the input string is denoted by n, then the above will need to check for divisibility by 2, 3, 4, 5, ..., n-1, which means n-2 tests (at most). Let's be sloppy and say n tests. Each requires advancing the color in the left string and n such advances are required. Each of these also requires changing the color in the second string, causing movement between the two strings that might take up to 4n steps to complete (2n moves right and 2n moves left). Now n times n times 4n equals 4n3. So the whole time won't take more than O(n3) steps.
- 7.10: Suppose we encode a graph G with k vertices as a binary string < G > of length n. So k <= n. We basically need the Turing Machine to execute the nesting of three loops, where each loop would iterate over the k different vertices. Inside all of these loops you could check to see if the three vertices are distinct and then have another loop that passes through < G > to see if there is an edge between each of the three pairs formed from these three vertices. This four-way nesting of loops should convince you that the time complexity of the Turing Machine is not any worse than O(n4).
