Formal languages and the theory of computation

Formal languages as partitions on sets of strings

Formal languages and the theory of computation

	Formal languages as partitions on sets of strings
	Ascending the Chomsky hierarchy we consider in turn several increasingly more subtle notions of structure: regular languages, context-free, context-sensitive, Turing complete

Formal languages and the theory of computation

	Formal languages as partitions on sets of strings
	Ascending the Chomsky hierarchy
	Establishing the coherence of the hierarchy witnessing languages demonstrate that each level is properly contained in the next

Formal languages and the theory of computation

	Formal languages as partitions on sets of strings
	Ascending the Chomsky hierarchy
	Establishing the coherence of the hierarchy
	Establishing the validity of semantic distinctions (constructive) equivalence proofs demonstrate that each level is "meaningful"

Formal languages and the theory of computation

	Formal languages as partitions on sets of strings
	Ascending the Chomsky hierarchy
	Establishing the coherence of the hierarchy
	Establishing the validity of semantic distinctions
	A universal notion of computation Equivalence of various "computationally complete" formalisms

Formal languages and the theory of computation

	Formal languages as partitions on sets of strings
	Ascending the Chomsky hierarchy
	Establishing the coherence of the hierarchy
	Establishing the validity of semantic distinctions
	A universal notion of computation
	The limits of computation simple arguments about cardinality imply that language cannot capture the mathematical reality of computation

Formal languages and the theory of computation

	Formal languages as partitions on sets of strings
	Ascending the Chomsky hierarchy
	Establishing the coherence of the hierarchy
	Establishing the validity of semantic distinctions
	A universal notion of computation
	The limits of computation
	Kolmogorov complexity and information content