Chapter 15. Hierarchy Of Models (iii)

Hierarchy of the Models

1

Review

Chomsky Hierarchy

Languages (grammars) Recursively Enumerable Sets (type 0) Context-sensitive Languages(type 1)

Machines Turing Machines (TM)

Linear-bounded Automata (LBA)

Context-free Languages(type 2)

Pushdown Automata (PDA)

Regular Languages(type3)

Finite State Automata (FA)

Other Models Post System, Markov Algorithms, µ -recursive Functions . . . ↓ : Containment . ↔ : Characterization . * Colored arrows indicate proven relations. Regular Expression 2

15. Hierarchy of the Models: Final Proof In Chapters 7 and 12, respectively, we have partially proved the characterization relations and the containment relations in the hierarchy of languages and automata (i.e., Chomsky hierarchy, repeated in the preceding slide, where the colored arrows indicate proven parts). This chapter introduces two additional interesting classes of languages into the hierarchy. One is the class of languages that cannot be recognized by any TM, and the other is the class of languages that can be recognized by a TM that eventually halts. (These languages are called recursive languages.) Then the chapter completes the proof of the hierarchy including these new classes of languages. The proofs are quite challenging for undergraduate students. However, it is worth the challenge because the techniques involve elegant logic that can be followed with the knowledge that we have learned in Chapter 1.

15.1 Languages that TM’s cannot recognize 437 Enumeration Enumerating TM’s 15.2 Universal TM 448 15.3 Enumerable Languages 450 15.4 Recursive Languages 459 15.5 Proof of characterizations 471 Type 0 grammar and TM CSG and LBA CFG and PDA Rumination 506 Exercises 507

3

Hierarchy

15.1 Languages that TM’s cannot recognize At the top level of the Chomsky hierarchy, there are type 0 languages. In this chapter we will prove that every language is type 0 if and only if it is recognizable by a TM. Before we prove this characterization, we may ask the following question. Is there a language that cannot be recognized by a TM? The answer is positive. We will first prove this answer. A popular approach that we will use in this chapter is the diagonalization technique introduced in chapter 1. This technique requires an enumeration (i.e., listing out) of all possible target objects, such as certain types of grammars, automata, or strings. Before using the diagonalization technique for the proof, we need to formally define the term enumeration. Definition 15.1(Enumeration). For a given set S, to enumerate S is to list out every element in S on a line, and we call a TM that is capable of enumerating a set an enumerator. If a set is enumerable, then we call it an enumerable set. For example, the set of positive integers and the set of character strings on a finite alphabet are enumerable, because we can build a TM that lists all the elements of the sets on its tape (see the illustration on the next page). Notice that because these sets are infinite, the enumerator never stops. 4

Non-type 0 Languages

Hierarchy

The figure below shows how we can build a TM which enumerates the set of positive integers in binary. (The set ∑*, for a finite alphabet ∑, is also enumerable because we can build a TM which enumerates the set in lexicographic order.)

Write 1 on the blank tape start (B, 1, R)

Write a copy of the rightmost number in the list to its right, separated by two cells.

Increment the copy by one

Enumerable sets are also called countable, because all the elements in an enumerable set are countable, i.e., they can be put to one to one correspondence with the set of positive integers. There are uncountable sets. The following theorem shows an example. 5

Hierarchy

Non-type 0 Languages

Theorem 15.1 For a given finite alphabet ∑, the sets of all languages in ∑ (i.e., the set of all subsets in ∑*) is not enumerable. Proof. We use the diagonalization technique. Suppose that all the languages in ∑* are enumerable, i.e., we can list them out along an infinite line. Let Li be the i-th language in the list. As illustrated in the figure below, consider a matrix M, where M[i, j] = 1, if wi is in language Lj, otherwise, M[i, j] = 0. (Notice that this is a conceptual setting. We don’t actually have to construct the whole matrix.) L 1 L2 L 3 L 4 L 5 . . . w1

0

1

0

1

1

w2

1

1

0

0

1

w3

1

0

1

1

0

w4

0

1

1

0

0

. .

M 6

Hierarchy

Non-type 0 Languages

Now, with the diagonal entries we construct a language LD defined as follows. LD = {wi | M[i, i] = 0} We claim that LD is a language that does not exist in the list. Suppose that i-th language Li = LD. If wi ∈Li, then wi ∉ LD. Otherwise, if wi ∉ Li, then wi ∈ LD. It must be that Li ≠ LD. Notice that this proof holds even for the singleton alphabet, for example, Σ = {a}. L 1 L2 L 3 L 4 L 5 . . . w1

0

1

0

1

1

w2

1

1

0

0

1

w3

1

0

1

1

0

w4

0

1

1

0

0

. .

M 7

Non-type 0 Languages

Hierarchy

Enumerating all TM’s Now we go back to the question of whether there is a language that cannot be recognized by any TM. We learned that for a given alphabet Σ , the set of languages in Σ * is not enumerable. If we can show that the set of all TM’s is enumerable, then we prove that there is a language that cannot be recognized by any TM, because for every TM, there is only one language that the machine recognizes. Let M = (Q, ∑, Γ , δ , q0, F) be a TM, where Q, Γ and ∑ ⊆ Γ are, respectively, the set of states, the tape alphabet, and the input alphabet, all finite. We assume that M has only one accepting state, i.e., |F| = 1 and ∑ = {a, b}. (Once in an accepting state, the TM’s do not have to move. Hence, all accepting states can be merged into a single state without affecting the language accepted by a TM. See the rumination section at the end of Chapter 4.) We may use other alphabet sizes, but 2 are enough for our proof. Notice that to list all TM’s accepting languages in ∑*, we must consider all possible finite sets of states and tape alphabets. Here, the finiteness implies that the size is fixed for a given TM, but there is no upper bound. Thus, there are infinitely many TM’s, each recognizing a language in {a, b}*. If they are enumerable, how can we list them with an enumerator? 8

Non-type 0 Languages

Hierarchy

With no loss of generality, assume that every TM uses a finite number of state names and the tape alphabet, respectively, chosen from the left end of the following lists (pool) of state names and tape alphabet. (Notice that both lists are infinitely long.) As usual, we will use R, L, N for the direction of the tape head move. pool of state names: {q0, q1, q2, . . . . } pool of tape alphabet: {t0, t1, t2, . . . . . } direction of a move: {R, L, N} We further assume that q0 is the start state, q1 is the accepting state, t0 is the blank symbol (B), t1 = a, and t2 = b. (Recall from the ruminations at the end of Chapters 4 and 5 that every TM can accept its language with one accepting state.) Finally, we chose a format to describe the state transition function δ . For example, we may list δ , as follows. δ (q0, a) = (q2, b, R); δ (q2, a) = (q5, a, L); δ (q0, b) = (q3, b, R); . . . . .

9

Non-type 0 Languages

Hierarchy

For simplicity, let’s delete the parentheses and commas from the list as follows. The transition function in conventional notation: δ (q0, t1) = (q2, t2, R); δ (q2, t2) = (q5, t1, L); δ (q0, t2) = (q3, t3, R); . . . . . The transition function in abbreviated notation: q0 t1 =q2 t2R;q2 t2=q5 t1L;q0 t2=q3 t3R; . . . . . In this shortened list, every transition consists of six symbols and is delimited with a semicolon. Though poorly legible, it carries the same information as the original list. We are going to represent a TM’s transition function δ written in this format. Recall that once all the symbols in the set of states Q, input alphabet Σ , tape alphabet Γ , the start state q0, and the accepting state in F are defined, we can uniquely represent a TM only with the transition function δ (or with the state transition graph). We will use this list for the convenience of converting it into a binary number in the next step.

10

Hierarchy

Non-type 0 Languages

Let E be an encoding function (i.e., homomorphism) such that given a symbol used in the transition function of a TM, E returns a binary code as follows. E(;) = 010, E(=) = 0120, E(L) = 0130, E(R) = 0140, E(N) = 0150, E(qi) = 016+2i 0, E(ti) = 017+2i 0, i ≥ 0. Notice that every binary code is uniquely identified by the number of 1’s between the two 0’s. State codes have an even number of 1’s and tape symbols an odd number of 1’s. Here are some examples of the binary encoding according to the above encoding function E. q0t1=q2t2R; q2t2=q5t1L; q0t2=q3t3R;

0160019001200110 00111 00140010 0110 00111 001200116 001900130010 01600111 001200112 00113 00140010

We extend function E such that, given a TM M, E(M) gives the binary encoding of M’s transition function δ according to the above definition. 11

Hierarchy

Non-type 0 Languages

It is possible to construct a TM MD that, given a binary string w, decides whether w is a binary encoding E(M) of a TM M or not. MD simply checks whether every substring in w delimited by 010 (the code for ;) is the binary encoding of a transition pa=qbX for some states p and q, some tape symbols a and b, and X ∈ {R, L, N}, each belonging to the sets we have defined. Now, we are ready to construct an enumerator TE (i.e., a TM) that lists all TM’s on its tape, M0, M1, M2, …. To do this, our enumerator TE generates the binary numbers on the tape in the order of their length and value; 0, 1, 00, 01, 10, 11, . . . , one by one, checking whether the current binary number written on the tape is the binary encoding of the transition function of a TM. If it is, the enumerator generates the next binary number to the right. Otherwise it erases the number before the next number is written. The enumerator repeats this process forever. Since for every TM M, the length of E(M) is finite, E(M) will eventually appear on the list. M0, M1, M2, . . . , Mi . . . TE 12

Non-type 0 Languages

Hierarchy

Now, we can claim the following theorem. Theorem 15.2 The set of all TM’s, each encoded by the function E, are enumerable. The binary encoding function E is one-to-one function, i.e., no two TM’s can be encoded to the same binary number. For each TM M, there is only one language accepted by M. Thus, the fact that all TM’s are enumerable implies that all TM languages are enumerable. (Since a language can be recognized by more than one TM, a language may appear in the enumeration multiple times.) Corollary. The set of all type 0 languages on a given finite alphabet ∑ is enumerable. Type 0 languages are also called recursively enumerable (R.E.) languages. By Theorem 15.1, we know that for a given finite alphabet ∑, it is impossible to enumerate all languages in ∑*. With this theorem and the above Corollary, we can claim the following theorem. Theorem 15.3 Let ∑ be a finite alphabet. There is a language in ∑* that cannot be recognized by a TM.

13

Non-type 0 Languages

Hierarchy

Notice that this theorem also holds for a singleton alphabet, for example ∑ = {a}. The same binary encoding technique that we have introduced for TM is also applicable to grammars and other automata. Thus, we can also claim the following. Theorem 15.4 The set of all binary encoded CSG’s is enumerable.

Life

Break Time

- We make a living by what we get, we make a life by what we give. - Sir Winston Churchill - Life is something that happens when you can’t get to sleep. - Fran Lebowitz – - Life is something that everyone should try at least once. - Henry J. Tillman - Life is pleasant. Death is peaceful. It’s the transition that’s troublesome. - Isaac Asimov – - Life is what happens to you while you’re busy making other plans. - John Lennon – - The secret of a good life is to have the right loyalties and hold them in the right scale of values. - Norman Thomas -

14

Hierarchy

15.2 Universal TM Definition 15.2 (Universal TM). We call a TM Tu universal, if Tu, given an arbitrary TM M and an input x, simulates the computation of M on the input x. Here is an idea of how to construct a universal TM Tu. The input M and x given to Tu must be represented according to an agreed format. Suppose that they are binary encoded as E(M) and E(x), using the same function E that we developed in the previous section. TU records E(M), E(x), the current state E(qi) of M and the head position as the following figure illustrates. Using this information on its tape, Tu follows M’s moves one by one. If M enters an accepting state, so does Tu. If M meets a transition undefined, Tu terminates the simulation. E(M) E(x) E(qi) Head position

Tu 15

Hierarchy Universal TM A TM M recognizes only its language L(M). Thus M is a special purpose computer built to recognize L(M). In contrast, the universal TM is a general purpose computer in the sense that, given E(M) and E(x), the machine gives the result of the computation of M on input x. Here E(M) and E(x) correspond, respectively, to a program and an input represented in an agreed form, i.e., a programming language.

Break Time

Science & Research The whole science is nothing more than a refinement of everyday thinking.

- Albert Einstein –

Research is of mind, not of hands, a concentration of thought and not a process of experimentation. Research is the effort of the mind to comprehend relationships which no one had previously known. - DeForest Arnold -

16

Hierarchy

15.3 Enumerable Languages Now, we turn our attention from the topic of enumerating the sets of automata and languages to enumerating a language itself. We first prove the following theorem, which claims that enumerability is another characterization of type 0 languages. Theorem 15.5 (1) If a language L is enumerable, then L is a type 0 (R.E.) language. (2) If a language L is type 0 (R.E.), then L is enumerable. Proof (1). Let Me be a TM (i.e., enumerator) that enumerates L. With Me we can build a 2-tape TM M recognizing L as follows. Given an input x, using Me in its finite state control, M writes the next string wi in the enumeration and checks whether x = wi. If it does, M enters an accepting state and halts. Otherwise, it writes the next string wi+1 in the enumeration and repeats the process. M accepts x if and only if x ∈ L. x Me TM M wi 17

Enumerable Languages

Hierarchy

Proof (2). This part of proof is not as simple as the proof for part (1). Let M be a TM recognizing L. We build an enumerator Me for L with M. Let ∑ be the alphabet of language L. We may think of the following straightforward idea. We let Me, while writing the strings wi ∈ ∑* in the lexicographic order on one of its tape tracks, check whether wi is accepted by M. If it is accepted, we let it be the next string in the enumeration. Otherwise, we erase it and repeat the process with the next string in ∑*. There is a serious problem with this idea. What will happen to Me, if M enters an infinite loop without accepting wi? We cannot make Me not to put wi in the enumeration, because it is impossible for Me to decide whether M will eventually halt or not (i.e., it is an unsolvable decision problem). Thus, the idea fails. w1

w2

w3

w2

w4

w7

w4 . . . . . ...

accepted strings TM M

enumerated strings in ∑*.

Me 18

Hierarchy

Enumerable Languages

So we need a different approach. As before, while enumerating the strings in ∑* one by one in the lexicographic order, we let Me progressively simulate the computation of M on input w1, w2, . . ., as the figure below illustrates. We let Me, writing w1, simulate the first move of M on w1. Writing w2, we let it simulate the first move of M on w2 followed by the second move on w1. Writing w3, we let it simulate the first move of M on w3 followed by the second move on w2, followed by third move on w1, and so on. Any string accepted during this procedure is moved onto the lower track (not shown), and we let it be the next string in the enumeration. w1 w2 w3 w4 . . . .

steps

1•

•

•

2•

•

•

3•

•

•

4•

. .

TM M

Me 19

Enumerable Languages

Hierarchy

According to Church’s hypothesis, no computational model exists that is more powerful than Turing machines. In other words, any computational model computes at best what Turing machines can compute. Then we may ask the following. Is there any limit on what Turing machines can compute? We learned a proof that for a given alphabet ∑, there is a language in ∑* that cannot be recognized by any TM. This proof is non-constructive. The proof of the following theorem (constructively) shows a language that cannot be recognized by any TM. Theorem 15.6 Let ∑ be an arbitrary finite alphabet. There is a language in ∑*, that cannot be recognize by any TM. Proof. We know that the set ∑* and the set of all TM’s are enumerable (Theorem 15.2). With these facts, we will prove the theorem using the diagonalization technique. We assume that every TM M and string x ∈ ∑* are, respectively, expressed by the binary encoding E(M) and E(x) that we have introduced in the previous section.

20

Hierarchy

Enumerable Languages

Proof (cont’d). We construct a matrix M such that for every i ≥ 0, the i-th row corresponds to the i-th string wi , and the i-th column corresponds to the i-th TM Mi in the enumeration. This is possible because the set of TM’s and the set ∑* are both enumerable. For the matrix entries, we let M[i, j] = 1, if Mj accepts string wi. Otherwise, we let M[i, j] = 0. Now, we claim that no TM recognizes language L0 below, which contains string wi , if i-th TM Mi in the enumeration does not accept i-th string wi. M0 M1 M2 M3 . . . . w0

0

1

1

1

0

w1

1

1

0

0

1

w2

1

0

0

0

0

w3

0

0

1

1

1

w4

1

1

1

0

0

L0 = { wi | M[i, i] = 0, i ≥ 0 }

. M 21

Hierarchy

Enumerable Languages

Suppose that there is a TM, say Mi in the enumeration, that recognizes L0. (We are using the proof-by-contradiction technique.) Consider what will happen if we give ith string wi as an input to Mi. (Notice that Mi and wi have the same subscript.) Either wi ∈ L0 or wi ∉ L0. We examine these two cases. (1) When wi ∈ L0. By definition of the matrix, this case implies that M[i, i] = 0, i.e., Mi does not accept wi. It follows that wi ∉ L(Mi) = L0. We have a contradiction. (2) When wi ∉ L0. By definition, the case implies that M[i, i] = 1. That is, Mi accepts wi. It follows that wi ∈ L(Mi) = L0. Again, we have a contradiction. So we should give up the assumption that L0 = L(Mi), for some i ≥ 0. No TM exists that recognizes L0. Language L0 is not type 0 (R.E.). M0 M1 M2 M3 . . . . L0 = { wi | M[i, i] = 0, i ≥ 0 } = { w0, w2, w4 , . . . }

w0

0

1

1

1

0

w1

1

1

0

0

1

w2

1

0

0

0

0

w3

0

0

1

1

1

w4

1

1

1

0

0

.

22

Hierarchy

Enumerable Languages

Now, consider L1 = {wi | M[i, i] = 1 }, which is the complement of L0 (see below). We will show that in contrast to L0, language L1 is R.E., i.e., type 0. Theorem 15.7 L1 is a type 0 (R.E.) language. M0 M1 M2 M3 . . . . w0

0

1

1

1

0

w1

1

1

0

0

1

w2

1

0

0

0

0

w3

0

0

1

1

1

w4

1

1

1

0

0

L1 = { wi | M[i, i] = 1, i ≥ 0 } = { w1, w3, . . . }

.

23

Hierarchy

Enumerable Languages

Proof. We construct a TM MD that recognizes L1 as follows. Suppose an input x is given to MD. MD is equipped with two enumerators, the one enumerating the set of all strings in ∑* and the other enumerating the set of all TM’s (see the figure below). MD alternately enumerates M0, w0, M1, w1, . . . on its two extra tapes until TM Mi and wi (= x) appear. Then MD simulates the computation of Mi on input wi. If Mi accepts x, so does MD, and it halts. (Notice that Mi may run forever without accepting. Then so does MD.) It follows that MD is a TM which recognizes L1. Language L1 is type 0 (R.E.). If x = wi, then simulate Mi with input x.

Mi x

Input tape TM enumerator MD

∑*

enumerator wi 24

Hierarchy

Enumerable Languages Since L0 is the complement of L1, we have the following corollary.

Corollary. There is a type 0 language whose complement is not type 0.

Good life

Break Time

When you were born, you were crying and everyone around you was smiling. Live your life so that when you die, you’re smiling and everyone around you crying, with tears of joy for having known you. - Anonymous -

25

Hierarchy

15.4 Recursive Language The Turing machine model that we have defined halts if the input is accepted by the machine. The definition does not explicitly say what the machine should do if the input is not accepted. The machine may either enter a dead state (if an undefined input symbol is read in a state) or never halt, going around an indefinite loop of non-accepting states. (Recall that for convenience, we do not show transitions entering the dead state.) How about defining a TM model, as the following figure illustrates, which after some finite number of moves, always halts in either an accepting state or a nonaccepting state? Such TM’s and their languages are called recursive. (a, b, N) Reject and halt

Recursive TM

(c, a, N)

Accept and halt 26

Recursive Languages

Hierarchy

This model could be more user friendly than the original one. We may let it output a kind message before halting, like “Yes, I accept the input!” or “No, I regret that I have to reject it.” For the original TM model, it is impossible to give any specific message when it does not accept the input because there is no way to know whether it will enter an infinite loop or not. Interestingly, we will show that the recursive (i.e., halting) TM model is weaker than the original model in the sense that there is a type 0 language that cannot be recognized by any recursive TM. Before we show the proof, we define the following. Definition 15.3 (Recursive TM, Recursive Language). A recursive TM is a TM that eventually (i.e., after a finite number of moves) halts in either an accepting or a non-accepting state. The language accepted by such TM is called a recursive language. In contrast to type 0 languages, the following theorem claims that the complement of recursive languages are also recursive.

27

Hierarchy

Recursive Languages

Theorem 15.8 The complement of a recursive language is also recursive. Proof. Let L be a recursive language accepted by a recursive TM M. We simply change the accepting states of M to non-accepting states, and vice versa. This modified TM accepts the complement of L. Let Type-Rec be the class of recursive languages. We know that every recursive language is type 0. According to the Corollary of Theorem 15.7, there is a type 0 language whose complement is not type 0. Thus, Theorems 15.7 and 15.8 above implies the following theorem. Theorem 15.9 Type-Rec is properly contained in Type-0L.

Type-0L

Type-Rec

28

Hierarchy

Recursive Languages

Now that the top level (i.e., type 0) of Chomsky hierarchy has been refined, we move down to the next lower level (i.e., type 1). We will first prove Theorem 15.10 below, which claims that every context-sensitive language is recursive. Then using this theorem and Theorem 15.9, we will show that Type-1L ⊂ Type-0L. Theorem 15.10 Every context-sensitive language is recursive. Proof. Let G = (VT, VN, P, S) be an arbitrary context-sensitive grammar. We construct a recursive TM M that recognizes L(G) as follows. M has a two-track tape with G stored in its finite state control and the input is given on the top track, as the following figure illustrates. The idea is to let M, using G, nondeterministically generate a terminal string on its second track and see whether it is equal to x. If it is, M accepts x and halts. Otherwise, M rejects it and halts. x S => . . . . => x ? TM M

G 29

Hierarchy

Recursive Languages

On its lower track M writes a derivation sequence, i.e., a sequence of sentential forms, w0, w1, w2, . . ., that can be derivable starting with the start symbol S of G as the figure below illustrates. In the list w0 = S, and w1 is a sentential form that can be generated by applying a rule of S, string w2 is generated by applying a rule whose left side is a substring in w1, and so on. If wi contains more than one substring corresponding to the left side of some rules of G, then M nondeterministically chooses one of the substrings to apply its rule. If the chosen substring has more than one rule (for example, bA → Ab |ba), M nondeterministically chooses one of those rules. M repeats this procedure until it sees that one of the following conditions is satisfied. (1) wi = x,

(2) wi = wj, i < j ,

S⇒

Recursive TM M

(3) (|wi| > |x|) OR (wi ∈ (VT)+ AND wi ≠ x)

w1

x ⇒

w2

⇒. . .

G 30

Recursive Languages

Hierarchy

If condition (1) is satisfied, M halts in an accepting state. Case (2) implies that the derivation got into a loop. So, M halts in a non-accepting state. Case (3) implies that according to the non-contracting property of context-sensitive grammar rules, it is impossible to derive string x. Thus in this case too M halts in a non-accepting state. M is a recursive (i.e., halting) TM that recognizes L(G). It follows that every contextsensitive language is recursive. Now, we may ask the following question: Is the converse of Theorem 15.10 true? (That is, is every recursive language context-sensitive?) In terms of automata, this is equivalent to the question of whether every language recognized by a recursive TM can also be recognized by an LBA. The next theorem shows that there is a recursive language that is not context-sensitive.

31

Hierarchy

Recursive Languages

Theorem 15.11 There is a recursive language that is not context-sensitive. Proof. Again, we will use the diagonalization technique. We know that the set of all CSG’s with terminal alphabet VT = {a, b} is enumerable (see Theorem 15.4). As illustrated below, construct a matrix M such that i-th column corresponds to the i-th grammar Gi in the enumeration, and i-th row corresponds to the i-th string wi ∈ {a, b}* in the lexicographic order. For the entries of the matrix, we let M[i, j] = 1, if wi ∈ L(Gj). Otherwise, M[i, j] = 0. We have L(Gi) = { wj | M[j, i] = 1, j ≥ 0}. G0

G1

G2

G3 . . . .

w0

0

1

1

1

0

w1

1

1

0

0

1

w2

1

0

0

0

0

w3

0

0

1

1

1

w4

1

1

1

0

0

.

32

Hierarchy

Recursive Languages Now, going along the diagonal of matrix M, we pick all wi ∉ L(Gi) and construct the language L0. G0

G1

G2

G3 . . . .

w0

0

1

1

1

0

w1

1

1

0

0

1

w2

1

0

0

0

0

w3

0

0

1

1

1

w4

1

1

1

0

0

L0 = { wi | M[i, i] = 0, i ≥ 0 } = { w0, w2, w4, , , , }

. We first prove that L0 is not context-sensitive. This proof is very similar to the one of Theorem 15.3, where we showed a language that cannot be recognized by any TM. Suppose that L0 is a language of a CSG Gi, i.e., L0 = L(Gi). Consider the string wi. (Notice that wi and Gi have the same subscript.) Either wi ∈ L0 or wi ∉ L0. We examine each of these cases.

33

Hierarchy

Recursive Languages

(1) Case of wi ∈ L0: By the definition of L0, we have M[i, i] = 0, which implies that wi ∉ L(Gi) = L0 . We are in a contradiction. (2) Case of wi ∉ L0: Again by the definition of L0, we have M[i, i] = 1, which implies wi ∈ L(Gi) = L0. Again, we are in a contradiction. So we must give up the supposition that L0 = L(Gi). Language L0 is not contextNow, we will show that L0 is recursive. The proof is similar to the proof of Theorem sensitive. 15.7. We construct a recursive TM M0 which recognizes L0 as follows. Suppose that on the input tape of M0, a string x is given. Gi x

CSG enumerator M0

∑* enumerator wi 34

Hierarchy

Recursive Languages

The machine M0 has two enumerators, one for the set of context-sensitive grammars, and another for the set ∑ *. Using these two enumerators, M0 keeps alternately generating grammars and strings on two tapes as shown below, until wi appears, that is equal to x. Then M0 tests whether Gi can derive x using the idea presented in the proof of Theorem15.10. If this test shows that Gi can derive x, M0 rejects the input x and halts. Otherwise, M0 accepts x and halts. It follows that M0 is a recursive TM that recognizes L0. Language L0 is recursive. Gi x

CSG enumerator M0

∑* enumerator wi

35

Recursive Languages

Hierarchy

In this chapter we have introduced two additional classes of languages, i.e., the class of recursive languages and the class of languages that are not type 0, and we have identified their level in the Chomsky hierarchy. The one is the class of languages that cannot be recognized by any TM, and the other is the set of languages recognized by recursive TM’s. The next page shows the Chomsky hierarchy, including the class of recursive languages. (The class of non-type 0 languages is not shown.) In the figure the red arrows show the characterization relations ( ↔ ) and the proper containment relations (↓) that we have proved so far.

Funny ads

Break Time

- Dinner Special: Turkey $2.35; Chicken or Beef $2.25; Children $2.00. - For Sale: Antique desk suitable for lady with thick legs and large drawers. - Now is your chance to have your ears pierced and get an extra pair to take home too! - No matter what your topcoat is made of, this miracle spray will make it really repellent. - Dog for Sale: Eats anything and is fond of children. - Tired of cleaning yourself? Let me do it! - Jason -

36

Hierarchy

Chomsky Hierarchy Languages

Automata

Recursively Enumerable Sets (type 0)

Turing Machines

Recursive Languages Context-sensitive Languages(type 1)

Recursive Turing Machines Linear-bounded Automata

Context-free Languages(type 2)

Pushdown Automata

Regular Languages(type3)

Finite State Automata

↓ : Containment ↔ : Characterization * Colored arrows indicate proven relations. Regular Expression 37

Hierarchy

15.5 Proofs of Characterizations Now, finally, we will complete the proof of Chomsky hierarchy by proving the top three characterization relations between the types of grammars and automata. Since there is no known class of grammars that generate recursive languages, no proof for characterization is given for this level.

Type 0 grammars and the Turing machines Theorem 15.12 (1) Every language generated by a type 0 grammar can be recognized by a TM. (2) Every language recognized by a TM can be generated by a type 0 grammar. Proof (1). Let G be an arbitrary type 0 grammar, and let {α 1, α 2, . . , α n} be the set of strings used for the left side of the rules of G. Let {β i1 , β i2 , . . β ik } be the set of strings appearing on the right side of rule α i, i.e., α i →β

i1

|β

i2

|, . . , | β

ik

(Notice that n and k are some finite integers.) We construct a TM M that recognizes L(G) as follows. M has G in its finite state control stored as a look-up table. 38

Hierarchy

Proofs of Characterizations

Suppose that a string x is given on its input tape as illustrated in the figure below. The machine M, using an extra work tape, tests whether x can be derived by grammar G. M starts the work by writing the start symbol S on the work tape. Suppose w is a sentential form that can be derived starting with S. M, reading w from left to right, nondeterministically chooses a substring α i and replaces it with one of its right side β ij , also chosen nondeterministically. M repeats this process until it sees that the current sentential form w is equal to the input string x and, if it is, M halts in an accepting state. Notice that if x ∉ L(G), M may repeat the process forever or see a sentential form w on which no rule is applicable and halt. M accepts x if and only if it is generated by G. It follows that M recognizes L(G), and hence, every type 0 language is recognized by a TM. x

x

x

G

G

input G α

S

i

β

ij

x

?

G x

work tape 39

Type 0 Grammar ↔ TM

Hierarchy

Proof (2). For the proof, let M = (Q, ∑, Γ , q0, δ , F) be an arbitrary TM. We construct a type 0 grammar G that generates L(M). Let Q = {q0, q1, . . , qn}, and qf ∈ F. For the construction we shall use two distinct symbols #, $ ∉ Γ . Grammar G generates L(M) in the following three phases (see the figure below): (1) for an arbitrary string x ∈ Σ *, grammar G generates string x#q0x$. (2) Starting with the start state q0, G simulates M’s computation on input x using the string x generated to the right of q0 in the first phase. (3) If M enters the accepting state qf in the second phase, G erases all symbols except the left side x generated in the first phase. We will show how G carries out the three phases. According to the convention of using upper case letters for the nonterminal symbols of a grammar, we shall use Qi instead of state qi. In the figure below, strings u and v concatenated corresponds to the final tape content of M when it accepts x. (2) (3) (1) S ⇒ . . . ⇒ x#Q0x$ ⇒ . . . . ⇒ x#uQfv$ ⇒ . . . . ⇒ x

40

Hierarchy

Type 0 Grammar ↔ TM

(2) (3) (1) S ⇒ . . . ⇒ x#Q0x$ ⇒ . . . . ⇒ x#uQfv$ ⇒ . . . . ⇒ x Let ∑ = {a1, a2, . . . , ak} be the input alphabet of M. The following set of rules carries out phase (1) to generate the string x#Q0x$, for every x ∈ ∑*. Notice that for x = ε , the rules generates #Q0$. S → A$ A → a1Aa1 | a2Aa2 | . . .

(1) S ⇒ . . . ⇒ x#Q0x$

| akAak | #Q0

41

Hierarchy

Type 0 Grammar ↔ TM (2) (3) (1) S ⇒ . . . ⇒ x#Q0x$ ⇒ . . . . ⇒ x#uQfv$ ⇒ . . . . ⇒ x

For phase (2), we set up a one-to-one correspondence between G’s sentential forms and M’s configurations as the following figures illustrate. Symbol a ∈ Γ is positioned to the right of Qi in a sentential form of G, if and only if M reads a in state qi (figure (a)). Symbol $ (symbol #) is to the right of Qi in a sentential form of G, if and only if M, in state qi, reads the blank symbol next to the right end (respectively, to the left end) of the current tape contents (figures (b) – (d)). ...

. . . bQia . . .

b a

..

qi

(a)

a .. ..

. . . Qi# a . . qi (c)

a .. ..

. . . #Qia . .

qi

(b) ... a

. . . aQi$ . . . (d)

qi 42

Hierarchy

Type 0 Grammar ↔ TM

Depending on M’s transitions, we design G’s rules as follows. Part (a) below is for the case of M reading a non-blank symbol a, and part (b) is for the case of reading the blank symbol next to either end of the current tape contents. Grammar G uses two special symbols $ and # as boundary markers, respectively, to expand its sentential form to the right and to the left to accommodate M’s current tape contents. (a) M’s transition: δ (qi, a) = (qj, b, D)

G’s rule (where c ∈Γ ∪ {#} ):

if D = R,

cQia → cbQj

if D = L,

cQia → Qjcb

if D = N.

cQia → cQjb

(b) M’s rule: δ (qi, B) = (qj, b, D)

Qi# → #bQj

if D = R, if D = L, if D = N,

G’s rule (where c ∈Γ ):

Qi# → Qj#b

Qi$ → bQj$

#Qi$ → Qj#b$

cQi$ → Qjcb$

Qi# → #Qjb

Qi$ → Qjb$ 43

Hierarchy

Type 0 Grammar ↔ TM (2) (3) (1) S ⇒ . . . ⇒ x#Q0x$ ⇒ . . . . ⇒ x#uQfv$ ⇒ . . . . ⇒ x

It is simple to design a set of rules for phase (3). By the two rules in (a) below, we let the nonterminal symbol Qf, which denotes the accepting state of M, move to the right till it meets $. Then by the rules in part (b), we let QE keep moving to the left and erasing every symbol it meets up to and including #. For every symbol a ∈Γ , include the following rules in G. (a) Qf# → #Qf

Qfa → aQf

(b) Qf$ → QE

aQE → QE

#QE → ε

Grammar G is type 0, and it derives a string x if and only if x is accepted by M. We proved that L(G) = L(M). It follows that every language recognized by a TM can be generated by a type 0 grammar. 44

Hierarchy

CSG and LBA

Now, we prove the characterization relation between CSG’s and LBA’s. The approach is similar to the one for the characterization between TM’s and type 0 grammars that we have just completed. For the proof we should take into consideration of two restrictions: the tape space of an LBA is bounded by the input length, and the grammar rules are non-contracting. Theorem 15.13 (1) Every language generated by a CSG can be recognized by an LBA. (2) For every language L recognizable by an LBA, there is a CSG G such that L(G) = L – {ε }. Proof (1). The LBA uses a two-track tape, instead of two tapes, to conveniently limit the tape space. If the LBA sees that next sentential form derived can be longer than x, it stops the derivation and rejects the input string x, because it is impossible to derive x by applying non-contracting CSG rules. input [

x

[S ]

]

[ [

G

x α

i

] ] G

[

?

[

x β

] ]

ij

G

[

x

[

x

] ] G 45

CSG ↔ LBA

Hierarchy

For the special case; when the input is ε (i.e., the tape has []), the machine enters an accepting state, if the grammar has the rule S → ε . (The details are omitted.) Proof (2). Suppose L is the language of an LBA M = (Q, Σ , Γ , δ , q0, [, ], F) , where Q = {q0, q1, …., qm}, and Σ = {a1, a2, …., ak}, for some constants m and k. For the proof we will construct a CSG G such that L(G) = L(M) – {ε }. For the construction, we will be inclined to use the same three-phase approach (repeated below) that we used to construct a type 0 grammar which can derive all the input string x accepted by a TM. (2) (3) (1) S ⇒ . . . ⇒ x#Q0x$ ⇒ . . . . ⇒ x#uQfv$ ⇒ . . . . ⇒ x However, we have a problem to follow this approach because CSG rules are noncontracting. Reviewing the type 0 grammar rules for the three-phase procedure, we find that among the rules for phase (3) (repeated below), all the rules in line (b) are contracting. These rules are used to erase the tape, leaving only the accepted input string x. (a) Qf# → #Qf Qfa → aQf (b) Qf$ → QE aQE → QE #QE → ε 46

Hierarchy

CSG ↔ LBA

To overcome this problem, instead of generating two copies of x in phase (1), we merge them into one with composite symbols as shown below. Let x = x1x2 . . . xn be the input string. CSG G derives the following sentential form, where each part delimited by either the angled brackets ‘<‘ and ‘>’ or the parentheses ‘(‘ and ‘)’ is a composite symbol, and ‘[‘ and ‘]’ are the input boundary markers. <x1, q0, ( [, x1 )><x2, x2> . . . . <xn, ( xn, ] )> Now, we are ready to show how G can derive the string x if and only if M accepts it. After deriving a sentential form of the above format, CSG G begins to “simulate” the computation of M on the string [x1x2 . . . xn] going along the sentential form of composite symbols. The leftmost elements in the composite symbols delimited by the angled brackets are reserved for the final derivation when M accepts the input. Seeing that M is in an accepting state, G erases all symbols in the current sentential form except for the reserved input symbols, consequently, deriving the input string x = x1x2 . . . xn.

47

Hierarchy

CSG ↔ LBA <x1, q0, ([, x1)><x2, x2> . . . . <xn, (xn, ])>

Below (1) – (4) are the rules for deriving all possible sentential forms shown above. (Recall that in the above sentential form, xi is a member of the input alphabet Σ = {a1, a2, …., ak}.) The rules in line (2) are to generate the initial sentential forms of all possible input strings of length one. We need the rule in line (5) for the case when M accepts ε . Notice that we can safely add this rule because no rule has S on its right side. (Recall that CSG’s are allowed to use this contracting rule under the condition that no rule has S on its right side.) (1) S → A | A | . . . | A (2)

| | | . . . |

(3) A → A | A | . . . | A (4)

| | | . . . |

(5) If the start state q0 is an accepting state, add S → ε . 48

Hierarchy

CSG ↔ LBA

For the simulation, G assumes that M is currently reading (in a state qi) the rightmost element in the composite symbol (delimited by parentheses) appearing next to the right of symbol qi. The following figures show the correspondence between the various contexts involving the state symbol qi in a sentential form and the positions of M’s tape head. (Recall that M doesn’t keep the original input string x and may change it while computing.) <xi, a> ...

a b .. qi

<xn, qi, (a, ])> ... a

<x1, qi, ([, a)> [ a

..

qi <x1, qi, ([, ], a)>

]

[ a ]

qi

qi

<x1, qi, (a, [)> [ a

..

<xn, qi, (], a)> ... a

]

qi

qi <x1, qi, ([, a, ])>

<x1, qi, (], a, [)>

[ a ]

[ a

qi

]

qi 49

CSG ↔ LBA

Hierarchy

Below is the set of rules of G simulating each move of M. The readers are strongly recommended to refer the figures above showing the correspondence between the context of qi and M’s local configuration. M’s transition δ (qi, d) = (qj, e, D) if D = R δ (qi, c) = (qj, d, D) if D = L δ (qi, e) = (qj, d, D) if D = N

G’s rule ( a, b ∈ ∑ , c, d, e ∈ Γ ) → <(a, e)> → → → → → → → 50

Hierarchy

CSG ↔ LBA

Finally, to complete the construction for phase (2), we add the rules shown below for the special cases when M reads the boundary markers. M’s transition

δ (qi, ]) = (qj, ], L)

δ (qi, [) = (qj, [, R)

G’s rule ( a, b ∈ ∑, c, d, e ∈Γ ) → → → →

51

Hierarchy

CSG ↔ LBA

Now, we present below a set of rules needed for the final phase. With qf indicating that M has accepted the input, the grammar erases all the symbols in the sentential form, except for the leftmost elements reserved to generate the input string. Notice that all the rules satisfy the non-contracting condition. (Recall from Section 1.1 that composite symbols are introduced for the matter of comprehension. They are not different from the regular symbols. We are just extending the alphabet size.) In the following rules, a, b ∈ Σ and c, d ∈Γ . (1) → (2) → a (3) a → ba (5) → a

(4) a → ba → a → a

The rule in part (1) keeps shifting qf to right until it sees the rightmost composite symbol. Rule (2) extracts the rightmost input symbol (a in the figure). Rules (3) and (4) let the grammar, going left along the sentential form, collect the reserved input symbols to finally derive the input string accepted by M. Rules in part (5) are for the special cases when the length of the input string is 1. Grammar G derives every string x ∈ Σ * if and only if M accepts it, implying that L(G) = L(M). 52

Hierarchy

CFG’s and PDA’s

Now we finally complete the proofs of the characterizations in Chomsky hierarchy by proving the characterization relation between CFG’s and PDA’s. Theorem 15.14 (1) Every language generated by a CFG can be recognized by a PDA. (2) Every language recognized by a PDA can be generated by a CFG. Proof (1). Let G be an arbitrary CFG. We construct an NPDA M which recognizes L(G) as follows. The basic approach is the same as we took for the proof of the characterization at the upper level. Using G, the machine nondeterministically derives a terminal string x in the stack to match the input string. M starts the work by pushing the start symbol S into the stack and does the following until it sees that the stack is empty. Let A be a nonterminal symbol which has some constant k rules. A → α 1 | α 2 |, . . ., | α

k

(a) If A is at the stack top, M nondeterministically choosed a rule A → α i, 1≤ i ≤ k, popd A, and pushes α i. (b) If a terminal symbol, say a, appears at the stack top, M reads the input and pop the stack top if the input symbol and the stack top match. 53

Hierarchy

CFG ↔ PDA

(c) If the stack is empty (i.e., the stack top is Z0 ), M enters an accepting state. The NPDA M enters an accepting state if G derives the string given in the input tape. It follows that L(M) = L(G). Example: Suppose that CFG G shown in figure (a) below is given. We construct an NPDA as shown in figure (b), which recognizes L(G). Interestingly, we can show that 3 states are enough to construct an NPDA recognizing L(G) for any CFG G.

G:

S → aBC

B → bBc | bc

C → bCc | ε

(ε , S/aBC), (a, a/ε ), (c , c/ε ) (ε , B/bBc), (ε , B/bc), (b, b/ε ) (ε , C/bCc), (ε , C/ε ), (ε , Z0/Z0) 2 (ε , Z0/SZ0)

L(G) = {abncnbmcm | n ≥ 1, m ≥ 0 } (a)

1

(b) 54

CFG ↔ PDA

Hierarchy

Proof (2). This proof is the last and most challenging among the four characterizations between the models for grammars and automata. However, once we understand the underlying concept of the approach, it requires only perseverance. Here again we will present how to construct a CFG G for a given PDA M such that L(G) = L(M). For the proof we assume that M has the following property. (1) M accepts the input by empty stack (i.e., Z0 is popped out from the stack). (2) M pops the stack or pushes it with exactly one symbol. In Section 6.3, we showed that every context-free language can be recognized by a PDA with an empty stack (condition (1)). With an empty stack, no move is possible. So we assume that there is one distinguished state that M enters after emptying the stack. (If there is more than one such state, we can merge them all into one state.) In the rumination section of Chapter 4, we showed that every context free language can be recognized by a DPDA with stack operations restricted to either popping or pushing exactly one symbol in a move (condition (2)). (The same claim is applicable to NPDA’s.) Thus, without loss of generality, we can assume that M meets the two conditions (1) and (2) above. Otherwise, we can modify it without affecting the language. 55

Hierarchy

CFG ↔ PDA

Suppose that M, in a state p, with a symbol A on top of its stack, takes some number of moves until the next stack symbol below A (symbol B in figure (a) below) appears on the stack top for the first time, as shown in figure (b). Let q be the state of M when B appears for the first time on the stack top, but before any operation with B. Notice that B may never appear on the stack top, or the stack height may change many times before B appears. Let [p, A, q], called the stack-top erasing set (STES), denote the set of all input string segments that M will read from the input tape from the time when the machine sees A at the stack top in state p until it first sees B under A, as the following figures illustrate. (Notice that [p, A, q] may be empty.) x p Z0 . . . BA (a)

q Z0 . . . B

[p, A, q] = {x, y, . . } (c)

(b) 56

Hierarchy

CFG ↔ PDA

Figure (a) below shows non-empty STES’s for the PDA in figure (a). Notice that, among many others, [2, A, 5] and [1, Z0, 3] are empty STES’s.

(b, a/ε ) 2 (a, Z0/AZ0) 1

(a, A/aA)

6

5

(b, A/ε )

(b, A/ ε )

7

3

(ε , Z0/ ε )

(ε , Z0/ ε )

4

[5, a, 6] = {b} [6, A, 7] = {b} [7, Z0, 4] = {ε } [2, A, 7] = {ab} [2, A, 3] = {b} [1, Z0, 4] = {aabb, ab}

(a)

(b)

57

CFG ↔ PDA

Hierarchy

Let M = (Q, Σ , Γ , δ , q0, Z0, φ ) be the NPDA. Here is an algorithm for constructing a context-free grammar G = (VT, VN, S, P) such that L(G) = L(M). (1) Let VT = Σ , VN = { [p, A, q] | p, q ∈ Q, A ∈ Γ } ∪ {S} (i.e., the nonterminal alphabet of G consists of all the composite symbols, each denoting an STES of M and the start symbol S. (2) Let t be the state M enters in a move emptying the stack (i.e., Z0 is popped). Put rule S → [q0, Z0, t] in P. (3) Suppose that a rule with a nonterminal symbol [p, A, q] is newly included in P, where p, q ∈ Q, A ∈ Γ . (If there is no such rule, the algorithm terminates.) (a) If M has a move δ (p, a, A) = (r, BC) (where, a ∈ Σ ∪ {ε }, r ∈ Q, and B, C ∈ Γ ), then for every s ∈ Q, put the following rule in P. [p, A, q]→ a[r, B, s][s, C, q] (b) If M has a move δ (p, a, A) = (q, ε ) (where, a ∈ Σ ∪ {ε }), put the following rule in P. [p, A, q]→ a 58

CFG ↔ PDA

Hierarchy

Now we need to understand the underlying idea for constructing CFG rules with the PDA M that generates L(M). The main objective is to design the grammar rules such that x ∈[p, A, q] if and only if string x is derivable starting with the nonterminal symbol [p, A, q], as the following figures illustrate.

x ∈ [p, A, q] (a) M’s STES

[p, A, q] ⇒ . . . . ⇒ x (b) G’s derivation

STES [q0, Z0, t] contains all the strings that M reads, starting in the start state and continuing until it enters the state t by emptying the stack (i.e., pops Z0). Hence, we get L(M) = [q0, Z0, t]. It follows that G should be able to derive L(M) starting with the nonterminal symbol [q0, Z0, t]. However, to use S as the start symbol following the convention, in step (2) of the algorithm we put the rule S → [q0, Z0, t] in P.

59

Hierarchy

CFG ↔ PDA

Next let us examine step (3) of the algorithm. Recall that [p, A, q] is the set of all possible input segments that M will read, starting in state p with A on the stack top until the machine, in state q, sees the symbol under A (B in figure (a) below) appear for the first time at the stack top. For example, if M has a move as shown in figure (b) below (i.e. δ (p, a, A) = (q, ε )), then a ∈[p, A, q].

a

a (a, A/ε )

p

q

q

Z0 . . . BA

Z0 . . . B (a)

p (b)

60

Hierarchy

CFG ↔ PDA

Now, suppose that M has a pushing move, say δ (p, a, A) = (r1, DC). (Note that in this move, A is changed to C, and D is pushed on top of it). Let s1 be the state M enters the first time it sees C at the stack top, and let q be the state M enters the first time it sees B (which was under the A) at the stack top as shown below. The set [p, A, q] must contain all the strings in a[r1, D, s1][s1, C, q] (for example, axy in the figure), i.e., [p, A, q] ⊇ a[r1, D, s1][s1, C, q]. a

a

x

p

r1

s1

Z0 . . BA

Z0 . . BCD

Z0 . . BC

a

x

y

q Z0 . . . . B

61

Hierarchy

CFG ↔ PDA

The following state transition graph will help us understand why this containment relation holds. [p, A, q] ⊇ a[r1, D, s1][s1, C, q] p

(a, A/DC)

(. ./AB)

(., D/..) r1

q

(., D/..)

(. , B/..)

(. , C/. .) s11

s12

(. , C/. .)

Notice that, as the figure illustrates, there can be more than one state (in the figure s1i ) that M may enter the first time it sees C at the stack top. So the following relation holds. [p, A, q] ⊇ (a[r1, D, s11 ][s11 , C, q] ∪ a[r1, D, s12 ][s12 , C, q] ∪ . . . )

62

Hierarchy

CFG ↔ PDA

Suppose that M has multiple pushing moves in the same state p with the same stack top A, like δ (p, a1, A) = (r1, D1C1), δ (p, a2, A) = (r2, D2C2). We apply the same idea and let [p, A, q] include all the segments of the input strings that M will read until it sees for the first time the symbol (B in the figure below) under DiCi . Thus, for this more general case, we have the following (see the figure below, which illustrates the case).

[p, A, q] ⊇ a1[r1, D1, s11 ][s11 , C1, q] ∪ a1[r1, D1, s12 ][s12 , C1, q] ∪ . . a2[r2, D2, s21 ][s21 , C2, q] ∪ a2[r2, D2, s22 ][s22 , C2, q] ∪ . . . .....

(ai, A/DiCi) (.. /AB)

p

ri

(., Di /..)

q sij

(., B/..)

(., Ci /..)

63

Hierarchy

CFG ↔ PDA

Now, suppose that M has some popping moves in state p with A at the stack top, for example, δ (p, b1, A) = (q, ε ), δ (p, b2, A) = (q, ε ), . . . Since M has only popping and pushing moves on the stack, we finally get the following.

[p, A, q] = a1[r1, D1, s11 ][s11 , C1, q] ∪ a1[r1, D1, s12 ][s12 , C1, q] ∪ . . a2[r2, D2, s21 ][s21 , C2, q] ∪ a2[r2, D2, s22 ][s22 , C2, q] ∪ . . . .... ∪ {b1} ∪ {b2} ∪ . . . Suppose that in state p, M has k1 pushing moves and k2 popping moves, and let n be the number of states of M. The above equation can be expressed as follows. [p, A, q] =

k1

∪ i=1

(

n

∪ j=1

,where p, q, ri, sij , sij ∈ Q,

ai[ri, Di, sij ][sij ,Ci, q] ai, bi ∈ Σ ,

)

k2

b) ∪ (∪ i =1 i

A, Di, Ci,∈ Γ . 64

CFG ↔ PDA

Hierarchy

We know that for each triple p, q and A, the following equation holds.

[p, A, q] = a1[r1, D1, s11 ][s11 , C1, q] ∪ a1[r1, D1, s12 ][s12 , C1, q] ∪ . . a2[r2, D2, s21 ][s21 , C2, q] ∪ a2[r2, D2, s22 ][s22 , C2, q] ∪ . . . .... ∪ {b1} ∪ {b2} ∪ . . . Thus, for every nonterminal [p, A, q] in grammar G, we make the following rules. This is exactly what step (3) of the algorithm does.

[p, A, q] → a1[r1, D1, s11 ][s11 , C1, q] | a1[r1, D1, s12 ][s12 , C1, q] | . . | a2[r2, D2, s21 ][s21 , C2, q] | a2[r2, D2, s22 ][s22 , C2, q] |. . . .... | b1 | b2 |. . . 65

Hierarchy

CFG ↔ PDA Let’s see a couple of application examples of the algorithm.

Example 1. For the PDA M shown in figure (a) below, figure (b) shows a CFG constructed with the algorithm. Rule (1) is constructed by step (2) of the algorithm, rule (2) by step (3)-(a), and rule (3) and (4) by step (3)-(b). We can show that L(M) = {aba} = L(G).

p

(a, Z0/AZ0) (b, A/ε )

(1) S → [p, Z0, q]

r q

(3) [r, A, s] → b

s (a, Z0/ε ) (a) PDA M

(2) [p, Z0, q] → a[r, A, s] [s, Z0, q] (4) [s, Z0, q] → a (b) CFG G

66

Hierarchy

CFG ↔ PDA

Example 2. The PDA below is a little more complex than the one in Example 1. Notice that this is an NPDA because of the two transitions in state 2. (b, a/ε ) 2 (a, Z0/AZ0)

(a, A/aA)

6

5

(b, A/ε )

(ε , A/ ε )

7

3

1

(b, Z0/ ε )

4

(ε , Z0/ ε )

L(M) = L(G) = {aabb, ab } S → [1, Z0, 4] [1, Z0, 4] → a[2, A, 7] [7, Z0, 4] | a[2, A, 3] [3, Z0, 4] [2, A, 7] → a[5, a, 6][6, A, 7] [5, a, 6] → b [7, Z0, 4] → ε

[6, A, 7] → b

[2, A, 3] → ε

[3, Z0, 4] → b 67

Hierarchy

CFG ↔ PDA

The grammar that we have just constructed has too many rules to comprehend for the simple language. If we apply the techniques for minimizing the number of ε production rules and eliminating the unit production rules to this grammar (recall the techniques in Sections 10.1 and 10.2), we can drastically simplify the grammar as shown below. S → [1, Z0, 4] [1, Z0, 4] → a[2, A, 7] [7, Z0, 4] | a[2, A, 3] [3, Z0, 4] [2, A, 7] → a[5, a, 6][6, A, 7] [5, a, 6] → b [7, Z0, 4] → ε

[6, A, 7] → b

[2, A, 3] → ε

[3, Z0, 4] → b

S → aabb | ab

68

Hierarchy

CFG ↔ PDA

Example 3. Figure (a) below shows a PDA accepting (by empty stack) our familiar language L = {aibi | i ≥ 1 }. Figure (b) below shows the grammar G generated by the algorithm. Again, it has too many rules to comprehend. We need to clean it up.

(a, A/AA)

(1) S → [1, Z0, 4] (2) [1, Z0, 4] → a[2, A, 3][3, Z0, 4] |

2

(a, Z0/AZ0)

a[2, A, 2][2, Z0, 4] (b, A/ε )

1 (b, A/ε ) 4

3

(ε , Z0/ε )

(3) [2, A, 4] → a[2, A, 3][3, A, 4] | a[2, A, 2][2, A, 4] (4) [2, A, 3] → a[2, A, 3][3, A, 3] | a[2, A, 2][2, A, 3] | b (5) [2, A, 2] → φ (6) {3, A, 4] → φ (7) [3, A, 3] → b

(a) PDA M

(8) [3, Z0 , 4] → ε

(b) CFG G 69

Hierarchy

CFG ↔ PDA

Rules (5) and (6) are useless, because they generate empty string. In state 2, M makes only pushing moves and it never sees (in the same state 2) the stack symbol under the current stack top symbol A. So, [2, A, 2] is empty. Set [3, A, 4] is empty, since the machine empties the stack and terminates without reading the input. Thus we can eliminate all rules involving two nonterminals [2, A, 2] and [3, A, 4] from the grammar. (1) S → [1, Z0, 4]

(a, A/AA)

(2) [1, Z0, 4] → a[2, A, 3][3, Z0, 4] | a[2, A, 2][2, Z0, 4]

2

(a, Z0/AZ0)

(b, A/ε )

1 (b, A/ε ) 4

3

(ε , Z0/ε )

(3) [2, A, 4] → a[2, A, 3][3, A, 4] | a[2, A, 2][2, A, 4] (4) [2, A, 3] → a[2, A, 3][3, A, 3] | a[2, A, 2][2, A, 3] | b (5) [2, A, 2] → φ (6) [3, A, 4] → φ (7) [3, A, 3] → b

(8) [3, Z0 , 4] → ε 70

Hierarchy

CFG ↔ PDA

Cleaning up those useless symbols from the grammar (see Section 10.3), we get the following simplified grammar.

(a, A/AA) (1) S → [1, Z0, 4]

2

(a, Z0/AZ0) 1 (b, A/ε )

(b, A/ε )

(2) [1, Z0, 4] → a[2, A, 3][3, Z0, 4]

3

(4) [2, A, 3] → a[2, A, 3][3, A, 3] | b (7) [3, A, 3] → b

4

(ε , Z0/ε )

(8) [3, Z0 , 4] → ε (b) CFG G

(a) PDA M

71

Hierarchy

CFG ↔ PDA

To further simplify the grammar let us replace each of the composite symbols with a unique nonterminal symbol as shown in figure (c) below. Eliminating unit productions and minimizing the number of ε -production rules (presented in Sections 10.1 and 2), we finally get the CFG shown in figure (d). Now, we see that this grammar generates the language L = {aibi | i ≥ 1 }.

(1) S → [1, Z0, 4] (2) [1, Z0, 4] → a[2, A, 3][3, Z0, 4] (4) [2, A, 3] → a[2, A, 3][3, A, 3] | b (7) [3, A, 3] → b

(8) [3, Z0 , 4] → ε (b)

(1) S → A (2) A → aBC (4) B → aBD | b (7) D → b (8) C → ε (c)

(1) S → aB (4) B → aBb | b (d) 72

Hierarchy Rumination (1): Constructing a CFG with a PDA Step (3)-(a) of the algorithm (copied below) for constructing a CFG with a given PDA is the single source of generating a “flood” of rules into the grammar. (In particular, see the underlined part.) This step is executed for every pushing move of the automaton. As we saw in Example 3, the algorithm may generate many useless nonterminals. The algorithm for eliminating useless symbols from a CFG that we learned in Chapter 10 can be efficiently used to eliminate those useless symbols. (a) If M has a move δ (p, a, A) = (r, BC) (where, a ∈ Σ ∪ {ε }, r ∈ Q, and B, C ∈ Γ ), then for every s ∈ Q, put the following rule in P. [p, A, q]→ a[r, B, s][s, C, q]

Our Language

Break Time

Did you know that "verb" is a noun? How can you look up words in a dictionary if you can't spell them? If a word is misspelled in a dictionary, how would we ever know? If two mouses are mice and two louses are lice, why aren't two houses hice? If Webster wrote the first dictionary, where did he find the words? If you wrote a letter, perhaps you bote your tongue? If you've read a book, you can reread it. But wouldn't this also mean that you would have to "member" somebody in order to remember them? - MoodyFan -

73

Hierarchy Exercises 15.1 Prove that the union S1 ∪ S2 of two enumerable set s S1 and S2 is also enumerable. 15.2 Show that the set of all real numbers is not enumerable. 15.3 Prove that the class of languages which are not type 0 is not enumerable.

74