DISCRETE STRUCTURE MCQ SET 3

This entry was posted in DISCRETE STRUCTURE MCQ on by
1. The technique of automation with a stack as an auxiliary storage is called as

Pushdown Automata

2. Context Free Grammar(CFG) is

A language generator

 
3. A graph is a collection of 

Vertices and edges

4. A graph with no edges is called as

Empty graph or Trivial graph

5. A graph ‘G’, which is a connected acyclic graph is called as
Tree

Note: A tree has no cycles

6. A tree having a main node, which has no predecessor is called as

Rooted tree

7. All the vertices of a walk except the first and last vertices is called as

Internal vertices

8. In a tree, between every pair of vertices there is 

Exactly one path

9. Transitive and Irreflexive property imply
Asymmetric 
Shortcut:  

T and I = A

 
10. A graph ‘g’ is said to be Eulerian Graph if 
All vertices of graph ‘g’ is of even degree.
Tip: Eulerian graph=even degree
11. Context free languages are closed under

Union,keene closure

12. A bag contains 10 white balls and 15 black balls. Two balls are drawn in succession. Find out the probability that one is black and other is white.
1/2
Explantation:Total probability =(10+15)=25
So we have to take two balls from 25 balls, i.e., 25C2=300
Probability of choosing one white ball =10C1=10
probability of choosing one black ball=15C1=15
Therefore, Probability of getting one black ball and one white ball is
(10*15)/300=1/2

13. The collection of all subsets of a set is called as
Power set

14. A language is said to be regular only if it is accepted by a 
Finite automata

15. The intersection of a CFL and regular language is always
Regular and Context free.

16. The major difference between Moore machine and Mealy machine is
In Moore machine, the output depends only on the PRESENT state.

17. The recoginising capability of Non deterministic finite automata (NDFA) and deterministic finite automata (DFA)should be 
Same.

18. One of the limitation of Finite state automata (FSM) is that
It cannot remember arbitrary large amount of data.

19. A Finite state automata can be called as Turing machine (TM) because of.
Finite tape length, without rewinding capability, unidirectional tape movement.

20. A Turing Machine (TM) is more powerful than Finite State Automata (FSM) because
It has the capability to remember arbitrary long sequences of input symbols.

 

Leave a comment