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

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)

### 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.