In the name of ALLAH, the most beneficient, the most merciful

Theory of Automata (CS402)

Multiple Choice Questions (MCQs)

 

Objective Questions

Question

A regular language can be:

  1. irregular
  2. infinite
  3. non-deterministic
  4. None of the given options

Answer: 2 Chapter No.  

Question

All possible combinations of strings of a language including null string is referred as:

  1. Concatenation of a language with itself
  2. Kleene star closure of a language
  3. Multiplication of a language with itself
  4. Addition of a language with itself

Answer: 2 Chapter No.  

Question

We cannot construct an NFA for the language of ______ defined over alphabet set {a,b}.

  1. Even even
  2. Odd
  3. Palindromes
  4. Integers

Answer: Chapter No.  

Question

The minimum length of the strings(except null string) of a language that starts and ends in different letters will be

  1. 1
  2. 2
  3. 3
  4. 4

Answer: 2 Chapter No.  

Question

For every three regular expressions R, S, and T, the languages denoted by R(S U T) and (RS) U (RT) are the ________.

  1. Same
  2. Different
  3. R(S U T) is Greater
  4. None of the given options

Answer: Chapter No.  

Question

There ______ a language for which only FA can be built but not the RE.

  1. is
  2. cannot be
  3. may be
  4. may not be

Answer: Chapter No.  

Question

The language {a ab aba bab} is ________.

  1. Irregular
  2. Regular
  3. Recursive
  4. None of the given options

Answer: Chapter No.  

Question

If R is a regular language and L is some language, and L U R is a _______, then L must be a ________.

  1. Regular language
  2. Finite Automaton
  3. NFA
  4. Irregular language

Answer: Chapter No.  

Question

In _______ there must be transition for all the letters of a string.

  1. NFA
  2. GTG
  3. TG
  4. FA

Answer: Chapter No.  

Question

If we have a finite language and the number of states in the FA is n then the maximum number of letters in the each word of the language that will be accepted by the given FA will be:

  1. 1
  2. n-1
  3. n+1
  4. n

Answer: Chapter No.  

Question

A string will be accepted by an NFA if there exist _______one successful path.

  1. atmost
  2. atleast
  3. maximum
  4. none of the given options

Answer: Chapter No.  

Question

Let FA3 be an FA corresponding to FA1FA2, then the initial state of FA3 must correspond to the initial state of

  1. FA1 only
  2. FA2 only
  3. FA1 or FA2
  4. FA1 and FA2

Answer: Chapter No.  

Question

Decomposing a string into its valid units is referred as:

  1. Decomposing
  2. Splitting
  3. Tokenizing
  4. Dividing

Answer: Chapter No.  

Question

FA and _______ are same except that _______ has unique symbol for each transition.

  1. FA,TG
  2. NFA,TG
  3. NFA,FA
  4. GTG,NFA

Answer: Chapter No.