X hits on this document

128 views

0 shares

0 downloads

0 comments

6 / 40

Motivations

??

Non-computable

3

Finite state automata

Regular expressions

Regular

2

Non-deterministic pushdown automata

Context-free grammar

Context-free

1

Linear-bounded automata

Context-sensitive grammar

Context-sensitive

Turing machines that always halt

Recursive

0

Turing machines

Unrestricted

Recursively enumerable (RE)

Chomsky Hierarchy

Machine

Grammar

Language

properly inclusive

Document info
Document views128
Page views128
Page last viewedFri Jan 20 10:34:38 UTC 2017
Pages40
Paragraphs326
Words1871

Comments