CS402-Theory of Automata Quiz MCQS #Objective #Questions #Finalterm
1. Set of all palindromes over {a, b} is:
- Regular
- Regular and finite
- Regular and infinite
- Non-regular
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 even-even
- Language of odd-odd
4. If R is regular language and Q is any language (regular/non-regular), 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
- un-decidable
- 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->a|Xb|aYa
X->Y|^ (NOTE: ^means NULL)
Y->b|X
Which Non-terminal(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 non-terminals 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
