Teorema de Parikh

Introducción:
el teorema de Parikh en informática teórica dice que si uno mira solo el número de ocurrencias de cada símbolo terminal en un lenguaje libre de contexto, sin tener en cuenta su orden, entonces el lenguaje es indistinguible de un lenguaje regular. Es útil para decidir que las strings con un número dado de terminales no son aceptadas por la gramática libre de contexto. Rohit Parikh lo probó por primera vez en 1961 y lo volvió a publicar en 1966.

 Teorema: el
“ teorema de Parikh ” establece que la imagen de Parikh de un idioma libre de contexto es semilineal o, de manera equivalente, que cada idioma libre de contexto tiene la misma imagen de Parikh que algún idioma regular. Presentamos una construcción muy simple que, dada una gramática libre de contexto, produce un autómata finito que reconoce un lenguaje tan regular.
Se utiliza una forma reforzada del lema de bombeo para lenguajes libres de contexto para dar una prueba simple del teorema de Parikh.

1. Imagen Parij –

• Si w es una palabra sobre algún Σ, denotamos por Π _∑ (w) la imagen Parikh de w sobre el alfabeto Σ.
• Π _∑ (w) asigna un carácter en Σ a su número de ocurrencias en w .
• La imagen Parikh de una lengua L sobre Σ es {Π _∑ (w)|w ∈ L}. Se denota por Π _∑ (L).

   Ejemplos –

1. Π _{a,b,c} (bccba) = (1, 2, 2) donde (1, 2, 2) representa {(a, 1),(b, 2),(c, 2)}.
2. Π _{a,b,c} (cabaaabb) = (4, 3, 1).

2. Derivación –
Sea ∑={a1,a2,…,ak} un alfabeto. El vector Parikh de una palabra se define como la función p: ∑* -> N ^k , dada por p(w) = (|w| _a1, |w| _a2, …, |w| _k) donde |w| _ai denota el número de ocurrencias de la letra a _i   en la palabra w.

• Declaración 1 – 
  Sea L un lenguaje libre de contexto. Sea P(L) el conjunto de vectores Parikh de palabras en L , es decir, P(L)={p(w) | w ∈ L} . Entonces P(L) es un conjunto semilineal.
  Conjuntos semilineales = subconjuntos definibles por Presburger de N ^k .
  Se dice que dos idiomas son conmutativamente equivalentes si tienen el mismo conjunto de vectores Parikh.
• Declaración 2: 
  si S es cualquier conjunto semilineal, el lenguaje de las palabras cuyos vectores Parikh están en S es conmutativamente equivalente a algún lenguaje regular. Así, todo lenguaje libre de contexto es conmutativamente equivalente a algún lenguaje regular.
  Estos dos enunciados equivalentes se pueden resumir diciendo que la imagen bajo p de lenguajes libres de contexto y de lenguajes regulares es la misma, y ​​es igual al conjunto de conjuntos semilineales.

Para lenguajes limitados:
un lenguaje L está limitado si L es un subconjunto de w1*……..wk* para algunas palabras fijas w1,….., wk. Ginsburg y Spanier dieron una condición necesaria y suficiente, similar al teorema de Parikh, para lenguajes acotados.
El teorema de Ginsburg-Spanier dice que un lenguaje acotado L es independiente del contexto si y solo si {(n1,…….,nk) | w1n1…… wknk ∈ L} es un conjunto semilineal estratificado.

Ejemplo –

• Lenguaje libre de contexto (CFL) L = {0 ^norte 1 ^norte | n>=1}
  Número de 0 (N ₀ ) = n 
  Número de 1 (N ₁ ) = n
  N ₀ = N ₁
  Sea la string w = ‘000111’ Aquí, N ₀  = 3 N ₁  = 3. Entonces, N ₀ = N ₁ y por lo tanto, w ∈ L y esta string satisface una de las propiedades de un lenguaje libre de contexto.
  El teorema de Parikh se trata de contar la aparición de todos y cada uno de los símbolos de entrada en la string dada y aquí calculamos no. de 0 y no. de 1s.
  El vector Parikh se puede definir para esta string en particular con el no. de 0(|w|₀ ) y 1(|w| ₁ ) en la string. 
  P(w) = {|w| ₀ , |w| ₁ } 

Vector parij:
P(‘000111’) = {3, 3}

• Aquí hay otro ejemplo. Sea, L = {0 ^norte 1 ^norte | n<3, n>=1}. Los posibles valores de n son 1 y 2.
  Para n = 1, la string es ’01’ y para n = 2, una string es ‘0011’.

El vector Parikh se puede definir para esta string en particular con el no. de 0(|w| ₀ ) y 1(|w| ₁ ) en la string.
P(w) = {|w| ₀ , |w| ₁ } 
Entonces, P(’01’) = {1, 1}
y similarmente, P(‘0011’) = {2, 2}
P(L) es el conjunto de vectores Parikh de palabras en L .
Entonces, aquí P(L) = { P(’01’) , P(‘0011’) } = { {1,1}, {2,2} }
A medida que obtenemos el conjunto de vectores Parikh del idioma dado, por lo que la string que pertenece al idioma dado es finita y podemos construir fácilmente el DFA para el idioma dado, es decir, un equivalente conmutativo a algún idioma regular. 

Algunos corolarios:

• Cada CFL es «equivalente a una letra» de un idioma normal .
  Por ejemplo: ψ({a ⁿ b ⁿ | n ≥ 0}) = ψ((ab) ^* ).
• Las longitudes de una CFL forman un conjunto periódico en última instancia.
• Las lámparas fluorescentes compactas sobre un alfabeto de una sola letra son regulares.
• Es útil para decidir que las strings con un número dado de terminales no son aceptadas por la gramática libre de contexto.

Importancia:
El teorema tiene múltiples interpretaciones. Muestra que un idioma libre de contexto sobre un alfabeto singleton debe ser un idioma regular y que algunos idiomas libres de contexto solo pueden tener una gramática ambigua. Estos lenguajes se denominan lenguajes inherentemente ambiguos. Desde una perspectiva de gramática formal, esto significa que algunas gramáticas libres de contexto ambiguas no se pueden convertir en gramáticas libres de contexto no ambiguas equivalentes.