Clasificación de los lenguajes formales
Páginas: 7 (1727 palabras)
Publicado: 5 de marzo de 2010
CLASIFICACIÓN DE LOS LENGUAJES FORMALES
Desde mucho tiempo atrás era muy complicado poder agrupar los tipos de lenguajes formales existentes por lo que pensar en una clasificación era complicada pero en 1956 Noam Chomsky propuso una clasificación hasta el día de hoy vigente conocida como la jerarquía de Chomsky la cual es una clasificación jerárquica de distintos tipos de gramáticas formalesque generan lenguajes formales.
La Jerarquía de Chomsky consta de cuatro niveles:
Gramáticas de tipo 0 (sin restricciones): Que incluye a todas las gramáticas formales. Estas gramáticas generan todos los lenguajes capaces de ser reconocidos por una máquina de Turing, son los que dan lugar a los lenguajes son conocidos como lenguajes recursivamente enumerables. Estos puede iterar indefinidamentehasta reconocer o no una cadena de entrada, rechazándola o aceptándola, contienen reglas que transforman un número arbitrario de símbolos no vacío en otro número arbitrario, posiblemente vacío, de símbolos.
aAB -> a
bB -> aBC
También llamadas gramáticas no restringidas con estructura de frase. Se caracterizan:
* Porque en sus producciones no se establece ningún tipo de restricciónrespecto a su formato.
* En la parte izquierda tiene que haber al menos un símbolo no terminal.
* Respecto a sus partes derechas de producciones no hay ningún tipo de restricción.
* Pueden tener reglas compresoras.
Gramáticas de tipo 1 (gramáticas sensibles o dependientes al contexto): Generan los lenguajes sensibles al contexto. Contienen reglas de producción de la forma:
a A bà a g b
* A es un no terminal
* a, b y g son cadenas de terminales y no terminales.
* a y b pueden ser vacíos, pero g ha de ser distinto del vacío.
Se denominan gramáticas dependientes del contexto, porque, como se observa, A puede ser sustituido por g si está acompañada de a por la izquierda y de b por la derecha.
La regla está permitida si S no aparece en la parte derecha de ningunaregla.
Los lenguajes descritos por estas gramáticas son exactamente todos aquellos lenguajes reconocidos por una máquina de Turing determinista cuya cinta de memoria está acotada por un cierto número entero de veces sobre la longitud de entrada, también conocidas como autómatas linealmente acotados. En este tipo de gramáticas no existen reglas compresoras, salvo, opcionalmente, la que deriva el axiomaa la palabra vacía, en estas existen reglas en las que un símbolo no terminal puede derivar a formas senténciales distintas, según los símbolos que aparezcan a su alrededor, una regla es sensible al contexto si solo un símbolo no terminal en el lado izquierdo se reemplaza por otro símbolo mientras el resto permanece inalterado y en el mismo orden.
bQc -> bbcc
o la gramática que genera elmismo número de a, b, c:
Ss -> abc | aSQ
bQc -> bbcc
cQ -> Qc
Gramáticas de tipo 2 (gramáticas libres o independientes del contexto): Generan los lenguajes independientes del contexto. Generan los lenguajes libres de contexto. Están definidas por reglas de la forma:
A à g
* A es un no terminal
* g es una cadena de terminales y no terminales.
Se denominan independientes decontexto porque “A” puede sustituirse por “g” independientemente de las cadenas por las que esté acompañada. Los lenguajes independientes de contexto constituyen la base teórica para la sintaxis de la mayoría de los lenguajes de programación. Definen la sintaxis de las declaraciones, las proposiciones, las expresiones, etc. (es decir, la estructura de un programa), y pueden ser reconocidos por losautómatas de pila.
Estos lenguajes se caracterizan:
* Mayor capacidad para especificar lenguajes al incluir algunos lenguajes que no son reconocidos por un autómata finito.
* Son útiles para describir expresiones que tengan una anidación arbitraria o estructuras en bloque.
* si en el lado izquierdo de cada producción es un único símbolo no terminal y el lado derecho consta de uno o...
Desde mucho tiempo atrás era muy complicado poder agrupar los tipos de lenguajes formales existentes por lo que pensar en una clasificación era complicada pero en 1956 Noam Chomsky propuso una clasificación hasta el día de hoy vigente conocida como la jerarquía de Chomsky la cual es una clasificación jerárquica de distintos tipos de gramáticas formalesque generan lenguajes formales.
La Jerarquía de Chomsky consta de cuatro niveles:
Gramáticas de tipo 0 (sin restricciones): Que incluye a todas las gramáticas formales. Estas gramáticas generan todos los lenguajes capaces de ser reconocidos por una máquina de Turing, son los que dan lugar a los lenguajes son conocidos como lenguajes recursivamente enumerables. Estos puede iterar indefinidamentehasta reconocer o no una cadena de entrada, rechazándola o aceptándola, contienen reglas que transforman un número arbitrario de símbolos no vacío en otro número arbitrario, posiblemente vacío, de símbolos.
aAB -> a
bB -> aBC
También llamadas gramáticas no restringidas con estructura de frase. Se caracterizan:
* Porque en sus producciones no se establece ningún tipo de restricciónrespecto a su formato.
* En la parte izquierda tiene que haber al menos un símbolo no terminal.
* Respecto a sus partes derechas de producciones no hay ningún tipo de restricción.
* Pueden tener reglas compresoras.
Gramáticas de tipo 1 (gramáticas sensibles o dependientes al contexto): Generan los lenguajes sensibles al contexto. Contienen reglas de producción de la forma:
a A bà a g b
* A es un no terminal
* a, b y g son cadenas de terminales y no terminales.
* a y b pueden ser vacíos, pero g ha de ser distinto del vacío.
Se denominan gramáticas dependientes del contexto, porque, como se observa, A puede ser sustituido por g si está acompañada de a por la izquierda y de b por la derecha.
La regla está permitida si S no aparece en la parte derecha de ningunaregla.
Los lenguajes descritos por estas gramáticas son exactamente todos aquellos lenguajes reconocidos por una máquina de Turing determinista cuya cinta de memoria está acotada por un cierto número entero de veces sobre la longitud de entrada, también conocidas como autómatas linealmente acotados. En este tipo de gramáticas no existen reglas compresoras, salvo, opcionalmente, la que deriva el axiomaa la palabra vacía, en estas existen reglas en las que un símbolo no terminal puede derivar a formas senténciales distintas, según los símbolos que aparezcan a su alrededor, una regla es sensible al contexto si solo un símbolo no terminal en el lado izquierdo se reemplaza por otro símbolo mientras el resto permanece inalterado y en el mismo orden.
bQc -> bbcc
o la gramática que genera elmismo número de a, b, c:
Ss -> abc | aSQ
bQc -> bbcc
cQ -> Qc
Gramáticas de tipo 2 (gramáticas libres o independientes del contexto): Generan los lenguajes independientes del contexto. Generan los lenguajes libres de contexto. Están definidas por reglas de la forma:
A à g
* A es un no terminal
* g es una cadena de terminales y no terminales.
Se denominan independientes decontexto porque “A” puede sustituirse por “g” independientemente de las cadenas por las que esté acompañada. Los lenguajes independientes de contexto constituyen la base teórica para la sintaxis de la mayoría de los lenguajes de programación. Definen la sintaxis de las declaraciones, las proposiciones, las expresiones, etc. (es decir, la estructura de un programa), y pueden ser reconocidos por losautómatas de pila.
Estos lenguajes se caracterizan:
* Mayor capacidad para especificar lenguajes al incluir algunos lenguajes que no son reconocidos por un autómata finito.
* Son útiles para describir expresiones que tengan una anidación arbitraria o estructuras en bloque.
* si en el lado izquierdo de cada producción es un único símbolo no terminal y el lado derecho consta de uno o...
Leer documento completo
Regístrate para leer el documento completo.