- 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