¿Qué es Gramática aleatoria?

Asigne un cierto valor de probabilidad a cada producción gramatical (regla de reescritura) para describir la gramática de patrones aleatorios. El lenguaje generado por la gramática aleatoria se llama lenguaje aleatorio, y el autómata que acepta el lenguaje aleatorio se llama autómata aleatorio.

El ruido y la interferencia existen inevitablemente en problemas como la comunicación, el almacenamiento y recuperación de información y la medición y procesamiento de patrones físicos, por lo que el lenguaje utilizado para describir patrones tiene un carácter aleatorio. Para representar matemáticamente la incertidumbre y la aleatoriedad del lenguaje L , la medida de probabilidad p _ij se puede introducir en la producción gramatical , a saber, Y.

Suponga que la cadena x se deriva del símbolo de inicio s usando la secuencia de producción r ₁ , r ₂ , ..., r _m , y las probabilidades asociadas con las producciones r ₁ , ..., r _m son p ( r ₁ ), p ( r ₂ ), ..., p ( r _m ), cuando la probabilidad p ( r _i ) ( i = 1, ..., m ) no depende de la producción utilizada en el proceso de derivación anterior, use la secuencia anterior para derivar La probabilidad de la oración x es

Cuando hay k secuencias de producción diferentes para la misma x , la probabilidad derivada de la oración x es la suma de las probabilidades derivadas de cada secuencia. Similar al clasificador bayesiano en los métodos estadísticos, cuando la misma cadena es producida por más de dos gramáticas, la gramática que puede obtener la máxima probabilidad derivada de x se usa como descripción sintáctica de la cadena.

De acuerdo con las diferentes condiciones de restricción de _{i j} en la gramática de la estructura de la frase, existen tipos correspondientes 0 (sin restricciones), tipo 1 (sensible al contexto), tipo 2 (sin contexto) y tipo 3 (estado limitado). .

Un problema teórico importante en la gramática aleatoria es determinar la condición de consistencia, es decir, la condición de que la suma de las probabilidades derivadas de todas las oraciones producidas por la gramática sea igual a 1.

Para la forma de producción(A, B son símbolos no terminales, u, v son símbolos terminales) La condición de consistencia de la gramática lineal y la gramática aleatoria libre de contexto se puede determinar utilizando el proceso de Markov de estado finito y la teoría de la bifurcación de Galton-Watson, respectivamente. El problema de coherencia de la gramática aleatoria sensible al contexto aún no se ha resuelto.

Cuando el concepto de aleatoriedad se aplica a la gramática aleatoria de alta dimensión, se obtiene la gramática de árbol aleatorio y el lenguaje de árbol aleatorio correspondiente, la gramática de gráfico aleatorio y el lenguaje de gráfico aleatorio correspondiente. Esta gramática y lenguaje aleatorio de alta dimensión puede describir con eficacia patrones más complejos con ruido y distorsión.