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 - 'M2' 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(M2)

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  {anbm: n>=0, m>=0} except a3b3.  Is L regular? If so give the regular expression.

Yes, L is regular language

r = l + a* + b* + ab* + a2b* + a3b + a3b2 + a3b4b* + a4a*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 = r1 a r1 b r1 c r1  +  r1 a r1 c r1 b r1  +  r1 b r1 a r1 c r1   +  r1 b r1 c r1 a r1  +  r1 c r1 a r1 b r1  +  r1 c r1 b r1 a r1

where r1 = (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 = { axbyaz :  y>x+z,  x>=0,  z>=0 }

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

Taking w = am b2m+1 am  (wÎ L)

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 wi = xyiz ÎL for all i=0, 1, 2, ….

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

w = am-k ak b2m+1 am

wi = am-k (ak)i b2m+1 am

Taking i=2

w2 = am+k b2m+1 am

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