Resumen de lenguajes formales (gramática libre de contexto versus gramática regular)

La teoría del lenguaje formal es el estudio matemático de la sintaxis de los lenguajes naturales y los lenguajes artificiales (como los lenguajes de programación). Sólo estudia las reglas que componen el lenguaje, no su significado. La teoría del lenguaje formal tiene amplias aplicaciones en la comprensión y traducción del lenguaje natural, la descripción y compilación de lenguajes informáticos, la simulación de fenómenos sociales y naturales y el reconocimiento de patrones guiado por la gramática.

La gramática formal se define estrictamente como el cuaternión G = (N, T, P, S).

Según las características de generar a → β en P, la gramática formal. y su La clasificación del lenguaje formal generada constituye el llamado espectro del lenguaje formal. En la teoría del lenguaje formal, estudiamos principalmente cuatro tipos de gramática y lenguajes:

Los cuatro tipos de lenguajes definidos anteriormente tienen relaciones de implicación secuencial, es decir, para i=0, 1, 2, cuando el No se considera una cadena vacía, un lenguaje de tipo i implica un lenguaje de tipo i+1.

Toda gramática libre de contexto que no produce una cadena vacía se puede transformar en una forma normal equivalente de Chomsky o Graybach. Aquí, la equivalencia de dos gramáticas significa que generan el mismo lenguaje.

Dado que el paradigma chomskyano tiene una forma muy simple, tiene aplicaciones tanto teóricas como prácticas. Por ejemplo, para cada lenguaje libre de contexto, podemos usar la forma normal de Chomsky para construir un algoritmo polinomial para determinar si una cadena dada pertenece a ese lenguaje (algoritmo CKY [Restricción: P satisface la forma normal base de Chomsky], algoritmo gráfico [generalizando CKY algoritmo a todos los CFG]).

La diferencia importante entre las definiciones regulares y las gramáticas libres de contexto es que las definiciones recursivas no están permitidas en las definiciones regulares. Por ejemplo, A → aA|b no es una definición regular, donde el lado izquierdo de A debe hacerlo. ser un nuevo símbolo, es decir, no se puede definir en ningún otro lugar, pero el lado derecho de la definición requiere que cada símbolo esté definido, por lo que esta definición no puede satisfacerlo. La gramática libre de contexto no tiene esta restricción, por lo que A → aA|b es una fórmula generativa para la gramática libre de contexto, pero no es una definición de una definición regular.

Las expresiones regulares se utilizan comúnmente para el análisis léxico en compilaciones y para identificar sintaxis más complejas mediante NFA, DFA y otros algoritmos.

PPT1

PPT2