MCQs on Context free Grammar and Context Sensitive Languages

19
Score: 0
Attempted: 0/19
Subscribe

1. The entity which generates Language is termed as:
(A) Automata
(B) Tokens
(C) Strings
(D) Grammar

2. The minimum number of productions required to produce a language consisting of palindrome strings over ∑={a,b} is:
(A) 5
(B) 7
(C) 3
(D) 8

3. Which of the following statement is correct?
(A) All context free grammar are regular grammar but not vice versa
(B) All Regular grammar are context free but not vice versa
(C) Regular grammar and context free grammar are the same entity
(D) None of the mentioned

4. Context sensitive grammar (CSL) is also called?
(A) Length increasing grammar
(B) Non contracting Grammar
(C) Type 1 Grammar
(D) All of these

5. Which of the following is Type 3 language or Type 3 grammar?
(A) Regular grammar/ Regular language
(B) Context Free Grammar / Context Free language
(C) Context Sensitive Grammar / Context Sensitive language
(D) Recursively Enumerable

6. Which of the following is Type 2 language or Type 2 grammar?
(A) Regular grammar/ Regular language
(B) Context Free Grammar / Context Free language
(C) Context Sensitive Grammar / Context Sensitive language
(D) Recursively Enumerable

7. Which of the following is Type 1 language or Type 1 grammar?
(A) Regular grammar/ Regular language
(B) Context Free Grammar / Context Free language
(C) Context Sensitive Grammar / Context Sensitive language
(D) Recursively Enumerable

8. Which of the following is Type 0 language?
(A) Regular grammar/ Regular language
(B) Context Free Grammar / Context Free language
(C) Context Sensitive Grammar / Context Sensitive language
(D) Recursively Enumerable

9. Which of the following Machine is specific for Regular grammar?
(A) Finite state automata
(B) Push down automata
(C) Linear bounded automata
(D) Turing Machine with deterministic logic, unbounded infinite length of tape.

10. Which of the following Machine is specific for Context free grammar?
(A) Finite state automata
(B) Push down automata
(C) Linear bounded automata
(D) Turing Machine

11. Which of the following Machine is specific for Context sensitive grammar?
(A) Finite state automata
(B) Push down automata
(C) Linear bounded automata
(D) Turing Machine

12. Which of the following Machine is specific for Recursively enumerable languages?
(A) Finite state automata
(B) Push down automata
(C) Linear bounded automata
(D) Turing Machine

13. A context free language is called ambiguous if there exists a string that can have:
(A) only one parse tree
(B) more than one parse tree
(C) no parse tree
(D) Partial parse tree

14. The context free grammar X → XX | aXb | bXa | ɛ generates:
(A) Number of a’s followed by any number of b’s
(B) Unequal number of a’s and b’s
(C) Equal number of a’s and b’s
(D) None of these

15. Production Rule: aYb->agb belongs to which of the following languages?
(A) Recursively Enumerable Language
(B) Context free Language
(C) Context Sensitive Language
(D) Regular Language

16. Which of the following language cannot be accepted by a regular expression?
(A) Language of a set of numbers divisible by 4
(B) Language of a set of binary complement
(C) Language of a set of 0n1n
(D) Language of a set of string with odd number of 0

17. The minimum number of productions required to produce a language consisting of palindromes as a strings defined over ∑={0,1} is:
(A) 4
(B) 5
(C) 6
(D) 7

18. Which of the following statement is true about regular grammar?
(A) Regular grammar and context free
(B) All context free grammar are regular grammar but not vice versa
(C) All Regular grammar are context free but not vice versa grammar are the same entity
(D) All of these

19. Are ambiguous grammar context free?
(A) Yes
(B) No
Answer: (A) Yes

Theory of Automata MCQs
Finite Automata MCQs
Regular Languages
Context-Free Grammars (CFG)
Pushdown Automata (PDA) MCQs
- Deterministic PDA vs Non-deterministic PDA MCQs
- Relationship between PDA and context-free languages MCQs
Context-Free Languages MCQs
Turing Machines MCQs
- Turing machine as a language recognizer and transducer MCQs
Decidability and Undecidability MCQs
Computational Complexity MCQs
Advanced Topics in Automata Theory
Applications of Automata Theory MCQs

Context-sensitive grammars and languages MCQs
Relationship between PDA and context-free languages MCQs
CFG for strings with unequal numbers of a and b - Context-free grammar.
Properties of context-free languages MCQs
Pumping Lemma for context-free languages MCQs
Context Free Grammar CFG in theory of automata

MCQs on Context free Grammar and Context Sensitive Languages
By: Prof. Dr. Fazal Rehman | Last updated: April 15, 2025

Related Posts:

Leave a Comment