Regular Languages and Context-Free Grammars MCQs

30 min Score: 0 Attempted: 0/30

1. Which of the following is a regular language?
(A) {a, b}*
(B) {aⁿbⁿ | n ≥ 0}
(C) {aⁿbⁿcⁿ | n ≥ 0}
(D) {ww | w ∈ {a, b}}

2. Which automaton recognizes regular languages?
(A) Finite Automaton
(B) Pushdown Automaton
(C) Turing Machine
(D) Linear Bounded Automaton

3. Which of the following operations always produces a regular language?
(A) Concatenation of two context-free languages
(B) Union of two regular languages
(C) Intersection of two context-free languages
(D) Complement of a context-free language

4. What is a deterministic finite automaton (DFA)?
(A) An automaton with multiple stacks
(B) An automaton with unlimited memory
(C) A non-deterministic automaton with ε-moves
(D) A finite automaton with exactly one transition for each symbol in each state

5. What does a context-free grammar (CFG) generate?
(A) Only regular languages
(B) Recursively enumerable languages
(C) Context-sensitive languages
(D) Context-free languages

6. Which of the following is an example of a context-free language?
(A) {ww | w ∈ {a, b}*}
(B) {aⁿbⁿcⁿ | n ≥ 0}
(C) {aⁿbᵐcⁿ | n, m ≥ 0}
(D) {aⁿbⁿ | n ≥ 0}

7. Which of the following is a terminal in a CFG?
(A) Symbols that appear in productions but are not further replaced
(B) Variables that can be replaced
(C) Start symbol
(D) Stack symbols

8. In CFG, what is the start symbol?
(A) A terminal symbol
(B) A non-terminal symbol from which derivation begins
(C) An input symbol
(D) Stack symbol

9. What is the Chomsky hierarchy level of regular languages?
(A) Type 0
(B) Type 3
(C) Type 2
(D) Type 1

10. What is the Chomsky hierarchy level of context-free languages?
(A) Type 2
(B) Type 1
(C) Type 0
(D) Type 3

11. Which operation may result in a non-regular language even if applied to regular languages?
(A) Union
(B) Concatenation
(C) Intersection with a context-free language
(D) Kleene star

12. Which of the following is true about regular expressions?
(A) They can describe exactly the regular languages
(B) They can describe all context-free languages
(C) They require a stack to be recognized
(D) They are equivalent to Turing Machines

13. Which of the following is a production in CFG?
(A) A → aB
(B) a → b
(C) 0 → 1
(D) None of the above

14. Which of the following languages is not regular?
(A) {a, b}*
(B) {aⁿbⁿ | n ≥ 0}
(C) {a, b}
(D) {ε}

15. How can a DFA be converted to a regular expression?
(A) Using the pumping lemma
(B) Using CFG derivation
(C) Using state elimination method
(D) Using stack operations

16. Which method is used to prove a language is not regular?
(A) Pumping lemma for regular languages
(B) Chomsky normal form
(C) Pushdown automaton
(D) Context-sensitive grammar

17. Which normal form is used for CFG simplification?
(A) Chomsky Normal Form (CNF)
(B) Regular Normal Form
(C) Deterministic Normal Form
(D) Greibach Normal Form (GNF)

18. What is the main difference between regular languages and context-free languages?
(A) Regular languages require a stack; CFLs do not
(B) Regular languages are Type 2; CFLs are Type 3
(C) CFLs can handle nested structures; regular languages cannot
(D) CFLs cannot be represented by CFG

19. What is the purpose of the Kleene star in regular expressions?
(A) Denotes optional occurrence
(B) Denotes zero or more repetitions
(C) Denotes exactly one occurrence
(D) Denotes sequence concatenation

20. Which of the following is true about linear grammars?
(A) Linear grammars are context-sensitive only
(B) All linear grammars are regular
(C) Linear grammars are Type 0
(D) All linear grammars are context-free

21. Which type of CFG rule is allowed in Greibach Normal Form?
(A) A → BC
(B) A → ε only
(C) A → aα, where a is a terminal and α is a string of non-terminals
(D) A → B

22. What does the pumping lemma for regular languages prove?
(A) Every language is regular
(B) A language is context-free
(C) All context-free languages are regular
(D) Certain languages are not regular

23. Which of the following is a context-free grammar rule?
(A) A → aB | b
(B) A → Bc | C
(C) All of the above
(D) A → ε

24. Which language can be represented by both a regular expression and a DFA?
(A) {aⁿbⁿ | n ≥ 0}
(B) {ww | w ∈ {a, b}}
(C) {aⁿbⁿcⁿ | n ≥ 0}
(D) {a, b}*

25. What is the closure property of regular languages?
(A) Closed under stack operations
(B) Closed under intersection with context-free languages
(C) Closed under addition only
(D) Closed under union, concatenation, and Kleene star

26. Which tool can convert CFG to PDA?
(A) Deterministic finite automaton
(B) Non-deterministic finite automaton
(C) Turing machine
(D) Pushdown automaton

27. Which of the following is not a context-free language?
(A) {aⁿbⁿ | n ≥ 0}
(B) {aⁿbᵐ | n ≥ 0}
(C) {aᵐbⁿ | m, n ≥ 0}
(D) {aⁿbⁿcⁿ | n ≥ 0}

28. What is the start symbol in CFG used for?
(A) To mark the end of string
(B) To identify terminal symbols
(C) To denote stack top
(D) To begin derivation of strings in the language

29. How can CFGs be used in compilers?
(A) Optimizing CPU registers
(B) Generating machine code
(C) Parsing programming languages
(D) Managing memory allocation

30. What is the main limitation of regular languages compared to CFLs?
(A) Cannot handle nested or recursive structures
(B) Cannot handle finite languages
(C) Cannot be recognized by DFA
(D) Cannot be used in programming

Leave a Comment Cancel reply