Multiple Choice Questions On Discrete Structure - Set 1

Tuesday, 8 May 2012

1) Context free Grammar is ?
  1. A Compiler
  2. A language expression
  3. A regular expression
  4. None of these
Show/Hide Answer
Answer = B
Explanation: Context free Grammar generate the context free languages. These are defined by the rule of the form A -> b Where A a non terminal and b is the string of terminals.

2) The idea of an automation with a stack as auxiliary storage... ?
  1. Finite automata
  2. Push down automata
  3. Deterministic automata
  4. None of these
Show/Hide Answer
Answer = B 
Explanation: Push down automata manipulate the stack, as a part of performing a transition.

3) A Pushdown automata is.....if there is at most one transition applicable to each configuration ?

  1. Deterministic
  2. Non Deterministic
  3. Finite
  4. Non Finite
Show/Hide Answer
Answer = A 
Explanation:If in every situation only one transition is available as continuation of computation, then the result is a deterministic push down automation (DPDA).

4) The graphical representation of the transition of finite automata is ?

  1. Finite diagram
  2. State diagram
  3. Node diagram
  4. E-R diagram
Show/Hide Answer
Answer = B 
Explanation: State diagram is called the graphical representation of Finite automata.

5) If two sets A and B have no common elements i.e (A intersection B) has no element then such sets are known as ?
  1. Intersection
  2. Union
  3. Disjoint
  4. Complement
Show/Hide Answer
Answer = C 
Explanation:If two sets have no element in common then they are called disjoint sets.
6) The domain D of the relation R is defined as the.... ?
  1. Set of all elements of ordered pair which belongs to R
  2. Set of all last elements of ordered pair which belongs to R
  3. Set of all first elements of ordered pair which belongs to R
  4. None of these
Show/Hide Answer
Answer = C 
Explanation: No explanation for this question

7) 'A language is regular if and only if it is accepted by a finite automation' ?
  1. The given statement is true
  2. The given statement is false
  3. The given statement is partially true
  4. Sometime true, sometimes false
Show/Hide Answer
Answer = A 
Explanation: A regular language is accepted by the finite automation. Every regular language is context free.

8) Which of the following does not belong to the context free grammer?
  1. Terminal symbol
  2. Non-terminal symbol
  3. Start symbol
  4. End symbol
Show/Hide Answer
Answer = D 
Explanation:Context free grammar consist of terminal symbols, non terminal symbols, set of production rules, a start symbol but does not have any End symbol.

9) A regular grammar is a..... ?
  1. Context free grammar
  2. Non context free grammar
  3. English grammar
  4. None of above
Show/Hide Answer
Answer = A 
Explanation: Regular grammar is context free grammar. Such a grammar restricts its rules to a single non terminal on the left hand side and right hand side consisting of a single terminal.

10) The context free language are closed under... ?
  1. Union
  2. Kleene star
  3. Concatenation
  4. All of above
Show/Hide Answer
Answer = D 
Explanation: Context free language is closed under union, kleene star and concatenation.

Do You Like This? Please take 5 seconds to share with your firends.