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

Theory of Automata (CS402)

Multiple Choice Questions (MCQs)

Objective Questions

  1. The CFG S-->aSa | bSb | a | b | ^ represents ________ language.

    1. EVEN-EVEN
    2. ODD-ODD
    3. EQUAL
    4. PALINDROME
  2. A problem that has decision procedure is called ________ problem.

    1. decidable
    2. infinite
    3. un-decidable
    4. Regular language
  3. If an FA has N states then it must accept the word of length

    1. N+1
    2. N-1
    3. 2N
    4. N
  4. 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
  5. 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
  6. The locations into which we put the input letters on "Input Tape" are called ________.

    1. alphabets
    2. elements
    3. cells
    4. words
  7. 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
  8. 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
  9. Which of the following states is not part of PDA?

    1. START
    2. REJECT
    3. ACCEPT
    4. WRITE
  10. 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
  11. ________ is an operation that takes out a letter from the top of the STACK.

    1. PUSH
    2. WRITE
    3. APPEND
    4. POP
  12. 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
  13. 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
  14. In a CFG, the non-terminals are denoted by ________.

    1. Numbers
    2. Capital letters
    3. Small letters and numbers
    4. Small letters
  15. "CFG" stands for ________.

    1. Context Free Graph
    2. Context Finite Graph
    3. Context Finite Grammar
    4. Context Free Grammar
  16. 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
  17. 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
  18. A regular language can be:

    1. irregular
    2. infinite
    3. non-deterministic
    4. None of the given options
  19. 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
  20. We cannot construct an NFA for the language of ______ defined over alphabet set {a,b}.

    1. Even even
    2. Odd
    3. Palindromes
    4. Integers
  21. 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
  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. 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
  24. The language {a ab aba bab} is ________.

    1. Irregular
    2. Regular
    3. Recursive
    4. None of the given options
  25. 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
  26. In _______ there must be transition for all the letters of a string.

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

    1. Decomposing
    2. Splitting
    3. Tokenizing
    4. Dividing
  31. FA and _______ are same except that _______ has unique symbol for each transition.

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