- Theory of Automata MCQs
- Finite Automata MCQs
- Regular Languages
- Context-Free Grammars (CFG)
- Pushdown Automata (PDA) MCQs
- Context-Free Languages MCQs
- Turing Machines MCQs
- Decidability and Undecidability MCQs
- Computational Complexity MCQs
- Advanced Topics in Automata Theory
- Applications of Automata Theory MCQs
Context-sensitive grammars and languages MCQs
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