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

1.
A = L(a*), B
= {a^{n}b^{n} : n>=0}, A×B =
________________ (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=
{a^{n}b^{n} : 0<n<15} is a ___________________ language (regular
only/context-free only /both regular and context free / neither regular nor
context free)

7.
A={a^{m}b^{n}c^{n}
| m,n >=0} B=
{a^{n}b^{n}c^{m} | m,n>=0} C=AÇB={
______________ }
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= { a^{n}b^{n} | n>=0 }

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

** **

**Q5) (6
points)**

L =
{a^{x}b^{y}a^{z} ; 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=a^{2m}bbbaaaaa Î
L

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

According to
Pumping Lemma |y|=3 >1

w=xyz; x=
a^{2m-3, }y=aaa, z= bbbaaaaa

However
w=xy^{i}z = a^{2m-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 |
wÎS* and w has
** equal
and even** number of
0’s and 1’s }.

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 |
wÎS* and w **does not** contain exactly twice as many
0’s as 1’s }.

(**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 =
{q_{0}, q_{1}, q_{2}}

å = {a,
b}

G = {a, b,
ð}

F=
{q_{2}}

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 q_{f }y
ð · · · ð
for all x, y in {G-{ð}}* and all q_{f
}Î 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(q_{0},
a) = (q_{0}, a, R) ?

C)
What
production rules would you add to the grammar if Turing machine M has transition
rule d(q_{0},
b) = (q_{1}, b, L) ?