Theory of Automata (CS402)

1. "CFG" stands for ________.

   1. Context Free Graph
   2. Context Finite Graph
   3. Context Finite Grammar
   4. Context Free Grammar

2. The locations into which we put the input letters on "Input Tape" are called ________.

   1. alphabets
   2. elements
   3. cells
   4. words

3. 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

4. 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

5. The language {a ab aba bab} is ________.

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

6. 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

7. If an FA has N states then it must accept the word of length

   1. N+1
   2. N-1
   3. 2N
   4. N

8. 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

9. 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

10. 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

11. 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

12. 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

13. 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

14. 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

15. 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

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

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

17. Which of the following states is not part of PDA?

    1. START
    2. REJECT
    3. ACCEPT
    4. WRITE

18. A regular language can be:

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

19. ________ is an operation that takes out a letter from the top of the STACK.

    1. PUSH
    2. WRITE
    3. APPEND
    4. POP

20. 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

21. 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

22. In a CFG, the non-terminals are denoted by ________.

    1. Numbers
    2. Capital letters
    3. Small letters and numbers
    4. Small letters

23. 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

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

    1. EVEN-EVEN
    2. ODD-ODD
    3. EQUAL
    4. PALINDROME

25. A problem that has decision procedure is called ________ problem.

    1. decidable
    2. infinite
    3. un-decidable
    4. Regular language

26. 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

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

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

28. 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

29. Decomposing a string into its valid units is referred as:

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

30. 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

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

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

Select a course code for Objective Questions:

ACC311 ACC501 BIF101 BIF401 BIF501 BIO101 BIO201 BIO202 BIO203 BIO204 BIO301 BIO302 BIO303 BIO401 BIO503 BNK603 BT101 BT201 BT301 BT302 BT401 BT402 BT403 BT404 BT405 BT406 BT501 BT504 BT505 BT604 CHE201 CHE301 CS001 CS101 CS201 CS202 CS204 CS301 CS302 CS304 CS311 CS401 CS402 CS403 CS408 CS501 CS502 CS504 CS506 CS508 CS601 CS602 CS604 CS605 CS607 CS609 CS610 CS614 CS707 CS710 ECO401 ECO402 ECO403 ECO404 EDU302 EDU401 EDU402 EDU501 EDU601 ENG101 ENG201 ENG301 ENG501 FIN611 FIN624 FIN625 ISL201 IT430 MCM101 MCM301 MGMT623 MGT101 MGT211 MGT301 MGT401 MGT402 MGT501 MGT502 MGT503 MGT510 MGT601 MGT603 MKT501 MKT610 MKT630 MTH101 MTH202 MTH302 MTH501 MTH601 MTH634 PAK301 PHY101 PHY301 PSY101 PSY403 PSY502 PSY512 SOC101 SOC301 SOC401 STA301 STA630 STA641 ZOO102 ZOO401 ZOO501 ZOO502 ZOO503 ZOO504 ZOO505 ZOO506 ZOO510 ZOO630

Select a course code for Subjective Questions:

ACC311 CS001 CS101 CS201 CS301 CS607 CS701 CS702 CS703 CS704 CS707 CS708 CS710 CS711 CS718 CS721 CS724 ECO401 ECO403 ENG101 ENG301 MGT703 MTH501 STA301