Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 36 vistas

    TP2 2

    Cargado por

    ARIASYT
    Este documento describe los cuatro tipos de gramáticas (Tipo 0, 1, 2 y 3), junto con sus lenguajes correspondientes, formas de reglas de producción y autómatas que los interpretan. Explica que las gramáticas de Tipo 0 tienen reglas de producción sin restricciones y generan lenguajes no restringidos, mientras que las de Tipo 1 son sensibles al contexto, Tipo 2 son de contexto libre y Tipo 3 son regulares. También incluye una tabla resumiendo esta información.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    TP2 2

    Cargado por

    ARIASYT
    36 vistas3 páginas
    Este documento describe los cuatro tipos de gramáticas (Tipo 0, 1, 2 y 3), junto con sus lenguajes correspondientes, formas de reglas de producción y autómatas que los interpretan. Explica que las gramáticas de Tipo 0 tienen reglas de producción sin restricciones y generan lenguajes no restringidos, mientras que las de Tipo 1 son sensibles al contexto, Tipo 2 son de contexto libre y Tipo 3 son regulares. También incluye una tabla resumiendo esta información.

    Título original

    TP2.2

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento describe los cuatro tipos de gramáticas (Tipo 0, 1, 2 y 3), junto con sus lenguajes correspondientes, formas de reglas de producción y autómatas que los interpretan. Explica que las gramáticas de Tipo 0 tienen reglas de producción sin restricciones y generan lenguajes no restringidos, mientras que las de Tipo 1 son sensibles al contexto, Tipo 2 son de contexto libre y Tipo 3 son regulares. También incluye una tabla resumiendo esta información.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    36 vistas3 páginas

    TP2 2

    Cargado por

    ARIASYT
    Este documento describe los cuatro tipos de gramáticas (Tipo 0, 1, 2 y 3), junto con sus lenguajes correspondientes, formas de reglas de producción y autómatas que los interpretan. Explica que las gramáticas de Tipo 0 tienen reglas de producción sin restricciones y generan lenguajes no restringidos, mientras que las de Tipo 1 son sensibles al contexto, Tipo 2 son de contexto libre y Tipo 3 son regulares. También incluye una tabla resumiendo esta información.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    Está en la página 1de 3

    Trabajo práctico Individual 2.

    Compiladores

    Unidad 2

    Roberto Daniel Melgarejo Arias

    5.778.791

    Fecha de entrega: 04-diciembre

    2023
    Desarrollar en un solo documento los siguientes puntos:

    1. Describir los cuatro tipos de gramática, junto con su lenguaje correspondiente,


    forma de reglas de producción y autómata correspondiente que los interpreta.

    Comenzamos mencionando las gramáticas de tipo 0, también conocidas como gramáticas


    no restringidas, recursivamente e numerables o gramáticas con estructura de frase, sus
    reglas de producción de derivación son de la forma: α→β, los lenguajes descritos por este
    tipo son todos los lenguajes reconocibles por una máquina de Turing.

    Seguimos con las gramáticas de tipo 1, conocidas como gramáticas sensibles al contexto
    (context sensitive), sus reglas de producción son de la forma: α A β → αγβ siendo A ∈
    N; α, β ∈ (N ∪ T) * y γ ∈ (N ∪ T). Dicho de otra forma, A es no terminal y α, γ, β son
    cadenas con terminales y/o no terminales. α, β pueden ser vacías, pero γ no. La regla S→
    λ solamente es permitida si S no aparece en el lado derecho (resultado) de ninguna otra
    regla. Es sensible al contexto porque se puede reemplazar A (un no terminal) por γ (un
    terminal) siempre que estén en el contexto α.…β. Los descritos por este tipo son todos
    los lenguajes reconocibles por un autómata linealmente acotado no determinista.

    En el aspecto de compiladores, este tipo de gramática con el que se trabaja


    principalmente, ya que es el que corresponde a los lenguajes de programación d e alto
    nivel, las gramáticas de tipos 2, conocidas como gramáticas de libre contexto (GCL) o
    (context free), solo admiten un símbolo no terminal en su parte izquierda en sus reglas de
    producción, es decir son de la forma: A →α siendo A ∈ N y α ∈ (N ∪ T). Es decir, A es
    no terminal y α una cadena de terminales y/o no terminales. Si cada regla se representa
    como un par ordenado (A, α), el conjunto P es un sub conjunto del conjunto producto
    cartesiano N × ({N ∪ T}) +, es decir: P ⊂ {N × ({N} ∪{T}) +}, por lo que la
    denominación de contexto libre se debe a que puede cambiar A por α, independientemente
    del contexto en que aparezca A. las gramáticas de tipo 2 generan exactamente todos los
    lenguajes reconocidos por un autómata de pila.

    Por último, tenemos las gramáticas de tipo 3 conocidas como regulares, comienzan sus
    reglar de producción en la derecha con un símbolo terminal, que puede ser seguido o no
    por un símbolo no terminal, es decir son de la forma: A → aB, A → a donde A, B ∈ N y
    α ∈ T. las reglas restringen el uso de un solo no terminal a la izquierda, y el lado derecho
    compuesto por un terminal, o alternativamente un terminal seguido por un no terminal.
    Las gramáticas de tipo 3 generan los lenguajes regulares reconocibles por un autómata
    finito

    2. Lenguaje Forma de reglas Autómata

    Reglas de
    Gramática Lenguaje Autómata
    producción
    Recursivamente e
    Tipo 0 numerable o no Máquina de Turing α→β (sin restircc)
    restringida
    Sensible al Linealmente
    Tipo 1 αAβ→αℽβ
    contexto acotado (ND*)
    Tipo 2 Libre contexto De pila (ND*) A→α
    Tipo 3 Regular Finito A→aB/A→a
    → Indicaciones de resolución y entrega:

    • La actividad es de carácter individual.


    • Entregar el trabajo en formato .PDF
    • Ante cualquier duda, contacta con tu docente-tutor, mediante el correo de
    plataforma.
    • Lee atentamente la rúbrica para conocer los criterios que se tendrán en cuenta
    para calificar la tarea.

    También podría gustarte