What does Automata Theory mean?
• An Open ended computer science
discipline that concerns an abstract
device called “automaton”, which
performs a specific computational or
recognition function.
• Networks of automata are designed
to mimic human behaviour
, What we will do
Automata = abstract computing devices
Turing studied Turing Machines (= computers)
before there were any real computers
We will also look at simpler devices than
Turing machines (Finite State Automata,
Pushdown Automata, . . . ), and specification
means, such as grammars and regular
expressions.
NP-hardness = what cannot be efficiently
computed
• An Open ended computer science
discipline that concerns an abstract
device called “automaton”, which
performs a specific computational or
recognition function.
• Networks of automata are designed
to mimic human behaviour
, What we will do
Automata = abstract computing devices
Turing studied Turing Machines (= computers)
before there were any real computers
We will also look at simpler devices than
Turing machines (Finite State Automata,
Pushdown Automata, . . . ), and specification
means, such as grammars and regular
expressions.
NP-hardness = what cannot be efficiently
computed
