1. All strings having equal number of a and b can be recognized by

A. DFA
B. NDFA
C. PDA
D. All of these

2. The following CFG

S->aB|bA, A->a|aS|bAA, B->b|bS|aBB
generates strings of terminals that have

A. Equal number of a's and b's
B. Odd number of a's and odd number of b's
C. Even number of a's and even number of b's
D. Not equal number of a's and b's

3. The Language accepted by Finite Automata is

A. Context free
B. Regular
C. Non Regular
D. Context Sensitive

A. (c) (a) (b) (d)
B. (c) (b) (a) (d)
C. (c) (b) (d) (a)
D. (c) (a) (d) (b)

5. Which of the following statements is True?

A. A Turing Machine is more powerful than finite state machine because it has no finite state
B. A Finite State Machine can be assumed to be a turing machine of finite tape length without rewinding capability and undirectional tape movement
C. Both A and B
D. None of the above

6. The basic limitation of a FSM is that

A. It cannot remember arbitrary large amount of information
B. It sometimes recognizes grammar that are not regular
C. It sometimes fails to recognize grammars that are regular
D. All of the above

7. A Pushdown automata is different than a Finite automata by

A. A Read Head
B. A Memory in the form of Stack
C. A Set of States
D. All of the above

8. Pumping Lemma is used for proving

A. A given Grammar is Regular
B. A given Language is Regular
C. A given Language is not Regular
D. All of the above

9. Consider the regular expression (a + b) (a + b) ... (a + b) (n-times). The minimum number of states in finite automaton that recognizes the language represented by this regular expression contains

A. n states
B. n + 1 states
C. n + 2 states
D. 2n states

10. Finite state machine___________recognize palindromes.

A. Can
B. Cannot
C. May
D. May not

11. A Turing Machine

A. Is a simple mathematical model of general purpose computer
B. Models the computing power of any computer
C. Is capable of performing any calculation which can be performed by any computing machine
D. All of the above

12. A Recursive Enumerable Language is

A. Accepted by TM
B. Not accepted by TM
C. Sometimes accepted and sometimes not accepted
D. None of the above

13. Given the language L = {ab, aa, baa}, which of the following strings are in L* ?