Please enable JavaScript.

Coggle requires JavaScript to display documents.

cs 390 - Coggle Diagram

- - - - propeties of integers: set Z is closed under addition,multiiplication, and subtraction
        
        example of proving a set is not closed under an operation: natural numbers are not closed under subtraction, as they can result in a negative number (an integer)
      - all sqrts of natural numbers are irrational, other than perfect squares
  - - - ex: Proposition. If x and y are odd integers, then x * y is an odd integer. this is a "for all" proposition, meaning it cannot be proven by given examples, as we would be here all day listing every possible example of two odd numbers being multiplied together. instead we use a definition
  - - - constructing direct proofs
        
        start by assuming P is true, and proceed through a logical sequence of steps to arrive to the conclusion that Q must also be true
        
        require: \nDefinitions
        
        definitions are precise statements used for setting up a proof
        
        ex, for the conditional statement "If x and y are odd integers, then x * y is an odd integer." what definition could we use to define an even/odd integer?
        
        integer a is an even integer if there exists an integer n such that a = 2n. integer a is an odd integer if there exists an integer n such that a = 2n + 1.
        
        example of how a definition can be used in constructing a proof with a know show table
        
        other useful tool: backwards question
        
        backward question asks "under what conditions is this proposition true or untrue?"
        
        other useful tool: forwards question
        
        if the hypothesis is true, what conclusions can we draw?
  - - - $$P \wedge Q$$$$P \vee Q$$$$\neg Q$$$$P \Rightarrow Q$$
        
        P and Q\nP or Q\nNot Q\nIf P then Q
        
        $$P \wedge Q$$ is true if P AND Q are true$$P \vee Q$$ is true if P OR Q is true$$\neg Q$$ is true if Q is false, and false if Q is true$$P \Rightarrow Q$$ is false only when P is true and Q is false
        
        both are true\nat least one is true\nopposite value of Q\nfalse if hypothesis is true and conclusion are false, otherwise true(can be true if P = false and Q =false, P = false and Q = true, P = true and Q = true)
    - - $$P \oplus Q$$
        
        true if P is true and Q is falsetrue if Q is true and P is false\nfalse if P is true and Q is true\nfalse if P is false and Q is false
    - - $$P \leftrightarrow Q$$
        
        true if both A and B are false\ntrue if both A and B are true
    - - $$\equiv$$
        
        when two statements, compound statements, or conditional statements have the same truth table
    - - $$P \rightarrow Q \equiv \neg P \vee Q$$
        
        P then Q is equal to Not P OR Q
      - $$\neg (P \rightarrow Q) \equiv P \wedge \neg Q$$
        
        the negation of P then Q is equal to P AND Not Q
      - $$P \rightarrow Q \equiv \neg Q \rightarrow \neg P$$
        
        P then Q is equal to Not Q then Not P
      - $$\neg(\neg P) \equiv P$$
        
        not not p equals p
      - distributive laws
        
        $$P \vee (Q \wedge R) \equiv (P \vee Q) \wedge (P \vee R)$$
        
        P OR (Q and R) equals (P OR Q) AND (P OR R)
        
        $$P \wedge (Q \vee R) \equiv (P \wedge Q) \vee (P \wedge R)$$
        
        P AND (Q OR R) equals (P AND Q) OR (P AND R)
        
        left statement and left operator are distributed to both statements with in the compound statement, and the two new compound statements are joined by the operator inside the original righthand statement
      - de morgans laws
        
        $$\neg{(P \wedge Q)} \equiv \neg P \vee \neg Q$$
        
        the negation of P and Q is equal to Not P OR Not Q
        
        $$\neg{(P \vee Q)} \equiv \neg P \wedge \neg Q$$
        
        the negation of P or Q is equal to Not P AND Not Q
      - $$(P \leftrightarrow Q) \equiv (P \rightarrow Q) \wedge (Q \rightarrow P)$$
      - $$P \rightarrow (Q \vee R) \equiv (P \wedge \neg Q) \rightarrow R$$
      - $$(P \vee Q) \rightarrow R \equiv (P \rightarrow R) \wedge (Q \rightarrow R)$$
  - - - equations with one or more variables on either side, those only become statements when a value is substituted with a variable
  - - - converse and contrapositive
        
        converse swaps the original hypothesis and conclusion
        
        $$P \rightarrow Q$$ becomes $$Q \rightarrow P$$
        
        contrapositive swaps the positions of the original hypothesis with the position of the original conclusion, and negates both of them
        
        $$P \rightarrow Q$$ becomes $$\neg Q \rightarrow \neg P$$
  - - - if a variable exists in a set, its denoted by $$y \in S$$\notherwise $$y \notin S$$
    - - the set of all possible values that can be substituted in for that variable
      - U = {...}
  - - - 4 is a constant value, 1 and 2 are constants
- - - - \nr514 = r414 + (r415(r455)r454) \nk=5 \ni=1 \nj=4 \nr414 = null \nr314 = null \nr214 = null \nr114 = null \ncant work backwards, impossible to go from 1 to 4 without going through 5, so k must be equal or greater than 5 \nr414 = 0 + \ngiven r514 = 110(110) \ni= start \nj = end \nk = max node to get to j \np=k-1 \nrkij = rpij + (rpik(rpkk)rpkj) \nfind r614 \nk = 6 \ni = 1 \nj - 4 \nr614 = r514 + (r516(r566)r564) \nfind r 516, 566, r564 \nrkij = rpij + (rpik(rpkk)rpkj) \nk=5 p=4 i=1 j=6 \nr516 = r416 + (r415(r455)r456) \nr416= null, cant get from 1 to 6 without k=>5 \nr415 = 1 \nr455 = e + (101) \nr456 = 0, can go from 5 to 6, but cant go from 5 to 6 to 5, or 5 to 6 and loop to 6, because they would use a node higher than 4 as an intermediate state \nr516 = 1(101)0 \nrkij = rpij + (rpik(rpkk)rpkj) \nr566 = r466 + (r465(r455)r456) \nr466 = e+1 \nr465 = 0 \nr455 = e + (101) \nr456 = 0 \nr566 = e+1 + (0(101)0) \nr564 = r464 + (r465(r455)r454) \nk=5 i = 6 j = 4 p = 4 \nr464 = null \nr465 = 0 \nr455 = e + (101) \nr454 = 10 \nr564 = null + (0(e + (101))10) \nr564 = 0(101)10* \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
- - - - all regular languages are context-free languages
      - not all context-free languages are regular languages
      - two ways to describe a CFL: a PDA or a CFG
      - properties of CFLs
        
        *(star) closure properties
        
        closued under substitution, union, concatenation, kleene closure, homomorphisms, and reversal
        
        not closed under reversal, intersection, or difference (except for CFL - Regular Language, which results in a CFL)
        
        *(star) decision properties
        
        properties of CFLs can be proven using
        
        Chomsky Normal Form
        
        for every non empty CFL, there is a grammar G for L(G) - {$\epsilon$} that contains no useless symbols and each production has the form $A \rightarrow BC $ or $A \rightarrow a$
        
        useless variable
        
        X is useless if there exists no derivation in G where X can be reached from the Starting symbol and/or X can be used to generate at least one non-empty string
        
        1 more item...
        
        step 4: eliminate unreachable variables and symbols
        
        1 more item...
        
        step 3: eliminate non-generating variables
        
        1 more item...
        
        step 2: eliminate $\epsilon$-productions
        
        1 more item...
        
        step 1: eliminate unit productions
        
        2 more items...
        
        step 5: factor remaining into form $A \rightarrow BC $ or $A \rightarrow a$
        
        Pumping Lemma for CFLs
        
        compare to pumping lemma for regular languages
        
        used the same way as pumping lemma for regular languages, but with different rules
        
        choose a string z of length $\ge$ n(a chosen length) that can be divided into parts uvwxy, and violates one of these rules:
        $|vwx| \le n$ (middle isnt bigger than the whole string)
        $vx \ne \epsilon$ (at least one of v or x must be nonempty)
        $\forall i \ge 0, uv^iwx^iy \in L$ (v and x can be repeated as many times as we want without leaving the language the string z is a part of )
  - - - variable
        
        non-terminal symbols, where each symbol denotes a set of strings
      - terminal symbol
        
        the alphabet used to make each string
      - productions
        
        rules for recursively producing structure of the language
        
        a production p takes the form:
        p = A $\rightarrow \alpha $
        where A is a Variable ( $ A \epsilon V $ )
        $\alpha $ is a string of 0 or more variables or terminal symbols
        
        recursive as in they depend on V,T,S
      - starting symbol
        
        variable representing the set of all the strings that make up the ENTIRE language
        
        pick the one that gives you the most options
        
        ex:
        $E \rightarrow I $
        $E + E $
        $I \rightarrow a$
        $I \rightarrow b$
        You CAN choose any variable as a starting symbol, but E should be picked because you cant get to E if you pick I, and therefore cant form a + b if I is chosen
      - example
        
        V = {S}
        T = {0,1}
        P:$ S \rightarrow 01 $
        $ S \rightarrow 0S1 $
        S = S
        
        CFG for $0^n1^n | n \ge 1$
  - - - S
    - - we always choose the starting symbol
    - - replace the chosen variable with the right hand side of the production
        
        repeat steps in order until no variables are left, only terminal symbols
    - - used to simplify string derivation steps
        
        example:
        
        1.S
        2.S
        3.S $\rightarrow$ 0S1
        
        0S1
        
        S
        
        S $\rightarrow$ 0S1
        
        00S11
        
        S
        
        S $\rightarrow$ 01
        
        000111
        
        $ S \implies 0S1 \implies 00S11 \implies 000111$
        
        records the replacement steps
        
        records the starting string and every string after the variable selection, production selection, and replacement steps of derivation are completed
    - - 1.start with start symbol
        2.pick leftmost variable in current string
        
        pick production with that variable on lhs
        
        replace variable in string with rhs of p
        repeat until only terminal symbols left
        
        rightmost derivation
        
        same as leftmost derivation steps, only we choose rightmost variable instead of leftmost
        
        if you know leftmost you know rightmost, only difference is which variable gets picked each time
      - a valid derivation can be nonleftmost/nonrightmost(expanding a symbol in the middle ex: TATAT->TAtaAT) as long as multiple steps are not taken at once ex: ET -> ab
    - - used to simplify derivation steps
        
        instead of using definition to simplify the steps by only recording the replacement steps, we record only the productions selected to make replacements instead of the strings after replacements are made
        
        example
        
        $Expr \rightarrow id $
        $Expr \rightarrow Expr + Expr$
        $Expr \rightarrow Expr * Expr$
        $Expr \rightarrow (Expr) $
        a + b * c
        
        Expr
        
        Expr
        
        1 more item...
        
        +
        
        Expr
        
        1 more item...
        
        records the production selection step
      - used to show if a string or a grammar is ambiguous
        
        a string is ambiguous to a grammar if two distinct leftmost derivations and/or rightmost derivations can be constructed to form the same string using that grammar
        
        a grammar is ambiguous if an ambiguous string can be formed using it
        
        ambiguity can be fixed by adding layering
        
        example:
        
        $Expr \rightarrow id $
        $Expr \rightarrow Expr + Expr$
        $Expr \rightarrow Expr * Expr$
        $Expr \rightarrow (Expr) $
        
        1 more item...
        
        a context-free language is inherently ambiguous if it only has ambiguous grammars
        
        there are no algorithms to determine if a context-free grammar is ambiguous
        
        but common forms of ambiguity like precedence and associativity restrictions can be recognized by parser generators
        
        example
        
        $Expr \rightarrow id $
        $Expr \rightarrow Expr + Expr$
        $Expr \rightarrow Expr * Expr$
        $Expr \rightarrow (Expr) $
        a + b * c
        
        Expr
        
        Expr
        
        1 more item...
        
        Expr
        
        1 more item...
        
        *
- - - - ex: S = {1,2,3,4,...}
  - - - $$\sub$$
  - - - $$\supset$$
- - - - transition = movement from one state to another
        
        heat causes change of state in matter
      - final = accepted = accepted language
    - - what are the possible ways to get to final?
      - what are the possible ways to NOT get to final state?
      - what are the symbols on lines? thats your alphabet
      - notes from analyzing this diagram
        
        answer: all strings a,b that do not contain the substring aa
    - - what cases must be satisfied and how do i test them
      - what boundary cases do i need to test for (ex: empty string)
      - start with diagrams you know to be correct, then determine if you can merge start states and final states
      - what set of strings does each state represent, if you dont know what set of strings would lead to a state, consider whther you need it or not
        
        ex: given {01,101}∗ \n what do q1, q4, q5 represent?
        
        q1 = strings starting with 01 and ending in 01, that may have an extra 0 (note the only symbol leading out is a 1), so as soon as it hits 1 it moves to next state, s0 {01,101}∗{0} \n
        
        q4 = strings starting and ending with 101 that may have an extra 1 ( note the only symbol leading out is a 0), so as soon as it hits 0 it moves to next state, so {01,101}∗{1}
        
        q5 = strings starting and ending with 101 that may have an extra 10,
        
        the pattern is that each one can have as many repeating characters from previous transitions as they want, as long as they end in 01 or 101
  - - - state = collection of information remembered by a system
        
        state of the union is info about the us at that point in time
    - - Q
    - - FA = (Q,Σ,q0,A,δ)
        
        Q = finite set of states
        
        Σ = finite input alphabet(set of non-empty symbols
        
        q0 = initial state, q0 ∈Q ( the initial state is a member of the finite set of states)
        
        A = set of accepting states, A ⊆Q (A is a subset of the finite set of states)
        
        δ = , the transition function
        
        Q x Σ -> Q(each single state multiplied by each single input for each input leads to a state)
        
        set multiplication, ex
        
        {1,2,3} x {a,b} = {(1,a),(2,a),(3,a),(1,b),(2,b),(3,b)}
        
        given Q={q0,q1,q2,0,1,2}\nΣ={0,1}\nδ would be $$\begin{array}{ } \n \\ & &\text{Starting State}\n\\\n \hline& & q0 & q1 &q2 & 0 & 1 & 2 \\ \hline \text{Input} & 0&q1&q2&q2&0&2&1 \\ \n &1&1&q2&q2&1&0&2 \\ \n\hline \end{array} $$
        
        set of pairs(functions), {state+input,result),(state+input,result2),....}
        
        the function (q0,0),q1) means\nstate q0 when given input 0 will lead to q1
        
        the function (0,0),0) means \nstate 0 when given input zero will lead to 0\n
      - 5-tuple
        
        tuple = finite SEQUENCE of elements
        
        5 tuple = sequence of 5 elements
      - same for nondeterministic, only difference is δ
        
        for NFA, δ = Q X Q x Σ -> $$2^Q$$
      - only difference in definitions between deterministic and nondeterministic is that the functions for DFA can only have one function for each input and output pair, while nondeterministic can have more than 1 function per input and output pair
  - - - single thread vs multithread
    - - like shrodingers cat, the state can either be outcome A or B given a single input
- - - - read inputs to stack until last variable is reached
        pop inputs from stack once last varaible is reached
        once stack is empty, accept state is reach(if and only if youre at the end of input)
        
        ex
        
        0^k 1^k | k>=0
        
        read 0s from input and push to stack until a 1 is encountered
        when a 1 is read, pop 0s from stack
        once stack is empty, accept state is reach(if and only if youre at the end of input)
        
        $\delta(q,0,Z) = \{\ (q,XZ)\}\ $
        
        for first 0 in input, push X to stack
        
        $\delta(q,0,X) = \{\ (q,XX) \}$
        
        for each subsequent 0, push an X to the stack
        
        $\delta(q,1,X) = \{\ (p,\epsilon) \}$
        
        at first 1, go to state p and pop one X
        
        $\delta(q,1,X) = \{\ (p,\epsilon)\}$
        
        pop an X for each subsequent !
        
        $\delta(p,\epsilon,Z) =\{\ (f,Z)\}$
        
        1 more item...
        
        transition labels
        
        $a, X/\alpha$
        
        1 more item...
        
        tell us if input is a and top of stack is X, replace X with $\alpha$
  - - - $Q $
        $ \Sigma$
        $\delta$
        $q0$
        
        unchanged:
        set of states
        input alphabet
        transition function
        start state
        
        $\delta$ tranisition function mapping:
        ${Q, * \Sigma, * \Gamma \rightarrow Q * \Gamma^*}$
        
        aka
        
        $\delta (qi,a,Z) = (qj,a)$
        
        transition function only looks at current state and the input symbol for FAs, while for PDAs it looks at current state, input symbol, and top of stack
        
        transition function for PDA returns list of (state,string) pairs, where string is a sequence of symbols to be pushed onto the stack
        
        $\Gamma$
        
        stack alphabet(which symbols can be pushed onto it
        
        $Z$
        
        $Z \epsilon \Gamma$, the bottom (starting symbol) of the stack
        
        $F \subseteq Q$
        
        set of $F$inal states, same as A in FA definition
- - - - canvas editor
        
        superscript/subscript (hit once to enter ss mode then hit again to exit, or click and drag over which text you want to ss)
      - html entitites
        
        accessed through </> button, then type &characterName;
        
        Entity Renders As meaning\nα α\nalpha\nβ β\nbeta\nγ γ\ngamma\nδ δ\ndelta\nε ϵ\nepsilon, empty string\n&lamda; λ\nlambda, “special” mark\nσ σ\nsigma\nΣ Σ\nupper-case sigma, alphabets\n≠ ≠\nnot equal to\n≤ ≤\nless than or equal to\n≥ ≥\ngreater than or equal to\n→ →\nsimple right arrow\n⇒ ⇒\nderives, implies\n∧ ∧\nlogical and\n∨ ∨\nlogical or\n∈ ∈\nis in (set membership)\n∩ ∩\nintersection\n∪ ∪\nunion\n⊂ ⊂\nis a proper subset of\n⊆ ⊆\nis a subset or equal to\n∀ ∀\nfor all\n∃ ∃\nthere exists\n𝒩 N\nnatural numbers\nℜ R\nreal numbers
      - tex
        
        in canvas only:
        
        canvas only uses the math portion of latex(which is the same as/comes from tex) accessed through math editor($$\sqrt{x}$$ button), inline only, dont use \$...\$ or \\[...\\]
        
        combine superscript and subscript for $$x_1^2$$
        
        x_1^2
        
        create $$xi + 1 $$ and $$x{i+1}$$
        
        \\{x_{ij}\\}
        
        \\
        
        used for
        
        commands, alternative uses of special characters
        
        \\frac{numerator}{denominator}
        
        create $$\{x_{ij}\}$$
        
        \\{x_{ij}\\}
        
        create$$\sqrt{n}$$
        
        \\sqrt{n}
        
        add braces to arrays
        
        create $$\left\{\n\begin{array}{ll}\n n/2 & \text{if n is even} \\\n (-n-1) & \text{if n is odd} \\\n\end{array}\n\right.$$
        
        \\left\\{\n\\begin{array}{ll}\n n/2 & \\text{if n is even} \\\\\n (-n-1) & \\text{if n is odd} \\\\\n\\end{array}\n\\right.
        
        %
        
        used for comments
        
        click on the expression to view comment in editor:$$x + y = % addition is commutative$$
        
        division
        
        frac vs /
        
        \\frac{numerator}{denominator}\n
        
        create $$ a * b + c / (d - e)$$
        
        a * b + c / (d - e)
        
        create$$\frac{a * b + c}{(d - e)} $$
        
        \\frac{a*b+c}{(d-e)}
        
        positive, negative sign
        
        /p, /m
        
        rel ops
        
        LaTeX \nRenders As \nmeaning\nx < y x<y \nless than \nx > y x>y \ngreater than \nx = y x=y \nequal to \nx \\neq y x≠y \nnot equal to \nx \\leq y x≤y \nless than or equal to \nx \\geq y x≥y \ngreater than
        
        outside of canvas
        
        < is <\n> is >
        
        create x < y, x > y
        
        1 more item...
        
        bool ops
        
        LaTeX \nRenders As \nmeaning\nx \\wedge y x∧y\nand\nx \\vee y x∨y\nor\n\\neg x ¬x\nnot
        
        resizable
        
        summation
        
        create $$\sum_i^n x_i $$
        
        \\sum_i^n x_i
        
        product
        
        create $$\prod_i^n x_i $$
        
        \\prod_i^n x_i
        
        parentheses and brackets
        
        \\left(....\\right)
        
        \\left{...\\right}
        
        \\left[...\\right]
        
        can mix and match
        
        \\left(...\\right]
        
        create $$ \sum_{i=0}^n (xi + i) = \left(\sum{i=0}^n xi \right) + \left(\sum{i=0}^n i\right) = (n \bar{x}) + \left(\frac{n(n+1)}{2}\right) \n$$
        
        \\sum_{i=0}^n (xi + i) = \\left(\\sum{i=0}^n xi \\right) + \\left(\\sum{i=0}^n i\\right) = (n \\bar{x}) + \\left(\\frac{n(n+1)}{2}\\right) \n
        
        to create a lone bracket
        
        replace the bracket/brace/paranthesis on one end with a '.'
        
        \\left(\\right. or \\left.\\right}
        
        regular text (non-comment)
        
        \\mbox
        
        create
        
        \\text
        
        create $$n/2 \text{ if n is even}$$
        
        n/2 \\text{ if n is even}
        
        array
        
        \\begin{array}{numcols}\na & b \\\\\nc & d \\\\\n... \\end{array}
        
        to add brackets, \\left[ \\begin{array} \\ end{array} \\right], \\left{ \\begin{array} \\ end{array} \\right}, \\left( \\begin{array} \\ end{array} \\right),
        
        create $$\left\{\n\begin{array}{ll}\n n/2 & \text{if n is even} \\\n (-n-1) & \text{if n is odd} \\\n\end{array}\n\right.$$
        
        \\left\\{\n\\begin{array}{ll}\n n/2 & \\text{if n is even} \\\\\n (-n-1) & \\text{if n is odd} \\\\\n\\end{array}\n\\right.
        
        elem separators: &\nrow separators: \\\\
        
        pseudotable
        
        \\begin{array}{ } \n \\\\ & &\\text{Starting State}\n\\\\\n \\hline& & q0 & q1 &q2 & 0 & 1 & 2 \\\\ \\hline \\text{Input} & 0&q1&q2&q2&0&2&1 \\\\ \n &1&1&q2&q2&1&0&2 \\\\ \n\\hline \\end{array}
        
        ellipses
        
        \\ldots\n...
        
        \\vdots $$\vdots$$
        
        \\ddots$$\ddots$$
        
        create $$ \left[\begin{array}{llll}\n 1 & 0 & \ldots & 0 \\\n 0 & 1 & \ldots & 0 \\\n \vdots & \vdots & \ddots & \vdots \\\n 0 & 0 & \ldots & 1 \\\n\end{array}\right] $$
        
        \\left[\\begin{array}{llll}\n 1 & 0 & \\ldots & 0 \\\\\n 0 & 1 & \\ldots & 0 \\\\\n \\vdots & \\vdots & \\ddots & \\vdots \\\\\n 0 & 0 & \\ldots & 1 \\\\\n\\end{array}\\right]