Gramática (autómata)

Gramática (autómata)

Una gramática ("G") desde el punto de vista de la teoría de autómatas es un conjunto finito de reglas que describen toda la secuencia de símbolos pertenecientes a un lenguaje específico L. Dos gramáticas que describan el mismo lenguaje se llaman gramáticas equivalentes.

Una gramática es una estructura algebraica formada por cuatro elementos fundamentales:

G = { NT, T, S, P }

donde

  • NT es el conjunto de elementos 'No Terminales,
  • T es el conjunto de elementos Terminales
  • S es el Símbolo inicial de la gramática
  • P es el conjunto de Reglas de Producción

Contenido

Clasificación de las gramáticas según Chomsky

Las gramáticas se clasifican de acuerdo a las reglas de sustitución

Tipo 0 o "No restringida o recursivamente enumerables"

Chomsky grammar 0.png

“x puede ser sustituido por y si x está, ya sea, en los símbolos No Terminales o los símbolos Terminales, sin incluir la cadena vacía e y está en los símbolos No Terminales o Terminales, incluyendo la cadena vacía.”

Los lenguajes generados por este tipo de gramáticas se llaman "lenguajes sin restricciones"

Nota: "+" significa "sin incluir la cadena vacía" y "*" significa "incluyendo la cadena vacía". "/" significa "o"

Estos lenguajes también son denominados "recursivamente enumerables"

Las máquinas que los aceptan son las máquinas de Turing (y equivalentes no deterministas)

Tipo 1 o "Sensible al contexto"

Chomsky grammar 1.png

“α puede ser reemplazado por β si la longitud de α es menor o igual a la longitud de β, siendo α un símbolo Terminal o una cadena vacía z1, seguido de un símbolo No Terminal z2, seguido de otro símbolo Terminal o una cadena vacía z2. z1 debe ser el mismo símbolo z1 de α seguido de un símbolo No Terminal o Terminal sin ser la cadena vacía, seguido del símbolo z2.”

Las máquinas que los aceptan son autómatas linealmente acotados(linear-bounded).

Tipo 2 o "libre de contexto"

Chomsky grammar 2.png

“x puede ser reemplazado por y si x pertenece a los símbolos No Terminales y y es un Terminal o No Terminal, incluyendo la cadena vacía.”

Máquinas que los pueden leer:

Máquinas que los aceptan: Autómata a Pila (Pushdown Automaton)

Tipo 3 o "Regular"

Chomsky grammar 3.png

También llamada "De contexto regular"

“α puede ser reemplazado por β si α pertenece a los símbolos No Terminales y β es uno de estos 3:

  • Un símbolo Terminal no nulo seguido de un No Terminal.
  • Un símbolo No Terminal seguido de un símbolo Terminal no nulo.
  • Un símbolo Terminal pudiendo ser la cadena vacía.”
 Máquinas que los aceptan: autómata finito, determinista o no determinista.

Véase también


Wikimedia foundation. 2010.

Игры ⚽ Поможем написать реферат

Mira otros diccionarios:

  • Gramática (autómata) — Una gramática G desde el punto de vista de un autómata, es un conjunto finito de reglas que describen toda la secuencia de símbolos pertenecientes a un lenguaje específico L. Una gramática es una estructura algebráica formada por 4 elementos… …   Enciclopedia Universal

  • Gramática — (Del lat. grammaticus < gr. grammatikos, crítico literario.) ► sustantivo femenino 1 GRAMÁTICA, LINGÜÍSTICA Estudio y descripción que tiene como objeto establecer los elementos que componen las lenguas y las reglas que rigen su comportamiento …   Enciclopedia Universal

  • Gramática libre de contexto — En lingüística e informática, una gramática libre de contexto (o de contexto libre) es una gramática formal en la que cada regla de producción es de la forma: V → w Donde V es un símbolo no terminal y w es una cadena de terminales y/o no… …   Wikipedia Español

  • Jerarquía de Chomsky — Noam Chomsky. En lingüística la jerarquía de Chomsky es una clasificación jerárquica de distintos tipos de gramáticas formales que generan lenguajes formales. Esta jerarquía fue descrita por Noam Chomsky en 1956. Contenido …   Wikipedia Español

  • Forma normal de Chomsky — Saltar a navegación, búsqueda Una gramática formal está en Forma normal de Chomsky si todas sus reglas de producción tienen de una de las siguientes formas: A BC o A α o S λ donde S es el símbolo distingu …   Wikipedia Español

  • Forma normal de Greibach — Saltar a navegación, búsqueda Se dice que una gramática independiente del contexto (GIC) está en Forma normal de Greibach (FNG), si todas y cada una de sus reglas de producción tienen un consecuente que empieza por un carácter del alfabeto,… …   Wikipedia Español

  • Analizador sintáctico LR — Este artículo o sección necesita una revisión de ortografía y gramática. Puedes colaborar editándolo (lee aquí sugerencias para mejorar tu ortografía). Cuando se haya corregido, borra este aviso por favor. Los analizadores sintácticos LR, también …   Wikipedia Español

  • Autómatas linealmente acotados — Saltar a navegación, búsqueda Un autómata linealmente acotado, abreviadamente LBA (del inglés, Linear Bounded Automaton), es un autómata similar a una máquina de Turing no determinista. Contenido 1 Historia 2 Autómatas lineales …   Wikipedia Español

  • Analizador sintáctico — Un analizador sintáctico (en inglés parser) es una de las partes de un compilador que transforma su entrada en un árbol de derivación. El análisis sintáctico convierte el texto de entrada en otras estructuras (comúnmente árboles), que son más… …   Wikipedia Español

  • Lenguaje sensible al contexto — En las ciencias de la computación, un lenguaje sensible al contexto es un [[lenguaje formal] que puede ser definido por gramáticas sensibles al contexto. Es uno de los cuatro tipos de gramáticas en la jerarquía de Chomsky, siendo esta gramática… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”