El teorema de Parikh en informática teórica dice que si uno mira solo el número de apariciones de cada símbolo terminal en un lenguaje sin contexto , sin tener en cuenta su orden, entonces el lenguaje es indistinguible de un lenguaje regular . [1] Es útil para decidir que las cadenas con un número determinado de terminales no son aceptadas por una gramática libre de contexto. [2] Fue probado por primera vez por Rohit Parikh en 1961 [3] y reeditado en 1966. [4]
Definiciones y declaración formal
Dejar ser un alfabeto . El vector Parikh de una palabra se define como la función, dado por [1]
Un subconjunto de se dice que es lineal si tiene la forma
Declaración 1 : Dejaser un lenguaje libre de contexto. Dejar ser el conjunto de Parikh vectores de palabras en , es decir, . Luego es un conjunto semilineal.
Se dice que dos lenguajes son conmutativamente equivalentes si tienen el mismo conjunto de vectores Parikh.
Declaración 2 : Si es cualquier conjunto semilineal, el lenguaje de palabras cuyos vectores Parikh están en es conmutativamente equivalente a algún lenguaje regular. Por tanto, todo lenguaje libre de contexto es conmutativamente equivalente a algún lenguaje regular.
Estas dos afirmaciones equivalentes se pueden resumir diciendo que la imagen debajo de lenguajes libres de contexto y de lenguajes regulares es el mismo, y es igual al conjunto de conjuntos semilineales.
Fortalecimiento de las lenguas limitadas
Un idioma está acotado si por algunas palabras fijas . Ginsburg y Spanier [5] dieron una condición necesaria y suficiente, similar al teorema de Parikh, para los lenguajes acotados.
Llame a un conjunto lineal estratificado , si en su definición para cada el vector tiene la propiedad de que tiene como máximo dos coordenadas distintas de cero, y para cada si cada uno de los vectores tiene dos coordenadas distintas de cero, y , respectivamente, entonces su orden no es . Un conjunto semilineal se estratifica si es una unión de un número finito de subconjuntos lineales estratificados.
El teorema de Ginsburg-Spanier dice que un lenguaje limitado es libre de contexto si y solo si es un conjunto semilineal estratificado.
Significado
El teorema tiene múltiples interpretaciones. Muestra que un lenguaje libre de contexto sobre un alfabeto singleton debe ser un lenguaje regular y que algunos lenguajes libres de contexto solo pueden tener gramáticas ambiguas [ se necesita más explicación ] . Estos lenguajes se denominan lenguajes intrínsecamente ambiguos . Desde una perspectiva de gramática formal , esto significa que algunas gramáticas ambiguas sin contexto no se pueden convertir en gramáticas equivalentes sin ambigüedades sin contexto.
Referencias
- ↑ a b Kozen, Dexter (1997). Autómatas y Computabilidad . Nueva York: Springer-Verlag. ISBN 3-540-78105-6.
- ^ Håkan Lindqvist. "Teorema de Parikh" (PDF) . Umeå Universitet.
- ^ Parikh, Rohit (1961). "Dispositivos de generación de lenguaje". Informe de progreso trimestral, Laboratorio de Investigación de Electrónica, MIT .
- ^ Parikh, Rohit (1966). "Sobre lenguajes libres de contexto" . Revista de la Asociación de Maquinaria Informática . 13 (4).
- ^ Ginsburg, Seymour; Spanier, Edwin H. (1966). "Fórmulas y lenguajes de Presburger" . Pacific Journal of Mathematics . 16 (2): 285-296.