81.  The following diagram represents a finite state machine which takes as input a binary number from the least significant bit. Which one of the following is TRUE? 
a.  It computes 1's complement of the input number 
b.  It computes 2's complement of the input number 
c.  It increments the input number 
d.  It decrements the input number 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).It computes 2's complement of the input number

82.  The following finite state machine accepts all those binary strings in which the number of 1's and 0's are respectively 
a.  divisible by 3 and 2 
b.  odd and even 
c.  even and odd 
d.  divisible by 2 and 3 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).divisible by 3 and 2

83.  Consider the following Deterministic Finite Automata. Which of the following is true? 
a.  It only accepts strings with prefix as "aababb" 
b.  It only accepts strings with substring as "aababb" 
c.  It only accepts strings with suffix as "aababb" 
d.  None of the above 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).It only accepts strings with substring as "aababb"

84.  Consider the DFAs M and N given below. The number of states in a minimal DFA that accepts the language L(M) ∩ L(N) is __________. 
a.  0 
b.  1 
c.  2 
d.  3 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).1

85.  If the final states and nonfinal states in the DFA below are interchanged, then which of the following languages over the alphabet {a,b} will be accepted by the new DFA? 
a.  Set of all strings that do not end with ab 
b.  Set of all strings that begin with either an a or a b 
c.  Set of all strings that do not contain the substring ab 
d.  The set described by the regular expression b*aa*(ba)*b* 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).Set of all strings that do not end with ab

86.  Consider the following two finite automata. M1 accepts L1 and M2 accepts L2. Which one of the following is TRUE? 
a.  L1 = L2 
b.  L1 ⊂ L2 
c.  L1 ∩ L2' = ∅ 
d.  L1 ∪ L2 ≠ L1 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).L1 = L2

87.  Consider the following languages. Which one of the following statements is FALSE? 
a.  L2 is contextfree 
b.  L1 intersection L2 is contextfree 
c.  Complement of L2 is recursive 
d.  Complement of L1 is contextfree but not regular 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).Complement of L1 is contextfree but not regular

88.  Consider the below problem: 
a.  A 
b.  B 
c.  C 
d.  D 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).C

89.  Consider the following question 
a.  Push Down Automata (PDA) can be used to recognize L1 and L2 
b.  L1 is a regular language 
c.  All the three languages are context free 
d.  Turing machine can be used to recognize all the three languages 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).All the three languages are context free

90.  Consider the languages L1 = {0^i1^j  i != j}. L2 = {0^i1^j  i = j}. L3 = {0^i1^j  i = 2j+1}. L4 = {0^i1^j  i != 2j}. 
a.  Only L2 is context free 
b.  Only L2 and L3 are context free 
c.  Only L1 and L2 are context free 
d.  All are context free 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).All are context free
