Please enable JavaScript.

Coggle requires JavaScript to display documents.

Computing - Coggle Diagram

- - - - Finite Automata
        
        DFA
        
        Cross Product
        
        simulates parallel running
        
        Language of crossp of two DFAs is the intersection of both's languages
        
        a special kind of NFA since NFAs are atleast as powerful as a DFA
        
        NFA
        
        NFA with e-moves
        
        epsilon moves don't consume a symbol
        
        nondeterminism can be tamed but can result in exponential increase in states so we use e-moves instead
        
        Can be Converted into a DFA using subset construction
        
        a special kind of eNFA
        
        Regular Expression
        
        Can build NFA that accepts the same language as a regular Expr
        
        Rules
        
        assuming L(a) and L(b) are regular
        
        L(a+b) is regular and equal to L(a)UL(b)
        
        L(ab) is regular and equal to L(a)L(b)
        
        L(a) is regular and equal to L(a)
        
        All precisely accept regular languages
      - same expressive power as regular expressions
      - PDA
        
        can simulate NFAs and DFAs
        
        therefore every language accepted by DFA (regular) is accepted by a PDA and therefore a context free language also
        
        however not all CFLs are regular
        
        can recognise irregular languages
        
        single-state PDA
        
        can convert a CFG into a single state PDA showing any CFG can be made into a PDA
        
        can be constructed from a PDA
        
        can also be converted back into a CFG
        
        can generate the same languages as CFG
    - - Regular Language
        
        Closure
        
        Union & Intersection
        
        Concatenation
        
        Kleene Star
        
        complementation
        
        Accepted precisely by DFAs,NFAs and eNFAs
        
        Any language that accepts the production of a RegExpr is regular
        
        Proving irregularity
        
        contrapositive of pumping lemma
        
        the pumping lemma essentially shows that a language can be processed by with finite states (finite automata)
        
        The contrapositive allows us to show it CANNOT be processed by a finite number of states and hence is NOT REGULAR
        
        Demon game is a good way of putting the CP pumping lemma in to understanable terms
        
        Essentially want to createa contradiction without making any assumptions about what the demon does
        
        all regular languages are context-free
      - Sigma Σ means the alphabet
      - Σ* is the set of all strings over Σ
  - - - Formal definition of an algorithm - Equivalent to Lambda calculus
      - Multi-Tape TMs
        
        can be simulated by single tape TMs so their expressive power is the same
        
        has independent semi-infinite tapes and read/write heads
      - universal TMs
        
        a machine that can simulate all other TMs
        
        an example of interpreters
    - - recursively enumerable if it is equal to the language of some TM
      - co-recursively enumerable if its complement is r.e
      - recursive if it is equal to the language of some TOTAL TM
      - Properties are defined as:
        
        Decidable if the set of satisfying strings is recursive
        
        Semidecidable if the set of satisfying strings is recursively enumerable
        
        The relationship between decidability and recursiveness is two way
  - - - The language generated by a CFG is the set of all its sentences
      - Normal Forms
        
        Chomsky normal form
        
        all productions are of the form A -> BC or A -> a (i.e. two non terminals or a terminal)
        
        for every CFG G there exists a CNF version G' such that L(G') = L(G) - {e}
        
        Greibach normal form
        
        all productions are of the form A -> aB1B2B3...Bk (i.e. terminal followed by non terminals)
        
        cannot generate the empty string e
        
        removes all unit-productions and e-productions
      - parse tree of CFG derivation can be used to show pumping lemma can be used to prove if a language if CF
      - like with proving recursive/r.e languages, the CONTRAPOSITIVE of the PUMPING LEMMA can be used to show a lnaguage is not context free
    - - A language L is called a context free language if there exists a CFG G such that L = L(G)
      - Closure
        
        Union
        
        Concatenation
        
        Kleene Star
        
        intersection with regular languages
        
        NOT under intersection or complementation