TOC : Question Bank

UNIT-I

1.       Show by the principle of mathematical induction that n²-4n² is divisible by 3 for all n>0. (6)

2.       Define Kleen’s closure and Transitive closure.                                            (4)

3.       Consider the two regular expressions:   r=0˟+1˟ and   s=01*+10*+1*0+(0*1)*.

(a)    Find a string corresponding to s but not to r.

(b)    Find a string corresponding to both r and s.

(c)    Find a string in {0,1}* corresponding to neither r nor s.                     (6)

4.       Let L={0ⁿ1ⁿ|n>=0}. Show that L is not regular.                                             (6)

5.       Give the Regular expressions for the following languages:

(¡)  For Ʃ= {a,b},set of all string with at most  two ‘a’s                                (4)

(ii) L={ƹ,a,b,aa,ab,ba,bb}

6.       (a)Define the following formally with example:                                            

  (i)Alphabet.   (ii)Non deterministic finite automata.

   (iii)Deterministic finite automata.        (6)                               

(c)    An NFA with states 1-5 and input alphabet{a,b}has following transition table:

q δ(q,b) δ(q,b) 1 {1,2} {1} 2 {3} {3} 3 {4} {4} 4 {5}  ɸ 5  ɸ {5}

i)Draw transition diagram. ii)Calculate δ*(1,ab). iii)Calculate δ*(1,abaab).   

       7. a)  Explain the property pumping lemma of regular set. Where do we apply this

               property ?  Give the suitable example.                                                   (6)

            b) Design the NFA to recognize the following sets of strings:abc,abd,aacd.

     Assume that alphabet is {a,b,c,d}.Give the transition table and transition

    diagram both.                                                     (6)               

             c)  Differntiate between NFA and DFA.                     (4)

       8. Design a FA from given regular expression 10+(0+11)0*1.                                 (10)                                                                                                        UNIT- II

      1.Define Moore and  Mealy machine and how the equivalence of Moore and

         Mealy machine, can be  established with example. (6)                                                                 

      2.Convert the following the Moore machine into equivalent Mealy machine.

         M=({q0,q1},{a,b},{0,1},δ,λ,q0).                                                                         (4)

3. Give the Mealy machine for the following processes  “For input from (0+1)*,if input ends

    in   101,output X; if input ends in 110,output Y,otherwise output Z”.                     (8)

4. Define Mealy machine . Construct a Mealy machine which can output EVEN/ODD , if

    the total number of 1’s in the input is even or odd.The input symbols are -0 and 1.(5)

5. (a)Design a Mealy machine to find 2’s compliment of a given binary number.                 (6)

    (b)Design a Mealy machine to find 1’s compliment of a given binary number      (6)

6. Find the regular expression corresponding to each of the following subset of {0,1}*

   a)The language of all strings not containing the substring 000.

   b)The language of all strings that do not contain the substring 110

   c)The  language of all strings  containing both the 101 and 010 as a substring .   (10)

7. Convert NFA and DFA  for accepting all possible strings of 0’s and 1’s not containing 101

    substring.   Find  as a  regular expression for it.                                                               (8)

8. Show that P*(QP*)*=(P+Q)*.                                                               (4)

9. Prove or disprove each of the following about the regular expression :                              (4)

    1)(RS+R)*RS=(RR*S)*  (2)(R+S)*=R*+S*.

                             UNIT-III

                               

1.       Write short note on Chomsky hierarchy.                               (8)

2.       Construct the CFG for the regular expression (0+1)*  (8)

3.       Give CFG for set of odd length settings in {0,1}* with middle symbol ‘1’ (4)

4.       In each case find context free grammer generating given language          (8)

a)The set of odd length strings in {a,b}* with middle symbol  a.

b)The set of even length strings {a,b}*with the two middle symbols equal.

       5. Give an ambiguous grammer for if then else statement and then rewrite

            an equivalent   unambiguous grammer.                                                     (8)

6. Show that following grammer is ambiguous, S->a|absb|a A b, A->bs | a A A b   (6)

       7. Describe the closure properties of  CFL.         (10)

       8.Construct  regular grammer to FA with example.                                                    (5)

      9.Define and explain recursive and recursively ennumerable languages.          (4)

      10.Explain concurrent grammer and graph grammer.                                                                (4)

      11.Prove “ if L is recursive language so is its  compliment L^c ”                                   (5)

      12.Construct the given CFG to   Greibach Normal Form.                                           (8)

            S->CA,    A->a,      C->aB|b.