Q1) (18 points) Fill in the blanks. (In case of MCQs select the correct choice).

 

1.      A = L(a*), B = {anbn : n>=0}, AB = ________________ (regular / non-regular)

2.      |l| = __________

3.      The transition function for NFA is given by ________________________ (give the precise mathematical relation)

4.      L = regular language, L׳ / L׳׳ is ______________ (regular / non-regular) (prime  ׳ indicates complement of language)

5.      L = regular language, * - L is ______________ (regular / non-regular)

6.      L= {anbn : 0<n<15} is a  ___________________ language (regular only/context-free only /both regular and context free / neither regular nor context free)

7.      A={ambncn | m,n >=0}   B= {anbncm | m,n>=0}    C=AB={ ______________ }      Is C a context free language? ___________________(yes/no)

8.      The regular expression (0+l)+(0+l) (0+l)* (0+l) is equivalent to

(a) 0*           (b) l                (c) 0+l            (d) 00*            (e) none of these

9.      The regular expression 1+(0+l) (0+l)* 1 is equivalent to

(a) 01*          (b) 1+0*          (c) 00*1           (d) 0*1             (e) none of these

 

10. The regular expression l+(0+1) (0+l)* 1 is equivalent to

(a)  l+(0+1)0*1              (b)  l+00*1           (c)  l+10*1+11           (d)  l+(0+1)*01          (e)  none of these

11. The regular expression (rr)*(r+l) is equivalent to

(a) (rr)*                           (b) r*                     (c) r(rr)*           (d)  none of these

12. The regular expression r+(rr+rrr)* is equivalent to

(a) (rr)*                           (b) r*                     (c) r(rr)*           (d)  none of these

13.   Productions in Regular Grammars are of the form:  __________________________________________ (give mathematically precise definition)

14. Productions in Context Free Grammars are of the form:  __________________________________________ (give mathematically precise definition)

15. Productions in Unrestricted Grammars are of the form:  __________________________________________ (give mathematically precise definition)

16. Productions in S Grammars are of the form:  __________________________________________ (give mathematically precise definition)

17. In deterministic pushdown automata if d(q,l, b) is not empty, then _____________ must be empty for ________________

Q2) (6 points)

 

Construct an equivalent Generalized Transition Graph for the following NFA with two states.

 

 

 

 

 

 

 

 

 

 

 

 1

 
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Q3) (7 points) Give the Left Linear Grammar for the following DFA

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Q4) (10 points) Construct a context-free grammar generating the

 

Complement of L= { anbn | n>=0 }

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Q5) (6 points)

L = {axbyaz ; x is even, y is odd and z is odd}

 

A friend of yours has presented the following argument using pumping lemma to show that L is a non-regular language. Do you agree with your friend? If not, clearly point out the fallacy in the argument with respect to the Pumping Lemma definition. (Your answer should be precise, ambiguous statements carry no credit)

 

Your friends argument:

(Proof by contradiction) Suppose L is a regular language accepted by m-state dfa.

 

Taking w=a2mbbbaaaaa L

According to Pumping Lemma w can be decomposed as w=xyz, The selection of the string forces y to comprise of only as.

 

According to Pumping Lemma |y|=3 >1

 

w=xyz; x= a2m-3, y=aaa, z= bbbaaaaa

 

However w=xyiz = a2m-3 bbbaaaaa for i=0 is not in L therefore we have reached a contradiction of pumping lemma, and L is a non-regular langauge.

 

 

 

 

 


Q6 ) (9 points)

Given grammar G:

S XbYa | Z

X l | a | Y

Y b | ba | X

Z bZH

H abb

 

A)    Give an equivalent grammar without l productions

 

 

 

 

 

 

 

 

 

 

B)    Remove unit productions from grammar obtained in part (A)

 

 

 

 

 

 

 

 

 

 

 

 

C)    Remove useless productions from grammar obtained in part (B)

 

 

 

 

 

 

 

 

 

 

 

 

 

Q7 ) (8 points)

Using the construction in your textbook, convert the following to Greibach normal form.

S XA | BB

B b | SB

X b

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Q8) (15 points) Construct an NPDA for:

S = {0,1}.

L = {w | wS* and w has equal and even number of 0s and 1s }.

For example 00101101, 10101001 etc. are in L, while 010110 is not in L.

 

(IMPORTANT NOTE: You must clearly write your strategy for solving the problem and also write comments against each transition of npda. Failure to do so shall result in deduction in marks. Your score shall depend on how clearly (and neatly) you present your answer).

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Q9 ) (14 points) Construct an Turing Machine for (draw the state diagram):

S = {0,1}.

L = {w | wS* and w does not contain exactly twice as many 0s as 1s }.

 

(IMPORTANT NOTE: You must clearly write your strategy for solving the problem and also write comments describing each state of Turing machine. Failure to do so shall result in deduction in marks. Your score shall depend on how clearly (and neatly) you present your answer).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Q10) (7 points)

 

Given a Turing machine M=(Q,, G,d, , F)

Q = {q0, q1, q2}

= {a, b}

G = {a, b, }

F= {q2}

 

If you were constructing unrestricted grammar G(V, T, S, P), which generates the language accepted by Turing machine M then:

A)    What production rules would you add to the grammar to allow derivations

 

S* # x qf y                    for all x, y in {G-{}}* and all qf F

 

For G(V,T,S,P) take:

T =

V = { G - } Q { #} {S, A}

 

 

 

 

 

 

 

 

 

 

B)    What production rules would you add to the grammar if Turing machine M has transition rule d(q0, a) = (q0, a, R) ?

 

 

 

 

 

 

C)    What production rules would you add to the grammar if Turing machine M has transition rule d(q0, b) = (q1, b, L) ?