**Q1)** **(10 points)
**

1. A language is
defined very generally as a subset of
___________S*_______

2.
Given a
regular language L, Is L / L regular or non-regular? __Regular__

(Note: '/' indicates right
quotient)

3. Linear grammar
only generates those languages that are accepted by DFA or NFA (True/False) ___False_____

4. Regular expression r = (aa*b)* (aa* + l)

a) Give one string that is **not** in L(r)
__bba___________________

b) r is equivalent to: [3]

i) (ab)* (a+l) ii) a*(ab)* iii) (b+ba)* iv) (a+ab)*

v) (aa*b)* vi) None of these

5.
Give the equivalent simplified regular expression for [3]

r
= (a + b*)* (a + l)

(Simplify as much as possible) ___(a+b)*_____________

**Q2
)**** (8 points) **Give the Left
Linear Grammar for the following finite automata (show all steps)

ab

1) For the above finite automata 'M', construct an equivalent NFA with a
single final state

2) Construct an NFA - 'M_{2}' that accepts the reversal of L(M) (i.e. make the initial state final and final state
initial and reverse the direction of edges)

3) Write the Right Linear Regular Grammar for L(M_{2})

4) Reverse the grammar in step (3) to get the Left Linear Grammar for L(M).

**Q3
)**** (8 points)**

L is a
language consisting of all strings in {a^{n}b^{m}: n>=0,
m>=0} except a^{3}b^{3}.
Is L regular? If so give the regular expression.

Yes, L is regular language

r = l + a* + b* + ab* + a^{2}b*
+ a^{3}b + a^{3}b^{2} + a^{3}b^{4}b* +
a^{4}a*b*

**Q4
)**** (7 points)**

S = {a,b,c}

Find the
regular expression of all strings which have at least one occurrence of each
symbol in S

**regexp
r = ****r _{1}**

where r_{1}
= (a+b+c)*

**Q5
)**** (12 points**)

**A)** For S = {0,1}, construct a DFA that accepts all decimal numbers in
binary representation that are multiples of 3. (Full credit: if you do it in
the minimum number of states possible)

Also write your strategy for solving this problem For each number 'x' check if x mod 3 is 0, 1 or 2. The states in the DFA (numbered 0, 1 and 2) shall represent information about the remainder of the number when divided by 3. E.g. 111 (decimal 7) shall end up in state-1 because 7 mod 3 is 1. Similarly, 1000 (decimal 8) shall end in state-2 as 8 mod 3 is 2. etc. All numbers 'x' that have x mod 3=0 shall be accepted.

1 0

B) Write down the regular expression for the automaton found in part (A). Show all the steps.

( 0 + 1 (0 1* 0)* 1 )*

**Q6
)**** (7 points**) S = {0,1}

You are given the two DFA's M1 & M2 such that:

L(M1) accepts all numbers in binary representation that are a multiple of 2

L(M2) accepts all numbers in binary representation that are a multiple of 3

Using these DFA's how would you construct a finite automaton that accepts all binary numbers that are not a multiple of 6.

You are not asked to draw an automaton just give a precise description of steps required.

L(M1)
È L(M2)

OR

( L(M1)
Ç L(M2) )

** Q7 ) (10 points**) Convert the
following NFA to an equivalent DFA

**Q8
)**** (10 points)**

Using Pumping Lemma prove that the following language is not
regular

(vague arguments are not acceptable)

**L = { a ^{x}b^{y}a^{z} : y>x+z,
x>=0, z>=0 }**

Proof by Contradiction:

Assume that L is a regular language accepted by an m-state
DFA.

Taking w = a^{m }b^{2m+}^{1 }a^{m}

w
can be decomposed as w=xyz, with |xy| <= m, and |y| >=1. Therefore, y
consists of entirely a's.

If L is a regular language
then w_{i} = xy^{i}z ÎL for all i=0, 1, 2, ….

Assume |y|=k, where 1£ k £
m

w = a^{m-k} a^{k} b^{2m+}^{1} a^{m}^{}

w_{i} = a^{m-k} (a^{k})^{i} b^{2m+1}
a^{m}

Taking i=2

w_{2} = a^{m+k} b^{2m+}^{1} a^{m}

2m+1 !> 2m + k where 1£ k £
m

Therefore, we have established a contradiction of the
pumping lemma and L cannot be a regular language.

**Q9) (8 points) **

Given the
following NFA, construct an equivalent Generalized Transition Graph after
removing state-1. The Generalized Transition Graph must have a single final
state.

b

1) Make an equivalent NFA with a single final
state (State-3) and then remove state-1

aa