### Bassics

**Symbol**: a, b, c, d, …

**Alphabet**: collection of symbols {a, b} ; {c, d, a}

**String**: Sequence of symbols {aa, bb, cc, ac, da}

**Language**: Set of strings eg - L1 = set of all strings of length 2 {00, 11, 01, 10}

**Finite Automata**:

- It’s simplest model of computation
- It as very limited memory

There are two types:

- With Output
- Moore Machine
- Mealy Machine

- Without Output
- DFA (Deterministic Finite Automata)
- NFA (Non-Deterministic Finite Automata)

## DFA:

```
Given the current state we will know what the next state will be
It as unique next state
It as no choices and randomness
It is simple and easy
```

It’s defined by five tuples {Q, sigma, q0, F, del}

Q - Set of all States

Sigma - Inputs

q0 - Start state / Initial state

F - Set of final states

delta - Transition function \

## Regular Expression

If finite state machine recognises the language then it’s regular expression the language doesn’t require memory

#### Operations

- Union
- Concatenation
- Star

## NDFA

```
Given the current state there are multiple next states
The next state is chosen at random or choose all next state in parallel
```

Its is also defined by the same five states as DFA

## Minimisation of DFA

Equivalence states

## Mealy Machine

It as six tuples {Q, sigma, delta, del, lamda, q0}

Q - Finite set of all states

Sigma - Finite non-empty set of input alphabets

Delta - Set of Output Alphabets

Del - Transition Function

Lamda - Output function

q0 - Initial state

## Moore Machine

Same of Mealy Machine with slight difference in output function