Linear Bounded Automata
Explore context-sensitive languages with space-bounded Turing machines
Linear Bounded Automata Simulator
Simulate linear bounded automata for context-sensitive languages
Linear Bounded Automata Simulator 🔒
Explore context-sensitive languages with space-bounded Turing machines
LBA Configuration
Bounded Tape
LBA can only use space between endmarkers ⊢ and ⊣ (linear in input size)
Transition Function
Context-Sensitive Properties
Language: Recognizes {aⁿbⁿcⁿ | n ≥ 1} - equal numbers of a's, b's, and c's
Complexity: O(n) space, O(n²) time
Space Bound: Uses only O(n) tape cells (linear in input size)
Context-Sensitive: More powerful than context-free languages
Endmarkers: Cannot move beyond ⊢ (left) and ⊣ (right) boundaries
Decidable: All context-sensitive languages are decidable
Position in Computational Hierarchy
Regular
DFA/NFA
Context-Free
PDA
Context-Sensitive
LBA
Recursively Enum.
Turing Machine
LBAs recognize exactly the context-sensitive languages - more powerful than PDAs but less than unrestricted Turing machines
Context-Sensitive Language Examples
aⁿbⁿcⁿ
Equal numbers of three different symbols
Classic CSL example
w#w
String duplication with separator
Copy language
Type Checking
Variable declaration and usage
Programming languages
Palindromes
Strings that read same forwards/backwards
Linear space solution
Natural Language
Some aspects of human language syntax
Computational linguistics
Indexed Languages
Languages with stack + finite control
Between CFL and CSL