Please enable JavaScript.

Coggle requires JavaScript to display documents.

Teoría de autómatas y lenguajes formales - Coggle Diagram

- - - - suele llamar letras del alfabeto
      - EJEMPLO:Σ1 = {a,b,c,...,z} Σ2 = {0,1}
      - conjunto no vacío y finito de símbolos
    - - secuencia finita de símbolos de un alfabeto
      - EJEMPLO: x = casa es una palabra definida sobre el alfabeto Σ1
    - - Es un conjunto cualquiera de palabras
        definidas sobre dicho alfabeto, por lo tanto, L ⊂ ω(Σ)
    - - Generalmente utilizaremos los Autómatas Finitos para reconocer lenguajes regulares, es decir, una palabra se consideran validas solo si pertenece a un determinado lenguaje.
      - Formalmente, un Autómata Finito Determinista (AFD) se define como una tupla ,AF D = (Σ, Q, f, q0, F ) Donde:
        Σ es el alfabeto de entrada
        Q es el conjunto finito y no vació de los estados del Autómata
        es la función de transición que indica en qu´e situaciones el Autómata pasa deun estado a otro, se define f : Q × Σ −→ Q
        q0 ∈ Q es el estado inicial
        F ⊂ Q es el conjunto de estados finales de aceptación (F � = Ø)
    - - cualquier lenguaje independiente del contexto puede ser reconocido
        por un Automata de Pila.
      - AP = {Q, Σ, f, Γ, q0, z0, F }
    - - En los no deterministas podemos encontrarnos con varias opciones e, incluso, con λ- transiciones.
    - - conjunto de todas las palabras
        que se pueden construir con las letras de dicho alfabeto
      - Ejemplo: si Σ = {a} entonces ω(Σ) = {λ, a, aa, aaa, ...}
    - - Es una notación normalizada para representar lenguajes
        regulares, es decir, lenguajes generados por gramáticas de tipo 3.
      - EJEMPLO:01 + 001 es una e.r. que representa al lenguaje L = {01, 001}
    - - Por
        Extensión
        
        Es un tipo de lenguaje formal que se define enumerando explícitamente todas las cadenas o palabras que forman parte del lenguaje.
      - Por comprensión
        
        es una manera de definir un lenguaje formal mediante la especificación de un patrón o una regla que describe todas las cadenas que pertenecen al lenguaje.
    - - Se llama gramática formal definida sobre un alfabeto Σ a una tupla de la forma
        G = {ΣT , ΣN , S, P } donde
        ΣT es el alfabeto de símbolos terminales
        ΣN es el alfabeto de símbolos no terminales
        S es el símbolo inicial de la gramática
        P es un conjunto de producciones gramaticales
      - EJEMPLO :ΣT = {+, −, 0, 1, 2, . . . , 9}
    - - union
      - Concatenación
      - Estrella de
        Kleene