Clasificacion De Las Gramaticas

Noam Chomsky, en la clasificación de los Lenguajes y Gramáticas, estableciéndose a continuación los correspondientes autómatas, de manera que:

Se desarrollan los lenguajes tipo 3, generados por las gramáticas tipo 3, lineales izquierdas o derechas, ambas equivalentes, y que se corresponden con los CONJUNTOS REGULARES, dados por las EXPRESIONES REGULARES, capaces de simbolizar conjuntos infinitos mediante especificaciones finitas; a estos lenguajes les corresponden cierto tipo de autómatas, deterministas y no deterministas – equivalentes ambos – con los que se es capaz de resolver ciertos problemas de índole menor desde el punto de vista matemático. Los lenguajes tipo 2 siguen a los anteriores y son generados por las gramáticas tipo 2, “INDEPENDIENTES DEL CONTEXTO” que resuelven problemas de mayor envergadura, y se corresponden con los “AUTÓMATAS A PILA”, que a diferencia de los anteriores necesitan de una pila de memoria adicional. Se sigue con los lenguajes tipo1, “ DEPENDIENTES DEL CONTEXTO” a cuyas gramáticas generativas se les exige menos restricciones, y que se corresponden con los autómatas acotados linealmente. Por último Se desarrollan los lenguajes tipo 0, generados por las gramaticas tipo 0 “SIN RESTRICCIONES” isomórficas con las “MÁQUINAS DE TURING”, que resuelven problemas recursivamente enumerables. Se describen brevemente algunos problemas “no enumerables” que las máquinas deTuring no son capaces de resolver. Se finaliza el temario con una breve descripción de “LAS REDES DE NEURONAS”, autómatas capaces de simular – en alguna medida – el comportamiento del sistema neuronal humano.

CLASIFICAION DE LAS GRAMATICAS

1. SEA ∑={a, b } V={S, M}

P: S → asa

	S → Ma
       aS → b

Es una gramática tipo 0 pues la longitud del extremo izquierdo en la ultima regla es 2 y del derecho es 1.

2. SEA ∑= {a, b} V= {S, M, N}

	P:	 S → Ma
		 M → aM
                 M → b
		 M→ bN
                 N → a 

Es una gramática tipo 2, pues el elemento izquierdo de toda regla de producción es una variable. No es tipo 3 por que en la regla S → Ma, M no esta al final.

3. SEA ∑= {a, b, c} V= {S}

	P:	 S → aSa
		aS → bc

Es una gramática tipo 1 pues la longitud de los términos a la izquierda es menor ó igual a la derecha. Pero no es de tipo 2 pues aS → bc la expresión de la izquierdazo es variable.