• ( 1 ) Let w be any string of length n is {0,1}*.Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?

    • 1) n-1
    • 2) n
    • 3) n+1
    • 4) 2n-1
    • Discussion in forum
      Answer : 3) n+1
      Solution : We need minimum n+1 states to build NFA that accepts all substrings of a binary string. For example, following NFA accepts all substrings of "010" and it has 4 states.

      fig shows the NFA that accepts all substrings of 010, the substrings are: 0, 01, 10 and 010








      discussion


      Answer : 3) n+1

    • ( 2 ) The minimum state automaton equivalent to the above FSA has the following number of states

    • 1) 1
    • 2) 2
    • 3) 3
    • 4) 4
    • Discussion in forum
      Answer : 2) 2
      Solution : q0 and q1 are the states that are required at most and hence the minium number of states is 2








      discussion


      Answer : 2) 2

    • ( 3 ) Write regular expression to denote a language L which accepts all the strings which begin or end with either 00 or 11

    • 1) [(00(0+1)* 11] + [11( 0 + 1)* 00]
    • 2) [(00+11) (0+1)+] + [( 0 + 1)+ (00+11)].
    • 3) [(00+11) (0+1)*] + [( 0 + 1)* (00+11)]
    • 4) (00+11) (0+1)* (00+11).
    • Discussion in forum
      Answer : 3) [(00+11) (0+1)*] + [( 0 + 1)* (00+11)]
      Solution : The regular expression can be categorized into two subparts.
      R= L1+L2
      L1= the strings which begin with 00 or 11.
      L2= the strings which end with 00 or 11.
      Let us find out L1 and L2.
      L1= (00 + 11) (any number of 0's and 1's )
      L1 = (00 + 11) (0+1)*
      Similarly L2 = (any number of 0's and 1's ) ( 00 + 11) = (0+1)* (00 + 11)
      Hence R= [(00+11) (0+1)*] + [( 0 + 1)* (00+11)].








      discussion


      Answer : 3) [(00+11) (0+1)*] + [( 0 + 1)* (00+11)]

    • ( 4 ) The language L = { 0i 2 1 i i>-0 } over the alphabet (0,1,2) is

    • 1) not recurcise
    • 2) is recursive and deterministic CFL
    • 3) is a regular language
    • 4) is not a deterministic CFL but a CFL
    • Discussion in forum
      Answer : 2) is recursive and deterministic CFL
      Solution : Let us first design a deterministic pushdown automata for the given language.
      For each occurrence of '0' , we PUSH X in the stack.
      When '2' appears, no stack operation is performed. But, state of the automata is changed.
      For each occurrence of '1' , we POP X from the stack.
      If at the end Z0 is on the stack top then input string is accepted
      We also design a Turing machine for the given language.
      When '0' appears in the input string , we replace it with X .Then, traverse to the rightmost corner and replace '1' with Y.
      We go back to the leftmost '0' and repeat the above process.
      While traversing rightwards from the beginning of the input string, if after X, '2' appears and after '2', Y appears then we reach the HALT state.
      Thus, the given language is recursive. Every recursive language is a CFL.








      discussion


      Answer : 2) is recursive and deterministic CFL

    • ( 5 ) A given grammar is called ambiguous if

    • 1) two or more productions have the same non-terminal on the left hand side
    • 2) a derivation tree has more than one associated sentence
    • 3) there is a sentence with more than one derivation tree corresponding to it
    • 4) brackets are not present in the grammar
    • Discussion in forum
      Answer : 3) there is a sentence with more than one derivation tree corresponding to it
      Solution :








      discussion


      Answer : 3) there is a sentence with more than one derivation tree corresponding to it

    • ( 6 ) A minimum state deterministic finite automation accepting the language L = {W |W € {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has

    • 1) 15 States
    • 2) 11 states
    • 3) 10 states
    • 4) 9 states
    • Discussion in forum
      Answer : 1) 15 States
      Solution :








      discussion


      Answer : 1) 15 States

    • ( 7 ) In a context-free grammar

    • 1) ε can't be the right hand side of any production
    • 2) terminal symbols can't be present in the left hand side of any production
    • 3) number of grammar symbols in the left hand side is not greater than the number of grammar symbols in the right hand side
    • 4) all of these
    • Discussion in forum
      Answer : 4) all of these
      Solution :








      discussion


      Answer : 4) all of these

    • ( 8 ) If s is a string over (0 + 1)* then let n0 (s) denote the number of 0's in s and n1 (s)the number of l's in s. Which one of the following languages is not regular?

    • 1) L = {s € (0 + 1)*n0 (s) is a 3-digit prime
    • 2) L = {s € (0 + 1)* | for every prefix s' of s, l 0 (s') - n1 (s') | <= 2 }
    • 3) L={s € (0+1)* | n0(s) - n1(s) | <= 4}
    • 4) L = {s € (0 + 1) | n0 (s) mod 7 = n1 (s) mod 5 = 0 }
    • Discussion in forum
      Answer : 3) L={s € (0+1)* | n0(s) - n1(s) | <= 4}
      Solution :








      discussion


      Answer : 3) L={s € (0+1)* | n0(s) - n1(s) | <= 4}

    • ( 9 ) Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

    • 1) Both DHAM3 and SHAM3 are NP-hard
    • 2) SHAM3 is NP-hard, but DHAM3 is not
    • 3) DHAM3 is NP-hard, but SHAM3 is not
    • 4) Neither DHAM3 nor SHAM3 is NP-hard
    • Discussion in forum
      Answer : 1) Both DHAM3 and SHAM3 are NP-hard
      Solution : There is a difference between SHAM and DHAM, that SHAM is used for finding a hamiltonian cycle in a graph but DHAM is the problem of determining if a graph exists in a Hamiltonian cycle. Also it is given that |v| id divisible by 3, hence the problem can be reduced from 3 SAT which further determines that SHAM and DHAM are NP hard








      discussion


      Answer : 1) Both DHAM3 and SHAM3 are NP-hard

    • ( 10 ) For two regular languages
      L1 = (a + b)* a and L2 = b (a + b ) *, the intersection of L1 and L2 is given by

    • 1) (a + b ) * ab
    • 2) ab (a + b ) *
    • 3) a ( a + b ) * b
    • 4) b (a + b ) * a
    • Discussion in forum
      Answer : 4) b (a + b ) * a
      Solution :








      discussion


      Answer : 4) b (a + b ) * a





Top