Discrete Mathematics Set 15

Computer Science Engineering (CSE)

Practice Mode Previous Next
On This Page

This set of Discrete Mathematics Multiple Choice Questions & Answers (MCQs) focuses on Discrete Mathematics Set 15

Q1 | If R= {(x, 2x)} and S= {(x, 4x)} then R composition S=____.
  • {(x, 4x)}
  • {(x, 2x)}
  • {(x, 8x)}
  • {(x, 10x)}
Answer: {(x, 8x)}
Q2 | If R= {(x, 2x)} and S= {(x, 5x)} then R composition S=____.
  • {(x, 4x)}
  • {(x, 2x)}
  • {(x, 8x)}
  • {(x, 10x)}
Answer: {(x, 10x)}
Q3 | A regular grammar contains rules of the form _____.
  • A tends to AB
  • AB tends to a
  • A tends to aB
  • AB tends to CD
Answer: A tends to aB
Q4 | A type-2 grammar contains the rules of the form is____.
  • a tends to AB
  • AaB tends to a
  • A tends to aBC
  • AB tends to CD
Answer: A tends to aBC
Q5 | Let R={(1, 3), (4, 2), (2, 2), (3, 3), (1, 1),(4,4)} be a relation on the set A={1, 2, 3, 4}. Therelation R is ____.
  • transitive
  • reflexive
  • not symmetric
  • function
Answer: not symmetric
Q6 | The NAND statement is a combination of ______.
  • NOT and AND
  • NOT and OR
  • AND and OR
  • NOT or OR
Answer: NOT and AND
Q7 | The NOR statement is a combination of ________.
  • NOT and AND
  • NOT and OR
  • AND and OR
  • NOT or OR
Answer: NOT and OR
Q8 | If a relation is reflexive then in the graph of a relation there must be a loop at _____.
  • each node
  • only first node
  • any two nodes
  • only first and last nodes
Answer: each node
Q9 | Which of the following traversal techniques lists the nodes of binary search in ascendingorder?
  • pre order
  • post order
  • in order
  • root order
Answer: in order
Q10 | The grammar G ={{S},{0,1},P,S}} where P={S tends to 0S1 , S tends to S1} is a ________.
  • recursively enumerable grammar.
  • regular grammar
  • context sensitive grammar
  • context free grammar
Answer: context free grammar
Q11 | Which of the following regular expressions identifiers are true?
  • (r*)* = r
  • (r+s)* = r* . s*
  • r*.s* = r* + s*
  • (r.s)* = r*/s*
Answer: (r*)* = r
Q12 | In a grammar or language LAMDA is used to denote _______.
  • empty word
  • entire set
  • set of words
  • set of letters
Answer: empty word
Q13 | The number of letters in a word is called ________.
  • length
  • string
  • syntax
  • alphabet
Answer: length
Q14 | If r is a regular expression then r* is a _______ expression.
  • regular
  • irregular
  • isomorphic
  • homomorphic
Answer: regular
Q15 | An example for regular grammar is _____.
  • S tends to Ab
  • AB tends to SAB
  • S tends to aB
  • S tends to aBB
Answer: S tends to aB
Q16 | If all the productions have single non-terminal in the left hand side then the grammardefined is ________grammar.
  • context free
  • context sensitive
  • regular
  • phrase structure
Answer: context free
Q17 | In Backus Naur Form the symbol:: = is used instead of _______.
  • { }
  • tends to
  • <>
  • $
Answer: tends to
Q18 | Any subset L of A* is called ________ over A.
  • Language
  • Syntax
  • Alphabet
  • Word
Answer: Language
Q19 | Let S be a start symbol and S -> aA, A -> BA, A -> a, B -> b be the productions in agrammar then one of the string derived form the grammar is _____.
  • baba
  • bbaa
  • abba
  • aabb
Answer: abba
Q20 | If S is a start symbol and S -> AB, A -> aB, B -> b are the productions then a stringgenerated by the grammar is _______.
  • baa
  • aba
  • abb
  • bab
Answer: abb
Q21 | In FSA ,the notation for M being in state S0, reading the input symbol a, moving one cellright and reaching the state S1 is given by ________.
  • f(Si , x) = Sj
  • f(S0 , a) = S1
  • f(Si , a) = Sj
  • f(S0 , x) = S1
Answer: f(S0 , a) = S1
Q22 | If "S -> aS, S -> a" are the productions in a grammar G, then the grammar is called_____.
  • regular grammar
  • phrase structure grammar
  • context free grammar
  • context sensitive grammar
Answer: regular grammar
Q23 | The rank of the incidence matrix of any connected graph G with n vertices is ______.
  • n
  • n+1
  • n-1
  • n-2
Answer: n-1
Q24 | The number of 1's in each row of an incidence matrix of a graph G is equal to _____.
  • the degree of the corresponding vertices
  • the sum of degrees of all vertices
  • the degree of the initial vertex
  • the degree of the terminal vertex
Answer: the degree of the corresponding vertices
Q25 | Each column of an incidence matrix of a graph G has exactly _______.
  • one 1's
  • two 1's
  • one 2's
  • two 2's
Answer: two 1's
Previous Next