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

Theory of Automata (CS402)

Multiple Choice Questions (MCQs)

Objective Questions

  1. To examine wheather a certain FA accepts any words, it is required to seek the paths ________ state.

    1. from initial to initial back
    2. from final to back final
    3. from final to initial
    4. from initial to final
  2. Identify the TRUE statement about following CFG:
    S -> SB|AB
    A -> CC
    B ->b
    C -> a

    1. The given CFG has 8 Nonterminals
    2. The given CFG is in CNF
    3. The given CFG is not in CNF
    4. The given CFG has 8 Terminals
  3. 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
  4. If an FA has N states then it must accept the word of length

    1. N+1
    2. N-1
    3. 2N
    4. N
  5. The CFG S-->aSa | bSb | a | b | ^ represents ________ language.

    1. EVEN-EVEN
    2. ODD-ODD
    3. EQUAL
    4. PALINDROME
  6. A regular language can be:

    1. irregular
    2. infinite
    3. non-deterministic
    4. None of the given options
  7. 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
  8. A problem that has decision procedure is called ________ problem.

    1. decidable
    2. infinite
    3. un-decidable
    4. Regular language
  9. In large FA with thousands of states and millions of directed edges, without an effective procedure it is ________ to find a path from initial to final state.

    1. may be good
    2. always impossible
    3. Always easy
    4. Impossible
  10. ________ is an operation that takes out a letter from the top of the STACK.

    1. PUSH
    2. WRITE
    3. APPEND
    4. POP
  11. "CFG" stands for ________.

    1. Context Free Graph
    2. Context Finite Graph
    3. Context Finite Grammar
    4. Context Free Grammar
  12. The derivation of a word w, generated by a CFG, such that each step, a production is applied to the left most nonterminal in the working string, is said to be ________.

    1. Right most derivation
    2. Left most Terminal
    3. Left most derivation
    4. Right most Terminal
  13. In _______ there must be transition for all the letters of a string.

    1. NFA
    2. GTG
    3. TG
    4. FA
  14. 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
  15. Decomposing a string into its valid units is referred as:

    1. Decomposing
    2. Splitting
    3. Tokenizing
    4. Dividing
  16. We cannot construct an NFA for the language of ______ defined over alphabet set {a,b}.

    1. Even even
    2. Odd
    3. Palindromes
    4. Integers
  17. Which of the following states is not part of PDA?

    1. START
    2. REJECT
    3. ACCEPT
    4. WRITE
  18. Which of the following are called as Halt states in PDA?

    1. Accept and Reject
    2. Start and Accept
    3. Read and Reject
    4. Start and Reject
  19. In conversion form of PDA, no two ________ states exist in a row without ________ state.

    1. POP, REJECT
    2. PUSH, START
    3. PUSH, READ
    4. POP, READ
  20. Choice of path can be determined by left most derivation of the string belonging to CFL at ________ state.

    1. ACCEPT
    2. POP
    3. PUSH
    4. REJECT
  21. 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
  22. 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
  23. 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
  24. 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
  25. A ________ is the one for which every input string has a unique path through the machine.

    1. nondeterministic PDA
    2. deterministic PDA
    3. PUSHDOWN store
    4. Input Tape
  26. In a CFG, the non-terminals are denoted by ________.

    1. Numbers
    2. Capital letters
    3. Small letters and numbers
    4. Small letters
  27. The locations into which we put the input letters on "Input Tape" are called ________.

    1. alphabets
    2. elements
    3. cells
    4. words
  28. The language {a ab aba bab} is ________.

    1. Irregular
    2. Regular
    3. Recursive
    4. None of the given options
  29. In a CFG the non-terminal that occurs first from the left in the working string, is said to be ________.

    1. Left most derivative
    2. Left most nonterminal
    3. Least Significant nonterminal
    4. Most Significant nonterminal
  30. FA and _______ are same except that _______ has unique symbol for each transition.

    1. FA,TG
    2. NFA,TG
    3. NFA,FA
    4. GTG,NFA
  31. 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