Week4

Symbols, alphabets and languages

Alphabet (S): set of character

Language: L1(S) = {a,aa,b,ab, ba, ....} (infinite) L2(S) = {aa, bb, ab, ba} (lenght=2) (finite automata)

When we add restriction to language it become grammar (formal grammat)

G = (N,T, P, S) n = non terminal (variable) T = terminals (non variable) P = productions (rule) S = starting symbols (where to start our analysis)

hierarchy of grammar: 0. Unrestricted - [natural languages] 1. Context-sensitive - [Programming languages] 2. Context free - [Programming languages] 3. Regular - [Regular expressions]

BNF (Bakus Naur Form - a notation used in formal grammar to describe language systax) --> RegEx is just a syntactic notation

Regular grammar dont support nesting. It doesnt mean they dont suport recursion.

The canonical implemenrtation for regular grammars is the Finite Automata or the State machines.

Finite Automata (State machine):

FA w/ output: * Moore machine * Mealy machine

FA w/o output: * DFA (deterministic) - forbid multiple transition on the same symbol * NFA (non-deterministic) - allows transition on the same symbol to different states * e-NFA - NFA + transistion to e-transition

RegEx -> e-NFA -> ... -> DFA