Fri, 05/28/2010 - 13:50 — sunil sharma

Assignment No: 01

Subject Name: Theory of Computer Science

1. Prove that the relation “a b (modm)” is an equivalence relation on the set of integers

Ans:- Let a ε Z.

Reflexive: Since n divides a - a = 0, we have a a mod n.

Symmetric: Let a≡ b mod n.

n divides a - b

n divides - (a - b)

n divides b - a

b ≡ a mod n.

Transitivity: Let a, b, c ε Z such that a b mod n, b ≡ c mod n.

n divides a - b, and n divides b - c

n divides ( a - b ) + ( b - c)

n divides a – c

a ≡ c mod n.

Hence the relation is an equivalence relation.

2. Prove by the principle of mathematical induction that

Ans:-For ,n= 1, left side =1³ =1

right side = 1²(1+1) ²/4 =1.4/4=1

Hence it is true for n=1

3. Prove that the sum of the degrees of the vertices of a graph G is twice the number of edges

Ans:- Proof: (The proof is by induction on the number of edges ‘e’).

Case-(i): Suppose e = 1. Suppose f is the edge in G with f = uv.

Then d(v) = 1, d(u) = 1. Therefore,

Σd(x)=

x v

=Σd (x) + d(u) + d(v)

= 0 + 1 + 1 = 2 = 2

= 2 (number of edges).

Hence the given statement is true for n = 1.

Now we can assume that the result is true for e = k - 1.

Take a graph G with k edges.

Now consider an edge ‘f’ in G whose end points are u and v.

Remove f from G. Then we get a new graph G* = G - {f}.

Suppose d*(v) denotes the degree of vertices v in G*.

Now for any x {u, v}, we have d(x) = d*(x), and

d*(v) = d(v) - 1, d*(u) = d(u) - 1.

Now G* has k - 1 edges. So by induction hypothesis

Σ d*(vi) = 2(k - 1).

Now

2(k - 1) =Σd*(vi)= Σd( vi ) + d*(u) + d*(v)

=Σ(vi)+(d(u) - 1) + (d(v) - 1)

=Σd( v i ) + d(u) + d(v) - 2 = Σ d* ( vi ) - 2

• 2(k - 1) + 2 =Σd* ( vi) 2k = Σd(vi).

Hence, by induction we get that “the sum of the degrees of the vertices of the graph G is twice the numbers of edges”.

4. Generate the language by the grammar

G = ({S, A, B, C}, {a, b}, S, )

where is the set of productions

{SaS, SaB, BbC, CaC, Ca}

Ans:- We generate the language for n = 2. That is, we derive the string a2b2c2.

S aSBC

aaBCBC

aaBBCC

aabBCC

aabbCC

aabbcC

aabbcc

5. Write briefly about the concept of Deterministic Finite Automata (DFA)

Ans:- The first type of automata, we study in detail the finite accepters that are deterministic in their operation. We start with a precise formal definition of deterministic accepters.

Definition A DFA is 5-tuple or quintuple M = (Q, ∑ , , q0, F) where

Q is non-empty, finite set of states.

∑ is non-empty, finite set of input alphabet.

is transition function, which is a mapping from Q * ∑ to Q. For this transition function the parameters to be passed are state and input symbol. Based on the current state and input symbol, the machine may enter into another state.

q0 Q is the start state.

F Q is set of accepting or final states.

Note:- For each input symbol a, from a given state there is exactly one transition (there can be no transitions from a state also) and we are sure (or can determine) to which state the machine enters. So, the machine is called Deterministic machine. Since it has finite number of states the machine is called Deterministic finite machine (automaton).

6. Convert the Moore machine M1 whose state table is given in table below into an equivalent Mealy machine

Moore Machine

Present State Next state Output

Input a = 0 Input a =1

q0 q1 q2 1

q1 q3 q2 0

q2 q2 q1 1

q3 q0 q3 1

Ans:- Let us first transform each column of inputs into the pairs of the next state and the output as shown in the following table.

Present State Input a = 0 Input a = 1

State Output State Output

q0 q1 0 q2 1

q1 q3 1 q2 1

q2 q2 1 q1 0

q3 q0 1 q3 1

Since there are no two states in the above state table which have identical row elements, the state table as shown represents the equivalent Mealy machine for the Moore machine depicted above.

Assignment No: 02

Subject Name: Theory of Computer Science

1. Construct DFA and the corresponding transition diagram to accept the language generated by the following grammar

S aA

A aA bB

B bB 10 marks

Ans:- Observe that each production of the form

A wB

the corresponding transition will be (A, w) = B

Also, for each production of the form A w, we can introduce the transition

(A, w) = qf, where qf is the final state.

The transitions obtained from grammar G is shown in the table

Productions Transitions

S 01A

A 10B

B 0A

B 11 (S, 01) = A (A, 10) = B

(B, 0) = A

(B, 11) = qf

2. Obtain a right linear grammar for the regular expression ((aab)* ab)*, given by the transition diagram.

Ans:- For each transition of the form (A, a) = B, introduce the production A aB. If q F (the final state), introduce the production A . The productions obtained from the transitions defined for DFA are shown below.

Transitions Productions

(S, a) = A

(S, b) = C

(A, a) = C

(A, b) = B

(B, a) = B

(B, b) = B

(C, a) = C

(C, b) = C S →aA

S →bC

A→ aC

A→ bB

B→ aB

B →bB

C→ aC

C →bC

From the diagram, it is clear that the state B is a final state.

Therefore, we introduce the production B .

The grammar G corresponding to the productions obtained is shown below.

G = (VN, VT, S, ), where

VN = {S, A, B, C}

VT = {a, b}

The set of productions: S aA bC

A aC bB

B aB bB

C aC bC

S is the starting symbol

3. Show that L = {aibj / i > j} is not regular

Ans:- Step 1: Let L is regular and n be the number of states in FA.

Consider the string x = an+1 bn.

Step2: Note that x = 2n+1 n. So, we can split x into uvw such that uv ≤ n and v 1 as shown below. x = an+1bn =

where u = j and v = k 1 and so that uv = u + v = j + k ≤ n.

Step 3: According to pumping lemma, uviw L for i = 0

That is, L for i = 0.

Now, if we choose i = 0, number of a’s in string u will not be more than the number of b’s in w which is contradiction to the assumption that number of a’s are more than the number of b’s.

So, the language L = {aibj i > j} is not regular.

4. Obtain a PDA to accept the language L = {anbn / n 1} by a final state

Ans:- General Method: Since n number of a‟s should be followed by n number of b’s, let us push all the symbols on to the stack as long as the scanned input symbol is ‘a’. Once we encounter b’s, we should see that for each ‘b’ in the input, there should be corresponding ‘a’ on the stack. When the input pointer reaches the end of the string, the stack should be empty. If stack is empty, it indicates that the string scanned has n number of a’s followed by n number of b’s. Step 1: Let q0 be the start and Z0 be the initial symbol the stack. As long as the next input symbol to the scanned is ‘a’, irrespective of what is there on the stack, keep pushing all the symbols on to the stack and remain in q0. The transitions defined for this can be of the form

(q0, a, Z0) = (q0, aZ0)

(q0, a, a) = (q0, aa)

Step 2: In state q0, if the next input symbol to be scanned is ‘b’ and if the top of the stack is ‘a’, change the state to q1 and delete one ‘b’ from the stack. The transition for this can be of the form (q0, b, a) = (q1, )

Step 3: Once the machine is in state q1, the rest of the symbols to be scanned will be only b’s and for each ‘b’ there should be corresponding symbol ‘a’ on the stack. Therefore, as the scanned input symbol is b and if there is a matching ‘a’ on the stack, remain in q1 and delete the corresponding ‘a’ from the stack. The transitions defined for this can be of the form

(q1, b, a) = (q1, )

Step 4: In state q1, if the next input symbol to be scanned is and if the top of the stack is Z0, change the state to q2 which is an accepting state. The transition defined for this can be of the form (q1, , Z0) = (q2, Z0)

5. State and prove pumping lemma for Context Free Languages

Ans:- Let L be the context free language and is infinite. Let z be sufficiently long string and z L so that z n where n is some positive integer. If the string z can be decomposed into combinations of strings

z = uvwxy

such that vwx ≤ n, vx 1, then uvi wiy L for i = 0, 1, 2, ….

Observations:-

n is the length of the longest string that can be generated by the parse tree where the same non terminal never occurs twice on the same path through the tree.

The string z is sufficiently long so that it can be decomposed into various sub strings u, v, w, x and y in that sequence.

The two sub strings v and x are present somewhere in z.

The sub string u appears before v, the sub string w is in between v and x and the sub string y appears after x.

The string w in between v and x cannot be too long since vwx ≤ n for some positive integer n.

Both the sub strings v and x cannot be empty since vx 1. (One of them can be empty).

If all the points mentioned (first five points) are satisfied and if we duplicate sub string v and x same number of times, the resulting string will definitely be in L and the string z L is context free. Otherwise, the string z L is not context free.

Proof of Pumping Lemma: By Pumping Lemma, it is assumed that string z L is finite and is context free language. We know that z is string of terminal which is derived by applying series of productions.

6. Find a Turing machine to accept the language containing string’s of 0’s and 1’s ending with 011

Ans:- The DFA which accepts the language consisting of 0‟s and 1‟s ending with the string 001 is shown below

The transition table for the DFA is shown below.

0 1

q0 q1 q0

q1 q1 q2

q2 q1 q3

q3 (final state) q1 q0

For each scanned input symbol (either 0 or 1), in whichever state the DFA was in, TM also enters into the same states on same input symbols, replacing 0 by 0 and 1 by 1 and the read-write head moves towards right. Therefore, the transition table for DFA and TM remains same (the format may be different. It is evident in both the transition tables). So the transition table for TM recognizes the language consisting of 0‟s and 1‟s ending with a substring 001

States

0 1 □

q0 q1, 0, R q0, 1, R

q1 q1, 0, R q2, 1, R

q2 q1, 0, R q3, 1, R

q3 q1, 0, L q0, 1, R q4, □, R

q4 - - -

Therefore, the TM to recognize the given language is given by

Q = {q0, q1, q2, q3}

= {0, 1}

= {0, 1, □}, is defined above.

q0 is the start state

□ is the blank character

F = {q4} is the final character