Parikhsova věta - Parikhs theorem - Wikipedia

Parikhova věta v teoretická informatika říká, že když se člověk podívá jen na počet výskytů každého z nich symbol terminálu v bezkontextový jazyk, bez ohledu na jejich pořadí, je jazyk nerozeznatelný od a běžný jazyk.^[1] Je užitečné se rozhodnout, že řetězce s daným počtem terminálů nebudou bezkontextovou gramatikou přijímány.^[2] Poprvé to prokázal Rohit Parikh v roce 1961^[3] a znovu publikovány v roce 1966.^[4]

Definice a formální prohlášení

Nechat ${ displaystyle Sigma = {a_ {1}, a_ {2}, ldots, a_ {k} }}$ být abeceda. The Parikh vektor slova je definována jako funkce ${ textstyle p: Sigma ^ {*} to mathbb {N} ^ {k}}$, dána^[1]

kde ${ displaystyle | w | _ {a_ {i}}}$ označuje počet výskytů písmene ${ displaystyle a_ {i}}$ ve slově ${ displaystyle w}$.

Podmnožina ${ displaystyle mathbb {N} ^ {k}}$ se říká, že je lineární pokud je ve formě

pro některé vektory ${ textstyle u_ {0}, ldots, u_ {m}}$Podskupina ${ displaystyle mathbb {N} ^ {k}}$ se říká, že je pololineární pokud se jedná o spojení konečně mnoha lineárních podmnožin.

Prohlášení 1: Nechte ${ displaystyle L}$ být bezkontextovým jazykem ${ displaystyle P (L)}$ být množinou Parikhových vektorů slov v ${ displaystyle L}$, to znamená, ${ textový styl P (L) = {p (w) střední w v L }}$. Pak ${ displaystyle P (L)}$ je pololineární množina.

Říká se, že jsou dva jazyky komutativně ekvivalentní pokud mají stejnou sadu Parikhových vektorů.

Prohlášení 2: Pokud ${ displaystyle S}$ je libovolná pololineární množina, jazyk slov, v nichž jsou Parikh vektory ${ displaystyle S}$ je komutativně ekvivalentní k nějakému běžnému jazyku. Každý bezkontextový jazyk je tedy komutativně ekvivalentní nějakému běžnému jazyku.

Tyto dva ekvivalentní výroky lze shrnout slovy, že obrázek pod ${ displaystyle p}$ bezkontextových jazyků a regulárních jazyků je stejné a rovná se množině semilineárních množin.

Posílení pro ohraničené jazyky

Jazyk ${ displaystyle L}$ je ohraničený -li ${ displaystyle L podmnožina w_ {1} ^ {*} ldots w_ {k} ^ {*}}$ pro některá pevná slova ${ displaystyle w_ {1}, ldots, w_ {k}}$Ginsburg a Spanier ^[5]dal nezbytnou a dostatečnou podmínku, podobně jako Parikhova věta, pro ohraničené jazyky.

Zavolej lineární množinu rozvrstvené, pokud je ve své definici pro každého ${ displaystyle i geq 1}$ vektor ${ displaystyle u_ {i}}$ má vlastnost, že má nanejvýš dvě nenulové souřadnice a pro každou ${ displaystyle i, j geq 1}$ pokud každý z vektorů ${ displaystyle u_ {i}, u_ {j}}$ má dvě nenulové souřadnice, ${ displaystyle i_ {1}$ a ${ displaystyle j_ {1}$jejich pořadí je ne ${ displaystyle i_ {1}$.Semi-lineární množina je stratifikována, pokud se jedná o unii konečně mnoha stratifikovaných lineárních podmnožin.

Ginsburg-Spanierova věta říká, že ohraničený jazyk ${ displaystyle L}$ je bezkontextový právě tehdy ${ displaystyle {(n_ {1}, ldots, n_ {k}) mid w_ {1} ^ {n_ {1}} ldots w_ {k} ^ {n_ {k}} v L } }$ je stratifikovaná pololineární množina.

Význam

Věta má několik interpretací. Ukazuje, že bezkontextovým jazykem nad singletonovou abecedou musí být a běžný jazyk a které mohou mít pouze některé bezkontextové jazyky dvojznačné gramatiky^{[je třeba další vysvětlení ]}. Takovým jazykům se říká neodmyslitelně nejednoznačné jazyky. Od a formální gramatika perspektiva, to znamená, že některé nejednoznačné bezkontextové gramatiky nelze převést na ekvivalentní jednoznačné bezkontextové gramatiky.

Reference