COS3701 Summary.

TERMS: i. FSM: Finite State Machine (Lowest level machine, basic computations) ii. CFL: Context Free Language (Capable of a little higher level computations) iii. TM: Turing Machine (High Level Computations) iv. Undecidable: Problems that cannot be solved by any machine v. Symbol examples: a, b, c, 0, 1, 2, 3.... vi. Alphabet: denoted by 'sigma': collection of symbols eg. {a,b} or {d, e, f, g} or {0, 1, 2} vii. String: sequence of symbols eg.a,b,0, aa, bb, ab, 01 viii. Language: Set of Strings EXAMPLES: given alphabet: sigma = {0,1} L1 = set of all strings of length 2 {00, 01, 10, 11} (finite set) L2 = set of all strings of length 3 {000, 001, 010, 011, 100, 101, 110, 111} (finite set) L3 = set of all strings that begin with 0 {0, 00, 01, 000, 001, 010, 011, 0000...} (infitine set) 1. POWERS OF SIGMA: EXAMPLE: Σ = {0,1} Σ^0: Set of all strings of length 0 : Σ^0 = {ϵ}(ϵ = empty string) Σ^1: Set of all strings of length 1 : Σ^1 = {0,1} Σ^2: Set of all strings of length 2 : Σ^2 = {00,01,10,11} Σ^3: Set of all strings of length 3 : Σ^3 = {000, 001, 010, 011, 100, 101, 110, 111} Σ^n: Set of all strings of length n 2. CARDINALITY: Number of elements in a set EXAMPLE: Σ = {0,1} Σ^0: Set of all strings of length 0 : Σ^0 = {ϵ}, cardinality = 1 Σ^1: Set of all strings of length 1 : Σ^1 = {0,1} cardinality = 2 Σ^2: Set of all strings of length 2 : Σ^2 = {00,01,10,11} cardinality = 3 Σ^n: Set of all strings of length n cardinality = 2^n 3. Σ* Σ* = Σ^0 union Σ^1 union Σ^2 union Σ^3 union ... = {ϵ} union {0,1} union {00,01,10,11} union {000, 001, 010, 011, 100, 101, 110, 111} union ... = set of all possible strings of all lengths over alphabet {0,1} = (infinite set) 4. FSM (aka Finite Automata):