**The basic limitation of an FSM is that**

**a) it does not have the capability to remember information**

**b) it sometimes recognizes grammars that are not regular**

**c) it sometimes fails to recognize grammars that are regular**

**d) all of the above**

**Ans is a**

**2. Palindromes can’t be recognized by any FSM because**

**a) an FSM does not have the capability to remember information**

**b) an FSM cn’t deterministically fix the mid-point**

**c) even if the mid-point is known, an FSM can’t find whether the second half of the string matches the first half**

**d) none of the above**

**Ans is a,b,c**

**3. An FSM can be considered a TM**

**a) of finite tape length, rewinding capability and unidirectional tape movement**

**b) of finite tape length, without rewinding capability and unidirectional tape movement**

**c) of finite tape length, without rewinding capability and bidirectional tape movement**

**d) of finite tape length, rewinding capability and bidirectional tape movement**

**Ans is b**

**4. TM is more powerful than FSM because**

**a) the tape movement is confined to one direction**

**b) it has no finite state control**

**c) it has the capability to remember arbitrary long sequences of input symbols.**

**d) none of the above**

**Ans is c**

**5. The language of all words(made up of a’s and b’s) with at least two a’s can be described by the regular expression**

**a) (ab)*a and a(ba)***

**b) (a+b)* and (a*+b)***

**c) (a*+b)* and (a+b)***

**d) none of the above**

**Ans is a,b,c**

**6. Set of regular languages over a given alphabet set, is not closed under**

**a) union**

**b) complementation**

**c) intersection**

**d) none of the above**

**Ans is d**

**7. Any given Transition graph has an equivalent**

**a) regular expression**

**b) DFSM**

**c) NDFSM**

**d) none of the above**

**Ans is a,b,c**

**8. The following CFG**

**S -> aS | bS | a| b**

**is equivalent to the regular expression**

**a) (a*+b)***

**b) (a+b)***

**c) (a+b)(a+b)***

**d) (a+b)*(a+b)**

**Ans is c,d**

**9. Any string of terminals that can be generated by the following CFG**

**s -> XY**

**X -> aX | bX | a**

**Y -> Ya | Yb | a**

**a) has at least one b**

**b) should end in an ‘a’**

**c) has no consecutive a’s or b’s**

**d) has at least two a’s**

**Ans is d**

**10. 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 b’s**

**c) even number of a’s and even number of b’s**

**d) odd number a’s and even number of b’s**

**Ans is a**

**11. Let L(G) denote the language generated by the grammar G. To prove set A=L(G),**

**a) it is enough to prove that an arbitrary member of A can be generated by grammar G**

**b) it is enough to prove that an arbitrary string generated by G, belongs to set A**

**c) both the above comments (a) and (b) are to be proved**

**d) either of the above comments (a) or (b) is to be proved**

**Ans is c**

**12. Choose the correct statements.**

**a) All languages can be generated by CFG.**

**b) Any regular language has an equivalent CFG.**

**c) Some non-regular languages can’t be generated by any CFG.**

**d) Some regular languages can’t be generated by any CFG.**

**Ans is b,c**

**13. Which of the following CFG’s can’t be simulated by an FSM?**

**a) S -> Sa | a**

**b) S -> abX**

**X -> cY**

**Y -> d | aX**

**c) S -> aSb | ab**

**d) none of the above**

**Ans is c**

**14. CFG is not closed under**

**a) union**

**b) Kleene star**

**c) complementation**

**d) product**

**Ans is c**

**15. The intersection of a context free language and a regular language**

**a) need not be regular**

**b) need not be context free**

**c) is always regular**

**d) is always context free**

**Ans is c,d**

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

**a) abaabaaabaa**

**b) aaaabaaaa**

**c) baaaaabaaaab**

**d) baaaaabaa**

**a,b and c****b,c and d****a,b and d****a,c and d**

**17. A PDM behaves like a TM when the number of auxiliary memory it has is **

**a) 0**

**b) 1 or more**

**c) 2 or more**

**d) none of the above **

**Ans is c**

**18. Which of the following is accepted by an NDPDM, but not by a DPDM?**

**a) All strings in which a given symbol is present at least twice**

**b) Even palindromes(i.e. palindromes made up of even number of terminals).**

**c) Strings ending with a particular terminal.**

**d) None of the above**

**Ans is b**

**19. CSG can be recognized by a**

**a) FSM**

**b) DPDM**

**c) NDPDM**

**d) linearly bounded memory machine**

**Ans is d**

**20. Choose the correct statements.**

**a) An FSM with 1 stack is more powerful than an FSM with no stack.**

**b) An FSM with 2 stacks is more powerful than a FSM with 1 stack.**

**c) An FSM with 3 stacks is more powerful than an FSM with 2 stacks.**

**d) All of above**

**Ans is a,b**