Context-sensitive grammars and languages MCQs

By: Prof. Dr. Fazal Rehman | Last updated: September 23, 2024

Context-Sensitive Grammars and Languages MCQs Which of the following defines a context-sensitive grammar (CSG)? A) A grammar where every production is of the form A → α, where A is a non-terminal and α is a string of terminals and non-terminals. B) A grammar where every production is of the form A → α, where |α| ≤ |A| and A is a non-terminal. C) A grammar where every production is of the form α → β, where α and β are strings of terminals and non-terminals and |α| ≤ |β|. D) A grammar where every production is of the form αAβ → αγβ, where α, β, γ are strings of terminals and non-terminals. Answer: C A context-sensitive language (CSL) is: A) Any language that can be recognized by a finite automaton. B) Any language that can be generated by a context-free grammar. C) Any language that can be generated by a context-sensitive grammar. D) Any language that can be recognized by a pushdown automaton. Answer: C Which of the following grammars is more powerful than a context-sensitive grammar? A) Regular grammar B) Context-free grammar C) Unrestricted grammar D) Deterministic grammar Answer: C A context-sensitive grammar allows productions of the form: A) A → αB B) A → α C) αAβ → αγβ D) A → ε Answer: C Context-sensitive languages are closed under which of the following operations? A) Union B) Intersection C) Concatenation D) Complementation Answer: C Which of the following is true about context-sensitive languages compared to context-free languages? A) Context-sensitive languages can be recognized by pushdown automata. B) Context-free languages are a proper subset of context-sensitive languages. C) Context-sensitive languages are always regular. D) Context-free languages are more expressive than context-sensitive languages. Answer: B The Chomsky hierarchy places context-sensitive grammars and languages: A) Above regular grammars and below context-free grammars. B) Above context-free grammars and below unrestricted grammars. C) Above deterministic context-free grammars and below Turing machines. D) Below regular grammars and above context-free grammars. Answer: B A context-sensitive grammar can generate languages that include: A) {a^n b^n c^n | n ≥ 0} B) {a^n b^n | n ≥ 0} C) {ww^R | w ∈ {a, b}*} D) {a^i b^j c^k | i = j or j = k} Answer: D Which of the following is an example of a context-sensitive language? A) {a^n b^n | n ≥ 0} B) {a^n b^n c^n | n ≥ 0} C) {ww^R | w ∈ {a, b}*} D) {a^i b^j c^k | i ≠ j ≠ k} Answer: B Context-sensitive languages are recognized by which type of automaton? A) Finite automaton B) Pushdown automaton C) Turing machine D) Deterministic finite automaton Answer: C  
All Copyrights Reserved 2025 Reserved by T4Tutorials