Theory of computational maths PDF

Preview

Summary

Assignments on Theory of Computation...

Description

Solutions for Homework Five, CSE 355 1.

(7.1, 10 points) Let M be the PDA defined by

Q = {q0 , q1 , q2 }

δ(q0 , a, λ) = {[q0 , A]} δ(q0 , λ, λ) = {[q1 , λ]}

Σ = {a, b}

δ(q0 , b, A) = {[q2 , λ]}

Γ = {A} F = {q1 , q2 }

δ(q1 , λ, A) = {[q1 , λ]} δ(q2 , b, A) = {[q2 , λ]} δ(q2 , λ, A) = {[q2 , λ]}

a) Describe the language accepted by M . b) Give the state diagram of M . c) Trace all computations of the strings aab, abb, aba in M . d) Show that aabb, aaab ∈ L(M ). Solution: a) The PDA M accepts the language {ai bj | 0 ≤ j ≤ i}. Processing an a pushes A onto the stack. Strings of the form ai are accepted in state q1 . The transitions in q1 empty the stack after the input has been read. A computation with input ai bj enters state q2 upon processing the first b. To read the entire input string, the stack must contain at least j A’s. The transition δ(q2 , λ, A) = [q2 , λ] will pop any A’s remaining on the stack. b) The state diagram of M is aλ/A M:

λA/λ λλ/λ

q0

q1

bA/λ q2 bA/λ, λA/λ

c) The computations of aab in M are as follows: State q0 q1

String aab aab

State q0 q0 q1 q1

Stack λ λ

1

String aab ab ab b

Stack λ A A λ

State q0 q0 q0 q1 q1 q1 The computations State q0 q1

String abb abb

String Stack aab λ ab A b AA b AA b A b λ of abb in M are as follows: State q0 q0 q1 q1

Stack λ λ

State q0 q0 q0 q2 q2

String abb bb bb bb

String aab ab b λ λ

Stack λ A AA A λ

Stack λ A A λ

State q0 q0 q2

String abb bb b

Stack λ A λ

Stack λ A A λ

State q0 q0 q2

String aba ba a

Stack λ A λ

The computations of aba in M are as follows: State q0 q1

String aba aba

State q0 q0 q1 q1

Stack λ λ

String aba ba ba ba

d) To show that the string aabb and aaab are in L(M ), we trace a computation of M that accepts these strings. State q0 q0 q0 q2 q2

2.

String aabb abb bb b λ

State q0 q0 q0 q0 q2 q2 q2

Stack λ A AA A λ

(7.2, 10 points) Let M be the PDA in Example 7.1.3. bλ/B, aλ/A M:

q0

bB/λ, aA/λ λλ/λ

q1

a) Give the transition table of M . b) Trace all computations of the strings ab, abb, abbb in M . c) Show that aaaa, baab ∈ L(M ). d) Show that aaa, ab ∈ / L(M ). Solution: 2

String aaab aab ab b λ λ λ

Stack λ A AA AAA AA A λ

δ(q0 , b, λ) = {[q0 , B]} δ(q0 , a, λ) = {[q0 , A]}

Q = {q0 , q1 } Σ = {a, b} Γ = {A, B}

a)

δ(q0 , λ, λ) = {[q1 , λ]} δ(q1 , b, B) = {[q1 , λ]}

F = {q1 }

δ(q1 , a, A) = {[q1 , λ]}

b) The computations of ab in M are as follows: State q0 q1

String ab ab

State q0 q0 q1

Stack λ λ

String ab b b

Stack λ A A

State q0 q0 q0 q1

String ab b λ λ

Stack λ A BA BA

The computations of abb in M are as follows: State q0 q1

String abb abb

Stack λ λ

State q0 q0 q1

String abb bb bb

Stack λ A A

State q0 q0 q0 q1 q1

String abb bb b b λ

Stack λ A BA BA A

State q0 q0 q0 q0 q1

String abb bb b λ λ

Stack λ A BA BBA BBA

State q0 q0 q0 q1 q1

String abbb bbb bb bb b

The computations of abbb in M are as follows: State q0 q1

String abbb abbb

State q0 q0 q0 q0 q1 q1

State q0 q0 q1

Stack λ λ

String abbb bbb bb b b λ

String abbb bbb bbb

Stack λ A BA BBA BBA BA

Stack λ A A State q0 q0 q0 q0 q0 q1

String abbb bbb bb b λ λ

Stack λ A BA BA A

Stack λ A BA BBA BBBA BBBA

c) To show that the string aaaa and baab are in L(M ), we trace a computation of M that accepts these strings.

3

State q0 q0 q0 q1 q1 q1

String aaaa aaa aa aa a λ

Stack λ A AA AA A λ

State q0 q0 q0 q1 q1 q1

String baab aab ab ab b λ

Stack λ B AB AB B λ

d) To show that the string aaa and ab are not in L(M ), we trace all computations of these strings in M , and check whether none of them accepts these strings. We have listed all the computations of ab in (b), and none of them accepts it. Now we trace all computations of aaa in M State String Stack q0 aaa λ State String Stack q0 aa A q0 aaa λ q1 aa A q1 aaa λ q1 a λ State q0 q0 q0 q1 q1

String aaa aa a a λ

Stack λ A AA AA A

State q0 q0 q0 q0 q1

String aaa aa a λ λ

Stack λ A AA AAA AAA

Since none of the computations above is accepted, we have aaa is not in M .

3.

(7.3, 10 points) Construct PDAs that accept each of the following languages.

a) {ai bj | 0 ≤ i ≤ j} b) {ai cj bi | i, j ≥ 0} c) {ai bj ck | i + k = j} d) {w | w ∈ {a, b}∗ and w has twice as many a’s as b’s} e) {ai bi | i ≥ 0} ∪ a∗ ∪ b∗ f) {ai bj ck | i = j or j = k} g) {ai bj | i 6= j} h) {ai bj | 0 ≤ i ≤ j ≤ 2i} i) {ai+j bi cj | i, j > 0} j) The set of palindromes over {a, b} Solution: 4

aλ/A M:

a)

bA/λ, bλ/λ λλ/λ

q0

aλ/A

b)

M:

q0

cλ/λ λλ/λ

aλ/A

c)

M:

q0

q1

q1

bA/λ λλ/λ

bA/λ, bλ/B λλ/λ

q1

q2 cB/λ

λλ/λ

q2

d) The pushdown automaton defined by the transitions δ(q0 , λ, λ) = {[q1 , C]} δ(q1 , a, A) = {[q2 , A]} δ(q1 , a, C) = {[q2 , C]} δ(q1 , b, B) = {[q3 , B]} δ(q1 , b, C) = {[q3 , C]} δ(q1 , a, B) = {[q1 , λ]} δ(q1 , b, A) = {[q1 , λ]} δ(q1 , λ, C ) = {[q5 , λ]} δ(q2 , λ, λ) = {[q1 , A]} δ(q3 , λ, λ) = {[q4 , B]} δ(q4 , λ, λ) = {[q1 , B]} accepts strings that have twice as many a’s as b’s. A computation begins by pushing a C onto the stack, which serves as a bottom-maker throughout the computation. The stack is used to record the relationship between the number of a’s and b’s scanned during the computation. The stacktop will be a C when the number of a’s processed is exactly twice the number of b’s processed. The stack will contain n A’s if the automaton has read n more a’s than b’s. If n more b’s than a’s have been read, the stack will hold 2n B’s. When an a is read with an A or C on the top of the stack, an A is pushed onto the stack. This is accomplished by the transition to q2 . If a B is on the top of the stack, the stack is popped removing one b. If a b is read with a C or B on the stack, two B’s are pushed onto the stack. Processing a b with an A on the stack pops the A. The lone accepting state of the automation is q5 . If the input string has twice as many a’s as b’s, the transition to q5 pops the C, terminates the computation, and accepts the string.

5

bA/λ, aB/λ M:

λλ/λ

q0

aA/A, aC/C

q1

q2

λλ/A bB/B

λλ/B

bC/C

λλ/B

q4

q3

q5

aλ/A

bA/λ λλ/λ

q0

M:

λλ/λ

e)

q0

q1

λλ/λ

q2

q3

aλ/λ

bλ/λ

aλ/A M:

λC/λ

bA/λ λλ/λ

cλ/λ λλ/λ

q1

q2

λλ/λ q3

f)

M:

λλ/λ

λλ/λ

q4

q5

aλ/λ

bλ/B

cB/λ

aλ/A

bA/λ

bλ/λ

q0

λλ/λ

bλ/λ

q1

q2

λA/λ q3

g)

λA/λ

h) The language L = {ai bj | 0 ≤ i ≤ j ≤ 2 · i} is generated by the context-free grammar S → aSB | λ B → bb | b The B rule generates one or two b’s for each a. A pushdown automaton M that accepts L uses the a’s to record an acceptable number of matching b’s on the stack. Upon processing an a, the computation nondeterministically pushes one or two A’s onto the stack. The transitions

6

of M are δ(q0 , a, λ) = {[q1 , A]} δ(q0 , λ, λ) = {[q3 , λ]} δ(q0 , a, λ) = {[q0 , A]} δ(q0 , b, A) = {[q2 , λ]} δ(q1 , λ, λ) = {[q0 , A]} δ(q2 , b, A) = {[q2 , λ]} The states q2 and q3 are the accepting states of M . The null string is accepted in q3 . For a nonnull string ai bj ∈ L, one of the computations will push exactly j A’s onto the stack. The stack is emptied by processing the b’s in q2 . The state diagram of the PDA is aλ/A aλ/A M:

q0

q1 λλ/A

λλ/λ

bA/λ

q3

q2

aλ/A

i)

bA/λ λλ/λ

q0

M:

M:

q0

cA/λ λλ/λ

q1

aλ/A, bλ/B

j)

bA/λ

q2

aA/λ, bB/λ

aλ/λ, bλ/λ, λλ/λ

q1

4.

(7.7, 10 points) Let L be the language {w ∈ {a, b}∗ | w has a prefix containing more b’s than a’s.}. For example, baa, abba, abbaaa ∈ L, but aab, aabbab ∈ / L. a) Construct a PDA that accepts L by final state. b) Construct a PDA that accepts L by empty stack. Solution: aλ/A, bA/λ

a)

M:

q0

λλ/B

q1

aλ/λ, bλ/λ bB/λ

aλ/A, bA/λ

b)

M:

q0

λλ/B

q1

7

q2 aλ/λ, bλ/λ

bB/λ

q2

5. (7.12, 20 points) Use the technique of Theorem 7.3.1 to construct a PDA that accepts the languages of the Greibach normal form grammar. S → aABA | aBB A → bA | b B → cB | c Solution:

The state diagram for the extended PDA obtained from the grammar is Q = {q0 , q1 }

δ(q0 , a, λ) = {[q1 , ABA], [q1 , BB]}

Σ = {a, b, c} Γ = {A, B}

δ(q1 , b, A) = {[q1 , A], [q1 , λ]} δ(q1 , c, B) = {[q1 , B], [q1 , λ]}

F = {q1 }

bA/λ, bA/A, cB/λ, cB/B q0

6.

aλ/ABA, aλ/BB

q1

(7.15, 20 points) Let M be the PDA in Example 7.1.1. Q = {q0 , q1 } Σ = {a, b, c} Γ = {A, B} F = {q1 }

δ(q0 , a, λ) = {[q0 , A]} δ(q0 , b, λ) = {[q0 , B]} δ(q0 , c, λ) = {[q1 , λ]}

aλ/A, bλ/B M:

q0

aA/λ, bB/λ cλ/λ

q1

δ(q1 , a, A) = {[q1 , λ]} δ(q1 , b, B) = {[q1 , λ]}

a) Trace the computation in M that accepts bbcbb. b) Use the technique from Theorem 7.3.2 to construct a grammar G that accepts L(M ). c) Give the derivation of bbcbb in G. Solution:

a)

State q0 q0 q0 q1 q1 q1

String bbcbb bcbb cbb bb b λ

b) First we add transitions to M as follows.

8

Stack λ B BB BB B λ

δ(q0 , a, λ) = {[q0 , A]} δ(q0 , a, A) = {[q0 , AA]} δ(q0 , a, B) = {[q0 , AB]} δ(q0 , b, λ) = {[q0 , B]} δ(q0 , b, A) = {[q0 , BA]} δ(q0 , b, B) = {[q0 , BB]} δ(q0 , c, λ) = {[q1 , λ]} δ(q0 , c, A) = {[q1 , A]} δ(q0 , c, B) = {[q1 , B]} δ(q1 , a, A) = {[q1 , λ]} δ(q1 , b, B) = {[q1 , λ]} Second the rules of the equivalent grammar G and the transition from which they were constructed are presented in Table 1.

c)

[q0 , bbcbb, λ] ⊢ [q0 , bcbb, B] ⊢ [q0 , cbb, BB] ⊢ [q1 , bb, BB] ⊢ [q1 , b, B] ⊢ [q1 , λ, λ]

S ⇒ hq0 , λ, q1 i ⇒ bhq0 , B, q1 i ⇒ bbhq0 , B, q1 ihq1 , B, q1 i ⇒ bbchq1 , B, q1 ihq1 , B, q1 i ⇒ bbcbhq1 , λ, q1 ihq1 , B, q1 i ⇒ bbcbhq1 , B, q1 i ⇒ bbcbbhq1 , λ, q1 i ⇒ bbcbb

7. (7.17, 20 points) Use the pumping lemma to prove that each of the following languages is not context-free. a) {ak | k is a perfect square} b) {ai bj ci d j | i, j ≥ 0} c) {ai b2i ai | i ≥ 0} d) {ai bj ck | 0 < i < j < k < 2i} e) {wwR w | w ∈ {a, b}∗ } f) The set of finite-length prefixes of the infinite string abaabaaabaaaab · · · ban ban+1 b · · · Solution: a) Assume that language L consisting of strings over {a} whose lengths are a perfect square is context-free. By the pumping lemma, there is a number k such that every string in L with length k or more can be written uvwxy where 9

Transition δ(q0 , a, λ) = {[q0 , A]} δ(q0 , a, A) = {[q0 , AA]}

δ(q0 , a, B) = {[q0 , AB ]}

δ(q0 , b, λ) = {[q0 , B]} δ(q0 , b, A) = {[q0 , BA]}

δ(q0 , b, B) = {[q0 , BB ]}

δ(q0 , c, λ) = {[q1 , λ]} δ(q0 , c, A) = {[q1 , A]} δ(q0 , c, B) = {[q1 , B ]} δ(q1 , a, A) = {[q1 , λ]} δ(q1 , b, B) = {[q1 , λ]}

Rule S → hq0 , λ, q1 i hq0 , λ, q0 i → ahq0 , A, q0 i hq0 , λ, q1 i → ahq0 , A, q1 i hq0 , A, q0 i → ahq0 , A, q0 ihq0 , A, q0 i hq0 , A, q0 i → ahq0 , A, q1 ihq1 , A, q0 i hq0 , A, q1 i → ahq0 , A, q0 ihq0 , A, q1 i hq0 , A, q1 i → ahq0 , A, q1 ihq1 , A, q1 i hq0 , B, q0 i → ahq0 , A, q0 ihq0 , B, q 0 i hq0 , B, q0 i → ahq0 , A, q1 ihq1 , B, q0 i hq0 , B, q1 i → ahq0 , A, q0 ihq0 , B, q1 i hq0 , B, q1 i → ahq0 , A, q1 ihq1 , B, q1 i hq0 , λ, q0 i → bhq0 , B, q0 i hq0 , λ, q1 i → bhq0 , B, q1 i hq0 , A, q0 i → bhq0 , B, q0 ihq0 , A, q0 i hq0 , A, q0 i → bhq0 , B, q1 ihq1 , A, q0 i hq0 , A, q1 i → bhq0 , B, q0 ihq0 , A, q1 i hq0 , A, q1 i → bhq0 , B, q1 ihq1 , A, q1 i hq0 , B, q0 i → bhq0 , B, q0 ihq0 , B, q0 i hq0 , B, q0 i → bhq0 , B, q1 ihq1 , B, q0 i hq0 , B, q1 i → bhq0 , B, q0 ihq0 , B, q1 i hq0 , B, q1 i → bhq0 , B, q1 ihq1 , B, q1 i hq0 , λ, q0 i → chq1 , λ, q0 i hq0 , λ, q1 i → chq1 , λ, q1 i hq0 , A, q0 i → chq1 , A, q0 i hq0 , A, q1 i → chq1 , A, q1 i hq0 , B, q0 i → chq1 , B, q0 i hq0 , B, q1 i → chq1 , B, q1 i hq1 , A, q0 i → ahq1 , λ, q0 i hq1 , A, q1 i → ahq1 , λ, q1 i hq1 , B, q0 i → bhq1 , λ, q0 i hq1 , B, q1 i → bhq1 , λ, q1 i hq0 , λ, q0 i → λ hq1 , λ, q1 i → λ

Table 1: The rules of the equivalent grammar G and the transition from which they were constructed (Problem 7.15 (b))

10

(i) length(vwx) ≤ k (ii) v and x are not both null (iii) uvi wxi y ∈ L for all i ≥ 0. 2

The string z = ak must have a decomposition uvwxy that satisfies the preceding conditions. Consider the length of the string uv 2 wx2 y obtained by pumping uvwxy. length(z) =length(uv2 wx2 y) =lenght(uvwxy) + length(v) + length(x) =k 2 + length(v) + length(x) ≤k 2 + k 2, since we can always increase k while maintaining the three conditions above. Then the string z = ak bk+1 ck+2 is in L and must have a decomposition uvwxy that satisfies the preceding conditions. Consider the string uv k wxk y obtained by pumping uvwxy. Condition (i) requires the length of vwx to be at most k. This implies that vwx is a string containing only one type of terminal or the concatenation of either a and b types, or b and c types. If c is not contained in vwx, pumping v and x only increases the number of a’s or b’s. Thus the new string cannot keep the number of a’s less than the number of b’s which is less than the number of c’s, i.e. k + 2. If c is contained in vwx, then a is not contained in vwx. Thus uvk wxk y would have at least (k + 2) + (k − 1) = 2k + 1 number of c’s while keeping the number of a’s the same, i.e. k. Hence uvk wxk y ∈ / L, and consequently, L is not context-free. e) Assume that language L = {wwR w | w ∈ {a, b}∗ } is context-free. By the pumping lemma, there is a number k such that every string in L with length k or more can be written uvwxy where (i) length(vwx) ≤ k (ii) v and x are not both null (iii) uvi wxi y ∈ L for all i ≥ 0. The string z = (ak bk )(ak bk )R (ak bk ) = ak b2k a2k bk must have a decomposition uvwxy that satisfies the preceding conditions. By condition (ii), we have v and x have at least one terminal. Without loss of generality, assume that at least one a is in v or x (similar argument for the case of at least one b in v or x ). Condition (i) requires the length of vwx to be at most k. This implies that the substring vwx of z cannot contain a’s from both sides of b2k . If the a’s in the substring vwx of z are before b2k , then uv 2 wx2 y increases the number of a’s before b2k while keeping the number of a’s after b2k the same as 2k. Hence uv 2 wx2 y is no long in L = {wwR w | w ∈ {a, b}∗ }. If the a’s in the substring vwx of z are after b2k , we have uv 2 wx2 y ∈ / L by similar argument. Therefore L is not context-free. f) Assume that the language L consisting of prefixes of string abaabaaabaaaab · · · ban ban+1 b· is context-free and let k be the number specified by the pumping lemma. Consider the string z = abaab · · · bak b, which is in the language and has length greater than k. Thus z can be written uvwxy where (i) length(vwx) 6= k 12

(ii) v and x are not both null (iii) uvi wxi y ∈ L for all i ≥ 0. To show that the assumption that L is context-free produces a contradiction, we examine all possible decomposition of z that satisfy the conditions of the pumping lemma. By (ii), one or both of v and x must be nonnull. In the following argument we assume that v 6= λ. Case 1: v has no b’s. In this case, v consists solely of a’s and lies between two consecutive b’s. That is, v occurs in z in a position of the form · · · ban bai vaj ban+2 b · · · where i + length(v) + j = n + 1. Pumping v produces an incorrect number of a’s following ban b and, consequently, the resulting string is not in the language. Case 2: v has two or more b’s. In this case, v contains a substring ban b. Pumping v produces a string with two substrings of the form ban b. No string with this property is in L. Case 3: v has one b. Then v can be written ai baj and occurs in z as · · · ban−1 ban−i van+1−j b · · · Pumping v produces the substring · · · ban−1 ban−i ai baj ai baj an+1−j b · · · = · · · ban−1 ban baj +i ban+1 b · · · , which cannot occur in a string in L. Regardless of its makeup, pumping any nonnull substring v of z produces a string that is not in the language L. A similar argument shows that pumping x produces a string not in L whenever x is nonnull. Since one of v or x is nonnull, there is no decomposition of z that satisfies the requirements of the pumping lemma and we conclude that the language is not context-free.

13...