• Author / Uploaded
• Rahat Alam

Citation preview

Port City International University

Assignment “Given Problems” Course Code:CSE 317 Course Title: Theory of Computing

Remarks: Submitted To Teacher’s name : Mohammed ArmanuzzamanChowdhury Lecturer DepartmentOf CSE

Port City International University, Chittagong. Submitted By Rahat Alam ID: CSE 01406358 Batch: 014th(Day) Program: B.Sc. in CSE Department of CSE

Port City International University, Chittagong. Date of Submission: 17/08/2020

INDEX Sl. No.

Exercise Section

Exercise Number 14,15,16,22,23,24

1.

1.2

3,4,5,7 2.

1.3 1,2,3,4,11

3.

2.1 1

4.

2.2

2,3,4,5 5.

2.3

6.

2.4

1 2

Page

Remarks

Question: Find grammars for Σ = {a, b} that generate the sets of (a) all strings with exactly two a’s. (b) all strings with at least two a’s. (c) all strings with no more than three a’s. (d) all strings with at least three a’s. (e) all strings that start with a and end with b. (f) all strings with an even number of b’s. In each case, give convincing arguments that the grammar you give does indeed generate the indicated language.

Solution: (a) To all strings with exactly two a’s the grammar G = ({A,S} , { a, b} , S, P) , with P given by S → aaA | Aaa | AaAaA A → bA,A → λ Then S ⇒aaA⇒aabA⇒aabb

[String with exactly 2 a’s] [‘A’ can be replaced with bA|λ]

S ⇒Aaa⇒bAaa⇒bbaa S ⇒AaAaA⇒bAabAabA⇒babab

The string aabb,bbaa,bababis a sentence in the language generated by G, while aabbA,babAabis a sentential form.

Solution: (b) To all strings with at least two a’s the grammar G = ({A,S} , { a, b} , S, P) , with P given by S → aaA | Aaa | AaAaA A → bA|aA, A→λ

[String with at least 2 a’s] [‘A’ can be replaced with bA|aA|λ]

Then S ⇒aaA⇒aabA⇒aabbA⇒aabbaA⇒aabba S ⇒Aaa⇒bAaa⇒bbAaa⇒bbaAaa⇒bbabAaa⇒bbabaa S ⇒AaAaA⇒bAabAabA⇒baAabaAabaA⇒baabaaba

The string aabba,bbabaa,baabaabais a sentence in the language generated by G, while aabbaA,bbabAaa, baAabaAabaAis a sentential form.

Solution: (c) To all strings with no more than three a’s the grammar G = ({S} , { a, b} , S, P) , with P given by S → A | aAa | AaAaAa A → bA, A→λ

[String with no more than three a’s] [‘A’ can be replaced with bA|λ]

Then S ⇒A⇒bA⇒bbA⇒bbb S ⇒aAa⇒abAa⇒abbAa⇒abbbAa⇒abbba S ⇒AaAaAa⇒bAabAabAa⇒bababa

The string bbb ,abbba,bababais a sentence in the language generated by G, while bbA,abbbAa, bAabAabAais a sentential form.

Solution: (d) To all strings with at leastthreea’s the grammar G = ({A,S} , { a, b} , S, P) , with P given by S → AaAaAaA [String with at least Three a’s] A → bA|aA, A→λ

[‘A’ can be replaced with bA|aA|λ]

Then S ⇒AaAaAaA⇒bAabAabA⇒baAabaAabaA⇒baabaaba

The string baabaabais a sentence in the language generated by G, while baAabaAabaAis a sentential form.

Solution: (e) To all strings start with a and end with b the grammar G = ({A,S} , { a, b} , S, P) , with P given by S → aAb [String with start with a and end with b] A → bA|aA|abA|baA, A→λ

[‘A’ can be replaced with bA|aA|λ]

Then S ⇒aAb⇒abAb⇒abaAb⇒abaabAb⇒abaabbaAb⇒abaabbab

The string abaabbabis a sentence in the language generated by G, while abaabbaAbis a sentential form.

Solution: (f) To all strings with with an even number of b’s the grammar G = ({A,S} , { a, b} , S, P) , with P given by S → A | bbA, A → aS, S → λ.

[String with an even number of b’s] [‘A’ can be replaced with aS] [‘S’ can be replaced with λ]

Then S ⇒A⇒aS⇒aA⇒aaS⇒aabbA⇒aabbaS⇒aabba [ A→aS, S→A, A→aS, S→bbA,A→aS, S→λ] The string aabba, is a sentence in the language generated by G, while aabbA, aabbaSis a sentential form.

Question:Give a simple description of the language generated by the grammar withproductions S → aaA, A → bS, S → λ.

Solution: Given: G = ({S,A,},{a,b}, S, P) Set of productions P: S → aaA, A → bS, S→λ

We start from the start state S. We then need to use the production step S → aaA

• To determine A, we can use A → bS. Thus A then contains strings with 2n a's followed by n b's (where n > 0; when n = 0, then the string is the empty string). S ⇒aaA⇒aabS⇒aabaaA⇒aabaabS⇒aabaab {a2nbn|n≥ 0}

Thus the strings in the language generated by G contains the strings a2nbn, which results in the string a2nbn. L(G) = {a2nbn| n≥ 0}

Question: What language does the grammar with these productions generate? S → Aa, A → B, B → Aa

Solution: Given: G = ({S,A,B},a, S, P) Set of productions P: S → Aa, A → B, B→ Aa There is no terminating productionin the given grammar . So the given grammar accepts ø that means the given grammar doesn’t generate any language.

Question: Show that the grammar G = ({S} ,{a, b} , S, P ), with productions S → SS |SSS| aSb|bSa| λ, is equivalent to the grammar in Example 1.13. Take Σ = {a, b}, and let na(w) and nb(w) denote the number of a’s and b’s in the string w, respectively. Then the grammar G with productions S → SS, S → λ, S → aSb, S → bSa generates the language L = {w : na(w) = nb(w)} . This claim is not so obvious, and we need to provide convincing arguments.

Question: Show that the grammars S → aSb|ab|λ and S → aaSbb|aSb|ab|λ are equivalent.

Solution: We say that two grammars G1 and G2 are equivalent if they generate the samelanguage, that is, if L (G1) = L (G2) Given, G1=(S,{a,b}, S, P1) Production, P1 S → aSb|ab|λ We start from the start state S. We then need to use the production step S → aSb|ab. To determine S, we can use S → aSb|ab. Thus S then contains strings with n a's followed by n b's (where n ≥ 0; when n = 0, then the string is the empty string). S ⇒aSb⇒aaSbb⇒aabb S ⇒ab {anbn| n ≥ 0} Thus the strings in the language generated by G contains the strings a2nbn, which results in the string anbn . L(G1) = {anbn| n ≥ 0}

Given, G2=(S,{a,b}, S, P2) Production, P2 S →aaSbb|aSb|ab|λ

We start from the start state S. We then need to use the production step S → aaSbb|aSb| ab. To determine S, we can use S → aaSbb|aSb|ab. Thus S then contains strings with n a's followed by n b's (where n ≥ 0; when n = 0, then the string is the empty string). S ⇒aaSbb⇒aabb S ⇒aSb⇒aaSbb⇒aabb S ⇒ab {anbn| n ≥ 0}

Thus the strings in the language generated by G contains the strings a2nbn, which results in the string anbn . L(G2) = {anbn| n ≥ 0} As, L(G1) =L(G2) thistwo grammars G1 and G2 are equivalent

Question: Show that the grammars S → aSb|bSa|SS|a and S → aSb|bSa|a are not equivalent.

Solution: We say that two grammars G1 and G2 are equivalent if they generate the samelanguage, that is, if L (G1) = L (G2) Given, G1=(S,{a,b}, S, P1) Production, P1 S → aSb|bSa|SS|a We start from the start state S. We then need to use the production step S → aSb|ab. To determine S, we can use S → aSb|ab. Thus S then contains strings with n a's followed by n b's (where n ≥ 0; when n = 0, then the string is the empty string). S ⇒aSb⇒aaSbb⇒aabSabb⇒aabSSabb⇒aabaaabb

S⇒a {anbn| n ≥ 0} Thus the strings in the language generated by G contains the strings a2nbn, which results in the string anbn . L(G1) = {anbn| n ≥ 0}

Given, G2=(S,{a,b}, S, P2) Production, P2 S →aaSbb|aSb|ab|λ We start from the start state S. We then need to use the production step S → aaSbb|aSb|ab. To determine S, we can use S → aaSbb|aSb|ab. Thus S then contains strings with n a's followed by n b's (where n ≥ 0; when n = 0, then the string is the empty string). S ⇒aaSbb⇒aabb S ⇒aSb⇒aaSbb⇒aabb S ⇒ab {anbn| n ≥ 0}

Thus the strings in the language generated by G contains the strings a2nbn, which results in the string anbn . L(G2) = {anbn| n ≥ 0} As, L(G1) ≠L(G2) thistwo grammars G1 and G2 are not equivalent

Question: 3. Give a grammar for the set of integer numbers in C. 4. Design an accepter for integers in C. 5. Give a grammar that generates all real constants in C. 7. Modify the grammar in Example 1.15 so that the identifiers satisfy the following rules: (a) C rules, except that an underscore cannot be the leftmost symbol. (b) C rules, except that there can be at most one underscore. (c) C rules, except that an underscore cannot be followed by a digit.

Question: 1. Which of the strings 0001, 01101, 00001101 are accepted by the dfa in Figure 2.1?. 4. For Σ = {a, b}, construct dfa’s that accept the sets consisting of (a) all strings with exactly one a. (b) all strings with at least two a’s. (c) all strings with no more than two a’s. (d) all strings with at least one b and exactly two a’s. (e) all the strings with exactly two a’s and more than three b’s 2. 11. Consider the set of strings on {0, 1} defined by the requirements below. For each, construct an accepting dfa. (a) Every 00 is followed immediately by a 1. For example, the strings 101, 0010, 0010011001 are in the language, but 0001 and 00100 are not. (b) All strings that contain the substring 000, but not 0000. (c) The leftmost symbol differs from the rightmost one. (d) Every substring of four symbols has, at most, two 0’s. For example, 001110 and 011001 are in the language, but 10010 is not because one of its substrings, 0010, contains three zeros. (e) All strings of length five or more in which the third symbol from the right end is different from the leftmost symbol. 50 Chapter 2 Finite Automata (f) All strings in which the leftmost two symbols and the rightmost two symbols are identical. (g) All strings of length four or greater in which the leftmost two symbols are the same, but different from the rightmost symbol. Solution:

(a) FIGURE 2.1

the strings 0001, 01101, 00001101 The graph in Figure 2.1 represents the dfa M = ({q0, q1, q2} ,{0, 1} , δ, q0, {q1}) where δ is given by δ (q0, 0) = q0, δ (q1, 0) = q0, δ (q2, 0) = q2, δ(q0, 1) = q1, δ (q1, 1) = q2, δ (q2, 1) = q1. Forthe string0001⇒q0q0q0q1 . As q1 is the final state the string will be accepted. Forthe string01101⇒q0q1q2q2q1 . As q1 is the final state the string will be accepted. Forthe string 00001101⇒q0q0q0q0q1q2q2q1 . As q1 is the final state the string will be accepted.

2. Translate the graph in Figure 2.5 into δ- notation

Figure 2.5:

The graph in Figure 2.1 represents the dfa M = ({λ,0,00,001} , {0, 1} , δ, λ, {λ ,0,00}) where δ is given by δ (λ, 0) = 0, δ (0, 0) = 00,δ (00, 0) = 00 δ (001, 0) = 001,δ (λ,1) = λ, δ (0, 1) = λ, δ (00, 1) = 001,δ (001, 1) = 001 3. For Σ = {a, b}, construct dfa’s that accept the sets consisting of (a) all strings of even length. (b) all strings of length greater than 5. (c) all strings with an even number of a’s. (d) all strings with an even number of a’s and an odd number of b’s.

(a)

a,b

q1

q2

a,b

q0

(b) all strings of length greater than 5. a,b

a,b

q1

a,b

q1

a,b

a,bq1

q1

a,b q2

q0

a,b

a,b

q1

(c) all strings with an even number of a’s.

b

q0

b

a

a

a

q1

q2

b

4. For Σ = {a, b}, construct dfa’s that accept the sets consisting of (a) all strings with exactly one a. (b) all strings with at least two a’s. (c) all strings with no more than two a’s. (d) all strings with at least one b and exactly two a’s. (e) all the strings with exactly two a’s and more than three b’s

(a) b

a,b

a

q0

a

q1

q2

b

(b)

b

a,b

a

q0

a q1

q2

b

(c)

b

b

q0

b

a

a q1

a

a,b

q0

q2

(d)

b

b

a,b

a

q0

a

a

q1 q1

q1

b

a

q2

q1

a,bb

(e) all the strings with exactly two a’s and more than three b’s a,b

q1

bb

a

q0

a

b

q1

aa

a,

q1

q1

a

a

q1

b q1

q1

a

a

b

b

q2