# Context-Sensitive Language Theorem: All **Context-Sensitive Languages** are accpetable by **Linear Bounded Automata**. Theorem: The language class accepted by **Linear Bounded Automata** can be generated by **Context-Sensitive Grammar**. ## Context-Sensitive Grammars A **Context-Sensitive Grammar** is an unrestricted grammar in which every product has the form: $\alpha \rightarrow \beta$, with $|\beta| \geq |\alpha|$, $\alpha$ contains at least one variable. 這邊的定義是一種弱版本，也就說 Context-Sensitive Grammar 是 Unrestricted Grammar 的變體，前提就是變換過後的長度會大於原本的長度。 ### Another Definition of CSG Definition: a context-sensitive grammar is a quadruple: $$ G = (V, \Sigma, R, S) $$ * $V$ is an alphabet. (Variables + Terminals) * $\Sigma$ is a subset of $V$, the set of terminals * $R$ is the set of grammar rules: $V^\star (V-\Sigma) V^\star \rightarrow V^\star(V)^+V^\star$ * $S$ is a start **variable**. $A$ 是變數，$\alpha$ 和 $\beta$ 是字串，有限制上下文才能轉換。 $\alpha A \beta \rightarrow \alpha \gamma \beta$, $A \in (V - \Sigma), \alpha, \beta \in V^\star, \gamma \in V^+$ Context-Sensitive Grammar 是比 Context-Free Grammar 強大，Context-Free Grammar 會是 Context-Sensitive Grammar 的一種！ ### Context Sensitive Languages * Definition: A context-sensitive language is generated by a **Context-Sensitive Grammar**. * Context-Sensitive Grammar form a proper subset of the recursive language class. * The recursive language class is a proper subset of the recursively enumerable language class. # Linear Bounded Automata * Definition: A **Linear Bounded Automata** (LBA) is a Turing machine with linear-bounded memory size. * Working memory size = $O(|w|)$, where $w$ is the input string. > The size of the working memory is at most $k|w|$, $k$ is a constant. ### LBA and Non-determinstic * LBA is a **non-deterministic** Turing machine with limited memory space. * There is another **deterministic** version of LBA, called deterministic LBA (DLBA). LBA problem: Is DLBA < LBA? (Unsolved yet since 1964) ### History Deterministic LBA by Myhill in 1960 Non-deterministic LBA by Kuroda in 1964 Context-Sensitive Grammar by Chomsky in 1950s Chomsky hierarchy by Chomsky in 1956. ###### tags: `計算理論`