Automata Theory

tags : Computation and Computer Theory, The Analytical Engine, Regular Expressions

![](/ox-hugo/20230421132238-automata_theory-1356726852.png)

What is Automata Theory §

Logic of computation with respect to simple machines(automata)

Automatons §

• plural: automata
• Abstract models of machines that perform computations on an input by moving through a series of states
• At each state, transition function determines next state based on present state
• Once entire input have been read and is in an acceptable state, machine accepts input

Incomplete list of types of Automatons §

See Chomsky Hierarchy

The most general and powerful automata is the Turing machine

• Finite state machine(FSM)
• Pushdown automata(PDA)
• Linear bounded automata(LBA)
• Turing machine

More on Automatons Types §

Finite state machine(FSM/FSA/FA/SM) §

• See Finite Automata

Pushdown automata(PDA) §

• See Pushdown Automata (PDA)

Linear bounded automata(LBA) §

Turing machine §

• Purpose: Prove that certain specific languages have no algorithm.
  • Compared to regular programming languages like C++, it’s easier to prove it with a TM because it’s so simple
  • TM are as powerful as any computer and have infinite memory
  • So if there’s something a TM cannot solve, it probably cannot be solved.
• A Turing machine is a FSM but the inverse is not true.

Type of Problems §

See Complexity Theory