Please enable JavaScript.

Coggle requires JavaScript to display documents.

MoC Mind Map - Coggle Diagram

- - - - Prove by F^!G ≡ Contradiction
    - - F entails G and G entials F
  - - - Existential (OR)∃
      - Universal (AND)∀
    - - Skolemisation (Pre-processing)
      - Unification (Terms Mapping)
        
        Substitutions: Can only map variables to variables/functions/constants
        
        Most General Unifier
      - Factoring (Duplicated Predicate Reduction)
- - - - A set of substition rules
      - Elements
        
        V: Variable (A, S, E, etc)
        
        Sigma: terminals (alphabets for sentences)
        
        S: start variable
        
        R: rules
      - Definitions
        
        Sentential forms (a string with variables and terminals)
        
        Sentence (a string without variables)
      - Draw the parse tree
      - Ambiguity
    - - Q: a finite set of states
      - Sigma: finite input alphabet
      - Gamma: finite stack alphabet
      - Delta: power set of Q X Gamma with epsilon
      - q0: start state
      - F: accept states
    - - eps eps -> $
      - eps eps -> S (start variable)
      - Self loop terminals (a a -> eps, x x -> eps)
      - Self loop sentential forms inversly (eps,eps ->terminal/Variable)
        
        First transition: eps, variable -> terminal/variable
        
        Second to N transitions: eps eps -> termninal/variable
      - Extend if sentential forms contain different variables
  - - - Does not fail to halt
  - - - Total transitions
    - - Epsilon Transition
      - Mupltiple start states
      - Does not require total transitions
      - Clone
      - Construct NFA based on a regular expression
      - Construct a regular expression from an NFA
    - - Q = finite set of states
      - Sigma = finite alphabet
      - Delta = transition rules
        
        DFA: Q X Sigma (needs to be total)
        
        NFA: P(Q X Sigma)
      - F (accept states): subset of Q
      - q0 = start state(s)
        
        NFA: at least one start states
        
        DFA: one single start state
    - - All NFA has at least one equivalent DFA form
      - A language is regular iff at least one finite automaton recognise it
    - - Convert DFAs to an NFA based on regular operations
      - Use subset construction to convert an NFA to an DFA (not minimal)
      - Closure Results
      - Minimizing DFA from NFA
        
        Reverse the NFA
        
        Determinize the result (subset construction)
        
        Reverse again
        
        Determinize
  - - - Regular Language: xyiz
        
        [https://www.youtube.com/watch?v=x2J5kaf6gjg&t=669s&pp=ygUjcHVtcGluZyBsZW1tYSBmb3IgcmVndWxhciBsYW5ndWFnZXM%3D]
      - Context Free Language: uvixyiz
  - - - Concatenation
      - Union
      - Kleene star
- - - - Properties
        
        Symmetric
        
        R(x,y) -> R(y,x) for all x, y
        
        Asymmetric
        
        R(x,y) -> no R(y,x) for all x, y
        
        Anti-symmetric
        
        R(x,y) & R(y,x) -> x = y for all x,y in A
        
        Transitive
        
        R(x,y) & R(y,z) -> R(x,z) for all x,y,z
        
        Unique smallest transitive closure that includes R
        
        Irreflexive
        
        no R(x,x) for all x
        
        Reflexive
        
        R(x,x) for all x
      - Domain: x in R(x,y) where x is an element of A
      - Range: y in R(x,y) where y is an element of B
      - Full relation: total and injective (one-to-one)
      - Relation on A: both domain and range is A
      - Relation between A and B: domain is A and range is B
      - Identity: R(x,x)
      - Inverse: (b,a) from (a,b)
      - Composition: (x,z) elements of R1 o R2 iff R1(x,y) & R2(y,z)
      - Equivalence relation: reflexive, symmetric, transitive
      - Partial orders
        
        Pre-order: transitive and reflexive
        
        Strict partial order: transitive & irreflexive
        
        Partial order: antisymetric, transitive, reflexive (pre-order)
        
        Linear: iff R(x,y) || R(y,x) || x = y for all x,y in A
        
        Total order: linear partial order
      - Surjective: All elements from X is mapped to Y
      - Injective: one-to-one
      - Bijective: injective and surjective
  - - - Proper subset (cannot be equivalent)
    - - Union
      - Intersection
      - Difference
      - Symmetric Difference (XOR)
      - Compliment
    - - Empty set
        
        Empty set is a subset of every set
      - Singleton set
      - Universal set
      - Pair set
        
        Ordered pair (If (x,y), x <= y for all x, y)