COMP2022 Formal languages and logic Course Notes (High Distinction)

Description

These COMP2022 notes include my raw personal lecture and laboratory notes. I received a final mark of 94 (High Distinction). Contents ------------ Course information +-- Tutorials +-- Assessments +-- Exam Tutorials +-- Tutorial 01 +-- +-- Problem 1 +-- +-- Problem 2 +-- Tutorial 03 +-- +-- Fixed point combinators +-- +-- Church-Rosser +-- Tutorial 06 +-- Tutorial 07 +-- Tutorial 08 Lecture 01 +-- Background +-- Notation +-- Functional programming +-- Lambda calculus Lecture 02 +-- Terminology +-- Evaluation order +-- Currying +-- +-- Curried evaluation +-- Encodings +-- +-- Booleans +-- +-- Numbers +-- +-- Recursion Lecture 03 +-- Introduction +-- +-- eta-reduction +-- +-- Logical Notation +-- Y combinator +-- +-- Fixed point theorem +-- +-- Fixed point combinator +-- Encodings +-- +-- Pairs +-- +-- Lists +-- +-- Numbers (a different way) +-- Functional programming Lecture 04 +-- Lambda Calculus +-- +-- Computational power +-- Automata Theory +-- +-- Background +-- +-- DFA, Deterministic Finite Automata +-- +-- Regular languages +-- +-- NFA, Non-deterministic Finite Automata Lecture 05 +-- NFA +-- DFA and DFA equivalence +-- +-- Epsilon closure +-- +-- Converting a NFA to DFA +-- Minimal DFA +-- Regular languages and Closure properties +-- +-- Regular languages +-- +-- Closure properties +-- Regular expressions Lecture 06 +-- Regular expressions (RE) +-- Equivalence of FA and RE +-- +-- Generalised NFA (GNFA) +-- +-- Converting NFA to RE +-- Proving non-regularity +-- +-- Pumping a language +-- +-- Pumping lemma +-- +-- Proving a language is not regular Lecture 07 +-- Grammars +-- +-- Context-free grammars (CFG) +-- +-- Constructing grammars +-- +-- Parsing grammars +-- +-- Clean grammars +-- +-- Types of grammar Lecture 08 +-- Push down automata (PDA) +-- Parsing +-- +-- Table-descent (table-driven) parser +-- +-- First and follow sets +-- +-- LL(1) grammars +-- +-- Transforming non-LL(1) grammars +-- +-- Proving a language is not LL(1) Lecture 09 +-- Turing machines (TM) +-- +-- Language +-- +-- Cool stuff +-- +-- Computability +-- Logic Lecture 10 +-- Tautologies, contradictions +-- Equivalence laws +-- +-- Laws of equivalence +-- +-- Transformational proofs +-- Inference rules +-- +-- Rules of inference +-- Formal proofs using the Natural Deduction System Lecture 11 +-- Inference rules: CP and IP +-- Invalidity +-- Tautologies +-- Predicate logic +-- +-- Quantifier scope +-- +-- Interpretations Lecture 12 +-- Semantics +-- Validity and satisfiability +-- Laws of equivalence +-- Inference rules +-- +-- Free to replace +-- +-- Rules Lecture 13 +-- Computability +-- Church-Turing thesis +-- Exam