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