Context-sensitive grammars and languages MCQs

By: Prof. Dr. Fazal Rehman Shamil | 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

 

Related Posts: