LangStudies/App/RegM/Lectures/Lecture.3.Notes.md

# Finite Automata
***(AKA: Finite State Machine)***

Mechanism and abstraction used behind regular grammars.

Usually has its state represented using nodes and edges.

Regular grammar:
```
S -> bA
A -> epsilon
```
Equivalent to: `\b\`

State transition:

--label--> : Transition symbol 
O          : State Symbol
(o)        : Accepting State
->O.Start  : Starting State (State transition to Start)

Ex:

->O.*Start* --*transition*--> (o).*Accepting*

*ε* - Epsilon (Empty String)
`I will be spelling it out as I do not enjoy single glyth representation`

Two main types of Finite Automtata :

FA w/ output
* Moore machine
* Mealy machine

FA w/o output
* DFA - Deterministic
* NFA - Non-deterministic
* epsilon-NFA - (Epsilon Transition) special case

NFA : Non-deterministic FA - Allos transition on the same symbol to
different states

```
    a->o
   /
->o.1---b-->o
   \
    a->o 
```

epsilon-NFA : Extension of NFA that allows *epsilon* transitions

```
    a--->o---epsi--->(o)
   /                /
->o----b-->epsi--->o
   \
    a-->o--epsi-->(o)
```

DFA : A state machine which forbids multiple transitions on the same symbol, and *epsilon* transitions

```
    a--->o
   /
->o----b-->o
```

Use case:

Implementation Transformations:
```RegExp -> epsilon-NFA -> ... -> DFA```

## Formal Definition:

Non-deterministic finite automata is a tuple of five elements:
* All possible states
* Alphabet
* Transition Function
* Starting State
* Set of accepting states

NFA = ( States, Alphabet, TransitionFunction, StartingState, AcceptingStates )

NFA = ( Q, Σ, Δ, q0, F )