Formal Languages MCQ Test 1

1. What is the primary characteristic of a context-free grammar?

2. What is the purpose of a context-free grammar in the study of formal languages?

3. In the Chomsky hierarchy, which type of grammar is associated with context-free languages?

4. Which of the following machines can recognize context-free languages?

5. In the Chomsky hierarchy, which type of grammar generates languages recognizable by deterministic pushdown automata?

6. Which of the following machines is a deterministic model of computation?

7. Which of the following is not a property of regular languages?

8. What is the language generated by a regular expression (a|b)*?

9. Which of the following is the most complex type of automaton?

10. In the Chomsky hierarchy, which type of grammar is the most restrictive?

11. Which of the following is a non-deterministic model of computation?

12. Which type of automaton is capable of recognizing context-sensitive languages?

13. Which type of grammar generates the set of all strings over the alphabet?

14. What defines a regular language?

15. Which of the following is the most basic type of automaton?

16. What does the Pumping Lemma for regular languages guarantee?

17. Which of the following languages is always regular?

18. What does the Pumping Lemma for context-free languages guarantee?

19. Which of the following is a valid operation on regular languages?

20. Which of the following machines can recognize context-sensitive languages?