Lenguajes Formales

República Bolivariana de Venezuela
Universidad Fermín Toro
Facultad de Ingeniería














LENGUAJES FORMALES














Alumno:Cabudare, Julio de 2.013
Las gramáticas han sido clasificadas de acuerdo a particularidades y restricciones propias, una de ellas y la más acertada es la formula dada por Noam Chomsky, quienclasificó las gramáticas, dando origen a la Jerarquía de Chomsky en función de la forma de reglas de derivación o producción.

Características de Los Tipos de Gramáticas

Gramáticas RegularesGramáticas Sensibles al Contexto
Gramáticas Independientes del Contexto(GIC)
-Genera cadenas a partir de una cadena vacía.
-Las cadenas que puede generar el autómata son todas aquellas quepertenecen al lenguaje representado por el autómata L(M).
-Todas las cadenas inician con una „a‟, luego viene una serie de a‟s o b‟s y finalmente termina con una b‟.



-Es importantetomar en cuenta la ubicación de los símbolos no terminales en la regla de derivación (que preceden y suceden a cada símbolo Terminal.
-Deben mantener su ubicación en el lado derecho de la regla deproducción.
-Se caracteriza porque las partes Izquierdas y Derechas tienen que tener una parte común y se admite como regla compresora la regla S→ε.

-Es una cuádrupla G = (N, ∑ , S, P), donde:N: es una colección finita (no vacía) de símbolos no terminales.
∑: es un alfabeto.
S: es un no terminal llamado símbolo inicial.
P: un conjunto de producciones.




Ejemplo deGramática Regular:
Por ejemplo las siguientes gramáticas G1 y G2, son gramáticas regulares lineales a derecha y lineales a izquierda respectivamente, que generan el lenguaje L = {a2n / n ≥ 0}
G1= ({A, B}, {a}, P1, S1) G2 = ({C, D}, {a}, P2, S2)
Donde P1 es el cjto. Donde P2 es el cjto.
S1 → ε...