Skip to content

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^nb^nc^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 \rightarrow v\) on both left and right: string of variables and terminals.

Unrestricted Grammars have same power as Turing Machines.

Examples:

\(S \rightarrow aBc\)     \(aB \rightarrow cA\)     \(Ac \rightarrow 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| \leq |v|\).

Example: the language \(\{a^nb^nc^n\}\) is context-sensitive:

\(S \rightarrow abc \enspace | \enspace aAbc\)
\(Ab \rightarrow bA\)
\(Ac \rightarrow Bbcc\)
\(bB \rightarrow Bb\)
\(Ab \rightarrow aa \enspace | \enspace 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       │    │  │    │
       │   │  │  ╰———————————————————╯    │  │    │
       │   │  ╰—————————————————————————╯  │    │
       │   ╰———————————————————————————————╯    │
       ╰————————————————————————————————————————╯