CS402Theory of Automata Quiz MCQS #Objective #Questions #Finalterm
1. Set of all palindromes over {a, b} is:
 Regular
 Regular and finite
 Regular and infinite
 Nonregular
2. The unit production is ___
 Terminal>Terminal
 Terminal>Non Terminal
 Non terminal>Terminal
 Non terminal>Non Terminal
3. Which of the following cannot be represented by a regular expression?
 String of 0’s with an odd length
 String of 0’s with a prime length
 Language of eveneven
 Language of oddodd
4. If R is regular language and Q is any language (regular/nonregular), then Pref(___in ___) is regular.
 Q, Q
 Q, R
 R, Q
 R, R
5. If an FA accepts a word then there must exist a path from ___
 Initial to final state
 Initial to each state
 Initial to each state but not to final state
 Initial to final state by traversing each state
6. a^n b^n generates the ___ language
 regular
 non regular
 EQUAL and non regular
 EQUAL and regular
7. A language ending with ‘b’ partitions Σ* into ___ distinct classes.
 three
 four
 two
 five
8. Which of the following refers to the set of strings of letters that when concatenated to the front of some word in Q produces some word in R?
 Postf(R in Q)
 Postf(Q in R)
 Pref(Q in R)
 Pref(R in Q)
9. The CFG is said to be ambiguous if there exist at least one word of its language that can be generated by ___ production trees.
 one
 two
 more than one
 at most one
10. A problem that has decision procedure is called ___ problem
 Regular language
 undecidable
 infinite
 decidable
11. The language “PRIME” is an example of ___ language.
 regular but finite
 regular
 non regular but finite
 non regular
12. There is at least one production in CFG that has one___ on its left side.
 terminal
 null production
 unit production
 non terminal
13. For a non regular language, there exists ___ FA
 one
 at least one
 at most one
 no
14. Consider the following CFG:
S>aXbaYa
X>Y^ (NOTE: ^means NULL)
Y>bX
Which Nonterminal(s) is/are NOT nullable?
 S
 X
 Y
 S, X, and Y
15. One language can have ___ CFG(s)
 Only one
 At least one
 More than one
 At most one
16. If L1 and L2 are two regular languages, then they ___ expressed by FAs.

cannot be

maybe

can be

may or may not be
17. In a CFG, the nonterminals are denoted by ___

small letters

numbers

capital letters

small letters and numbers
18. If the FA has N states, then test the words of length less than N. If no word is accepted by this FA, then it will ___ word/words.

accept all

accept no

accept some

reject no