Automata

automata gramatica diferencias

Gramática (autómata)
De Wikipedia, la enciclopedia libre
Saltar a navegación, búsqueda
Una gramática ("G") desde el punto de vista de la teoría de autómatas es unconjunto 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.
Unagramá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 elementosTerminales
* S es el Símbolo inicial de la gramática
* P es el conjunto de Reglas de Producción
Contenido[ocultar] * 1 Clasificación de las gramáticas según Chomsky * 2 Tipo 0 o "Norestringida o recursivamente enumerables" * 3 Tipo 1 o "Sensible al contexto" * 4 Tipo 2 o "libre de contexto" * 5 Tipo 3 o "Regular" * 6 Véase también |
[editar] Clasificación de las gramáticassegún Chomsky
Las gramáticas se clasifican de acuerdo a las reglas de sustitución.
[editar] Tipo 0 o "No restringida o recursivamente enumerables"

“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 estetipo 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énson denominados "recursivamente enumerables"
Las máquinas que los aceptan son las máquinas de Turing (y equivalentes no deterministas)
[editar] Tipo 1 o "Sensible al contexto"

“α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...