Quiz on Theory of Computation

1.   Which string is not accepted by the following FSA?

                               

      a. 00110                b. 01010                      c. 11010                                           d. 00111

2.   Consider the following language L = {aⁿbⁿ|n ≥ 1} then  L is

      a.  regular              b. CSL but not CFL                c.  CFL but not regular        d. type 0 language but not type 1

3.   A language L is accepted by a FSA iff it is

      a. CFL                   b. CSL                         c. regular                                          d. recursive

4.   Which of the following strings is not generated by the following grammar? S → SaSbS | ε

      a. aabb                   b. abab                         c. aababb                                          d. aaabb

5.   Consider the following NFSA

       

The automaton accepts

      a. all words of the form {(ab)ⁿa|n ≥ 1}                             b. all words that end with a and ε  

      c. all words that end with a and not ε                              d. all words containing substring ba

6. Type-0 grammar is known as

a. Regular grammar                                                               b. context free grammar

c. context sensitive grammar                                                 d. recursive enumerable grammar

7. If NDFA contains Q number of states, then DFA contains

a. less than equal to 2^Q                                                                                            b. greater than equal to 2^Q

c. equal to 2^Q                                                                       d. All of the these

8. Regular language can be recognized by

a. turing machine                                                                   b. pushdown automata

c. finite state machine                                                                                                d. linear bounded automata

9.      For an undirected graph with n vertices and e edges, the sum of the degree of each vertex is equal to

a.      2n

b.      (2n-1)/2

c.       2e

d.      e²/2

10.  A graph with n vertices will definitely have a parallel edge or self loop of the total number of edges are

a.      more than n

b.      more than n+1

c.       more than (n+1)/2

d.      more than n(n-1)/2

11.  Which is not concerned with graph?

a.      Degree

b.      Vertex

c.       Edge

d.      Height

12.  Which is equivalent to ó?

a.      XOR

b.      XNOR

c.       NAND

d.      NOR

13.  A graph has n vertices and n-1 edges, then

a.      Graph has many cycle

b.      Graph has only one cycle

c.       Graph has no cycle

d.      None of the above

14.  How many handshakes are possible of 10 persons?

a.      10

b.      45

c.       10!

d.      None of the above

15.  If R={(a,b),(b,c),(c,a)} is

a.      Transitive                                            b. reflexive

c.       Symmetric                                           d. anti-symmetric

True and false

1.      NDFA can be converted into DFA.

2.      A tree has one cycle in it.

3.      A binary tree has two child node.

4.      Malayalam is a palindrome.

5.      Fishbone method is used in NDFA.

6.      DFA is a powerful machine.

7.      NDFA is more general machine.

8.      Next state of machine can be depends on input given and/or present state.

9.      Reflexive-transitive closure id denoted by R+

10.  Transitive closure is denoted by R*.

Fill in the blanks

1.      1331 is _____________

2.      Full form of NDFA_______________________________

3.      Full form if PDA ________________________________________

4.      Regular language accepts __________________________ grammar

5.      A finite state machine has ____________________ tuples

6.      Transition function has __________________ parameters

7.      Input symbol/alphabet is denoted by__________________

8.      Final state is denoted by double _______________

9.      Initial state is denoted by ________________

10.  An input given to state give same state, then the edge is called _______________________

Match the column

1.      Regular grammar                               a. Type 1

2.      Recursive grammar                            b. type 0

3.      Context sensitive grammar                c. type 2

4.      Context free grammar                       d. type 3

5.      Turing machine                                   e. recursive language

One word questions

1.      Draw transition table of

2.      Is, above automata is NDFA?

3.      What is palindrome?

4.      What is string?

5.      Define Automata?

6.      What is DFA?

7.      What is NDFA?

8.      Define production rule of Regular grammar.

9.      Full form of TOC.

10.  Which symbol is used to define transition function?