Please enable JavaScript.

Coggle requires JavaScript to display documents.

Started by these guys Kurt and Turing - Coggle Diagram

- - - - Length |w| :red_flag:
      - Concatenation: XY :red_flag:
      - Alphabet: Finite set of symbols
        
        Formal Language L: a set of strings from one alphabet :star:
        
        Empty Language
        
        Special Languages: Sigma+ Sigmastar : Sigmastar is a infinite set
        
        All possible languages: P(sigma*)
        
        Concatenation: L1L2
        
        Union: L1 + L2
        
        Kleene closure: L*
        
        Empty Language: LPHI, PHI Remember: PHI* is not empty , it has { A }
        
        Regular Expressions :star:
        
        Base cases: empty language, empty set , symbols in the alphabet
        
        Recursion: r+s ( Union) , rs ( Concatenation) , r* Kleene Closure
        
        Kleenes Theorem : :star:
        
        Conversion ( RE -> NFA with e moves ) :warning:
        
        Algorithm :check:
        
        6 more items...
        
        Conversion ( NFA with e moves -> RE ) :warning:
        
        Algorithm :check:
        
        6 more items...
        
        Classifying of languages :star:
        
        REGULAR LANGUAGES :star:
        
        1 more item...
        
        NON REGULAR LANGUAGES :star:
        
        1 more item...
        
        The Pumping Lemma ??? :red_flag:
        
        2 more items...
        
        Empty alphabet: :forbidden:
        
        Formal Finite Automaton: (FA) : 5 tuple (Q,sigma,qo,T,Transition Function :red_flag:
        
        Nondeterministic Finite Automaton (NFA): M(Q,sigma,qo,T,Transition function:( Q X sigma -> P(Q) :red_flag:
        
        Algorithm to solve: :check:
        We consider only the set of states resulting from processing the entire string.
        If at least one of those states is an accepting state, then accept the string, otherwise reject.
        
        NFA with e-transitions: M(Q,sigma,qo,T,(Q X (sigma UNION {e} ) -> P(Q) :red_flag:
        
        E-closure: set of states :warning:
        This means that when the automaton enters a state with an outgoing e-transition, the automaton may stay in that state or traverse the e-transition to its destination state.
        
        Conversion(NFA with e-moves to FA) :warning:
        
        Algorithm (NFA with e -> DFA ) :check:
        
        Same alphabet Lose column e
        Loose all nondeterminism
        Loose all empty sets
        Cell values are now set of states
        -> states
      - Empty string