Q.1 Which of the following is true about context-sensitive grammars?
They can generate all recursively enumerable languages
They generate only context-free languages
They generate languages where the length of the output string never decreases
They can only generate finite languages
Explanation - Context-sensitive grammars are defined such that productions are of the form αAβ → αγβ, ensuring that |αγβ| ≥ |αAβ|, i.e., the string length never decreases.
Correct answer is: They generate languages where the length of the output string never decreases
Q.2 A Linear Bounded Automaton (LBA) differs from a Turing Machine in that:
It cannot move its head left
It has a tape of fixed length proportional to input size
It cannot use a stack
It can only recognize regular languages
Explanation - An LBA is a non-deterministic Turing Machine whose tape is restricted to be linearly proportional to the input size, unlike a general Turing Machine which has an infinite tape.
Correct answer is: It has a tape of fixed length proportional to input size
Q.3 Which of the following languages is context-sensitive?
{a^n b^n | n ≥ 0}
{a^n b^n c^n | n ≥ 0}
{a^n b^m | n, m ≥ 0}
All regular languages only
Explanation - The language {a^n b^n c^n} is context-sensitive because a context-free grammar cannot generate it, but a context-sensitive grammar can.
Correct answer is: {a^n b^n c^n | n ≥ 0}
Q.4 Which property is true for context-sensitive languages?
They are closed under union
They are closed under complementation
They are closed under intersection
All of the above
Explanation - Context-sensitive languages are closed under union, intersection, concatenation, and complementation.
Correct answer is: All of the above
Q.5 The acceptance condition for a Linear Bounded Automaton is:
Halting in an accepting state
Empty tape
Reaching a specific symbol
Accepting any input by default
Explanation - An LBA accepts an input if it halts in an accepting state, similar to other automata, but with its tape restricted in size.
Correct answer is: Halting in an accepting state
Q.6 Which of the following is true about the relation between context-sensitive languages (CSL) and linear bounded automata (LBA)?
Every CSL can be recognized by an LBA
Every LBA language is context-free
CSL is a subset of regular languages
LBAs can only recognize regular languages
Explanation - By definition, a Linear Bounded Automaton recognizes exactly the set of context-sensitive languages.
Correct answer is: Every CSL can be recognized by an LBA
Q.7 Which of the following is NOT true about context-sensitive grammars?
They can generate non-context-free languages
Their rules may have a left-hand side longer than right-hand side
They require length of string to never decrease in productions
They are more powerful than context-free grammars
Explanation - In context-sensitive grammars, the length of the left-hand side is always ≤ the length of the right-hand side to ensure non-decreasing string length.
Correct answer is: Their rules may have a left-hand side longer than right-hand side
Q.8 Which of these languages can a context-sensitive grammar generate but not a context-free grammar?
{a^n b^n | n ≥ 0}
{a^n b^n c^n | n ≥ 0}
{a+b+ | all strings with at least one a and one b}
All regular languages
Explanation - The language {a^n b^n c^n} requires counting three types of symbols simultaneously, which a context-free grammar cannot handle but a context-sensitive grammar can.
Correct answer is: {a^n b^n c^n | n ≥ 0}
Q.9 Which of the following operations preserves the context-sensitive property of languages?
Union
Concatenation
Kleene star
None of the above
Explanation - Context-sensitive languages are closed under union, concatenation, and intersection, but not all unrestricted operations like arbitrary Kleene star in some cases.
Correct answer is: Union
Q.10 A Linear Bounded Automaton is a:
Non-deterministic Turing Machine with restricted tape
Finite automaton with a stack
Pushdown automaton with two stacks
Regular expression machine
Explanation - An LBA is essentially a non-deterministic Turing Machine whose tape length is bounded by a linear function of the input size.
Correct answer is: Non-deterministic Turing Machine with restricted tape
Q.11 Which of these is true for languages recognized by LBAs?
All are context-free
All are context-sensitive
All are regular
All are recursively enumerable but not necessarily context-sensitive
Explanation - The class of languages recognized by LBAs is exactly the set of context-sensitive languages.
Correct answer is: All are context-sensitive
Q.12 Which statement about context-sensitive languages is false?
They are more general than context-free languages
They are closed under complementation
They are closed under homomorphism
They can be recognized by LBAs
Explanation - Context-sensitive languages are generally not closed under arbitrary homomorphisms.
Correct answer is: They are closed under homomorphism
Q.13 Which of the following is a restriction of Linear Bounded Automata compared to general Turing Machines?
Tape length proportional to input size
Can only move right
Cannot use a finite control
Cannot halt
Explanation - An LBA cannot exceed tape proportional to input length, unlike a Turing Machine which has infinite tape.
Correct answer is: Tape length proportional to input size
Q.14 Which language is an example of a context-sensitive language that is not context-free?
{a^n b^m | n, m ≥ 0}
{a^n b^n | n ≥ 0}
{a^n b^n c^n | n ≥ 0}
{a, b}*
Explanation - The language {a^n b^n c^n} requires counting three sets simultaneously, which cannot be done by a context-free grammar.
Correct answer is: {a^n b^n c^n | n ≥ 0}
Q.15 Which of the following statements is true about context-sensitive grammars?
They have productions of the form α → β where |β| ≥ |α|
They are equivalent to regular expressions
They can only generate finite languages
They have no restrictions on production lengths
Explanation - The rule ensures that strings do not shrink in length, a key property of context-sensitive grammars.
Correct answer is: They have productions of the form α → β where |β| ≥ |α|
Q.16 Which of the following languages cannot be recognized by a Linear Bounded Automaton?
{a^n b^n | n ≥ 0}
{a^n b^n c^n | n ≥ 0}
{a^n b^n c^n d^n | n ≥ 0}
{a^n | n ≥ 0}
Explanation - Languages requiring counting more than three sets of symbols exceed the power of LBAs, as they are context-sensitive but require more space.
Correct answer is: {a^n b^n c^n d^n | n ≥ 0}
Q.17 Which of the following is true regarding the closure properties of context-sensitive languages?
Closed under union and intersection only
Closed under union, intersection, concatenation, and complementation
Closed under union but not intersection
Closed under concatenation only
Explanation - CSLs are closed under all these operations due to their correspondence with LBAs.
Correct answer is: Closed under union, intersection, concatenation, and complementation
Q.18 Which automaton recognizes exactly the context-sensitive languages?
Pushdown Automaton
Finite Automaton
Linear Bounded Automaton
Turing Machine with infinite tape
Explanation - By definition, LBAs recognize exactly the set of context-sensitive languages.
Correct answer is: Linear Bounded Automaton
Q.19 Which of the following is a correct form of context-sensitive grammar production?
A → a
AB → ACB
A → ε
a → b
Explanation - CSG productions allow context on both sides and must not decrease string length; AB → ACB is valid as |ACB| ≥ |AB|.
Correct answer is: AB → ACB
Q.20 Which of the following statements is true for Linear Bounded Automata?
They can have infinite tape
They always halt for any input
They are equivalent in power to context-sensitive grammars
They are less powerful than pushdown automata
Explanation - An LBA and a context-sensitive grammar define exactly the same set of languages.
Correct answer is: They are equivalent in power to context-sensitive grammars
Q.21 Which of the following is an example of a context-sensitive language?
{a^n b^n | n ≥ 0}
{a^n b^n c^n | n ≥ 0}
{a+b+}
{a, b}*
Explanation - CSLs can generate {a^n b^n c^n} but context-free grammars cannot.
Correct answer is: {a^n b^n c^n | n ≥ 0}
Q.22 Which of the following is true for a context-sensitive language?
It may shrink in length with production rules
It is recognized by an LBA
It can only have one terminal symbol
It is always finite
Explanation - CSLs correspond exactly to the languages recognized by Linear Bounded Automata.
Correct answer is: It is recognized by an LBA
Q.23 Which of the following languages is context-sensitive but not context-free?
{a^n b^n | n ≥ 0}
{a^n b^n c^n | n ≥ 0}
{a+b+}
{ab}*
Explanation - Context-free grammars cannot generate {a^n b^n c^n} because they cannot enforce equal numbers of three symbols, but context-sensitive grammars can.
Correct answer is: {a^n b^n c^n | n ≥ 0}
Q.24 Which is a limitation of Linear Bounded Automata compared to general Turing Machines?
Cannot move left
Tape size limited to linear function of input
Cannot read input symbols
Cannot have multiple states
Explanation - An LBA has a tape bounded by a linear function of input length, unlike a Turing Machine with infinite tape.
Correct answer is: Tape size limited to linear function of input
Q.25 Context-sensitive languages are:
More general than context-free languages
Equivalent to regular languages
Less general than context-free languages
Only finite languages
Explanation - CSLs include all context-free languages and some languages not context-free, making them more general.
Correct answer is: More general than context-free languages
Q.26 Which of the following operations is context-sensitive languages NOT closed under?
Union
Concatenation
Arbitrary homomorphism
Intersection
Explanation - Context-sensitive languages are generally not closed under arbitrary homomorphisms, though they are closed under union, concatenation, and intersection.
Correct answer is: Arbitrary homomorphism