14. Chomsky Hierarchy

Feb 22, 2022

Linear-Bounded Automata

• the input string tape space is the only allowed tape space allowed
• cannot go left/right beyond input
• all computation is done between end markers

=> this restriction limits the number of problems that can be solved

• LBAs have more power than PDAs
• LBAs have less power than TMs

Example languages accepted by LBAs

$L=\{a^n{b}^n{c}^n\}$     $L=\{a^{n!}\}$

(Presumably) open problem:

do nondeterministic LBAs have same power as deterministic LBAs?

Variations of Grammars

Unrestricted Grammars

Production rules are sensitive to the context of the variables, e.g. $u\to v$ on both left and right: string of variables and terminals.

Unrestricted Grammars have same power as Turing Machines.

Examples:

$S\to aBc$     $aB\to cA$     $Ac\to d$

Theorem. A language $L$ os Turing-acceptable iff $L$ is generated by an unrestricted grammar.

Context-sensitive Grammars

Subcase of unrestricted grammars — restricted form where $|u|\le |v|$.

Example: the language $\{a^n{b}^n{c}^n\}$ is context-sensitive:

$S\to abc|aAbc$
$Ab\to bA$
$Ac\to Bbcc$
$bB\to Bb$
$Ab\to aa|aaA$

Note: the length of left side is upper bounded by length of right side.

Theorem. A language $L$ is context-sensitive iff it is accepted by a linear-bounded automaton.

Observation: There is a language which is decidable but not context-sensitive.

Chomsky Hierarchy

       ╭————————————————————————————————————————╮
       │  Unrestricted/recursively enumerable     │
       │   ╭———————————————————————————————╮      │
       │   │      Context—sensitive         │    │
       │   │  ╭—————————————————————————╮  │    │
       │   │  │      Context—free       │  │    │
       │   │  │  ╭———————————————————╮    │  │    │
       │   │  │  │     Regular       │    │  │    │
       │   │  │  ╰———————————————————╯    │  │    │
       │   │  ╰—————————————————————————╯  │    │
       │   ╰———————————————————————————————╯    │
       ╰————————————————————————————————————————╯