Twierdzenie Parikha

Twierdzenie Parikha w informatyce teoretycznej mówi, że jeśli spojrzy się tylko na liczbę wystąpień każdego symbolu końcowego w języku bezkontekstowym , bez względu na ich kolejność, to język ten jest nie do odróżnienia od zwykłego języka . Jest to przydatne do decydowania, że ​​ciągi z określoną liczbą końcówek nie są akceptowane przez gramatykę bezkontekstową. Zostało to po raz pierwszy udowodnione przez Rohita Parikha w 1961 roku i ponownie opublikowane w 1966 roku.

Definicje i oświadczenie formalne

Niech ${\ Displaystyle \ Sigma = \ {a_ {1}, a_ {2}, \ ldots, a_ {k} \}}$ będzie alfabetem . Wektor Parikh słowa jest zdefiniowany jako funkcja ${\ textstyle p: \ Sigma ^ {*} \ to \ mathbb {N} ^ {k}}$ , dana przez

$${\ Displaystyle p (w) = (| w|_ {a_ {1}}, | w|_ {a_{2}},\ldkropki ,|w|_{a_{k}})}$$

gdzie ${\ displaystyle | w | _ {a_ {i}}}$ oznacza liczbę wystąpień litery w słowie ${\ displaystyle a_ {i}}$${\ displaystyle w}$ .

O podzbiorze mówi się, że jest liniowy , jeśli ma postać ${\ displaystyle \ mathbb {N} ^ {k}}$

$${\ Displaystyle u_ {0} + \ mathbb {N} u_{1}+\kropki +\mathbb {N} u_{m}=\{u_{0}+t_{1}u_{1}+\kropki +t_{m}u_{m}\mid t_{1 },\ldots ,t_{m}\w \mathbb {N} \}}$$

dla niektórych wektorów ${\ textstyle u_ {0}, \ ldots, u_ {m}}$ . Mówi się $, że$ podzbiór jest półliniowy, jeśli jest sumą skończenie wielu podzbiorów liniowych

Twierdzenie - Niech będzie $językiem$ bezkontekstowym lub językiem regularnym, niech $L}$ zbiorem wektorów Parikh słów w $displaystyle L}$ że L { jest ${\ textstyle P (L) = \ {p (w) \ mid w \ in L \}}$ . następnie ${\ displaystyle P (L)}$ jest zbiorem półliniowym.

Jeśli jest jakimkolwiek $zbiorem$ półliniowym, to istnieje język regularny (który a fortiori jest bezkontekstowy), którego wektorami Parikh jest $\ displaystyle S}$ .

Krótko mówiąc, obraz pod $bezkontekstowymi$ i językami regularnymi jest taki sam i jest równy zbiorowi zbiorów półliniowych.

Mówi się, że dwa języki są przemiennie równoważne , jeśli mają ten sam zestaw wektorów Parikh. Zatem każdy język bezkontekstowy jest przemiennie odpowiednikiem jakiegoś języka regularnego.

Dowód

Druga część jest łatwa do udowodnienia.

Dowód

$S$ półliniowy , aby skonstruować język regularny, którego zestaw wektorów Parikh to $\ displaystyle S}$ .

${\ displaystyle S}$ to suma 0 lub więcej zestawów liniowych. Ponieważ język pusty jest regularny, a suma języków regularnych jest regularna, wystarczy udowodnić, że dowolny zbiór liniowy jest zbiorem wektorów Parikh języka regularnego.

Niech ${\ Displaystyle S = \ {u_ {0} + t_ {1} u_ {1} + \ dots +t_{m}u_{m}\mid t_{1},\ldots ,t_{m}\in \mathbb {N} \}} , to jest to zbiór wektorów$ Parikha ${\ Displaystyle \ {z_ {0} \} \ cdot (\ kubek _ {i = 1} ^ {m} \ {z_ {i} \}) ^ {*}} , gdzie każdy$ z $\ displaystyle z_ {i}}$ ma wektor Parikh ${\ displaystyle u_ {i}}$ .

Pierwsza część jest mniej łatwa. Przypisuje się następujący dowód.

Najpierw potrzebujemy małego wzmocnienia lematu o pompowaniu dla języków bezkontekstowych :

Lemat - Jeśli jest $generowany$ przez gramatykę postaci normalnej Chomsky'ego, to ${\ Displaystyle \ istnieje N \ geq 1}$ tak, że L {

Dla każdego i dla dowolnego $Displaystyle k \$$1}$${\ Displaystyle | w | \ geq N ^ {k}}$ z , istnieje sposób na podzielenie $\$ segmenty $displaystyle ux_ { 1}\cdots x_{k}zy_{k}\cdots y_{1}v}$ i nieterminalny symbol taki, że ${\ displaystyle A}$

$i} | \ geq 1}$${\ Displaystyle | x_ {1} \ cdots x_ {k} zy_ {k} \ cdots y_ {1} | \ równoważnik N ^ {k}}$$dla$ wszystkich |

$${\ Displaystyle S \ Strzałka w prawo ^ {*} uAv \ quad A \ Strzałka w prawo ^ {*} z \ quad \ dla wszystkich ja, A \ Strzałka w prawo ^{*}x_{i}Ay_{i}}$$

Dowód jest zasadniczo taki sam, jak standardowy lemat o pompowaniu: użyj zasady przegródki, aby znaleźć $kopie$$jakiegoś$ na najdłuższej ścieżce w najkrótszym drzewie derywacyjnym.

Dowód

Najpierw skonstruuj gramatykę postaci normalnej Chomsky'ego dla ${\ displaystyle L}$ .

Dla każdego skończonego niepustego podzbioru nieterminali zdefiniuj zbiór zdań w taki, że istnieje wyprowadzenie, które wykorzystuje każdy nieterminal w ${\ Displaystyle U}$$L_ {$${\ displaystyle$$}$ , nie więcej i nie mniej. Jest oczywiste, że ${\ Displaystyle L = \ kubek _ {U} L_ {U}}$ , więc wystarczy udowodnić, że każdy ${\ displaystyle p (L_ {U})}$ jest zbiorem półliniowym.

Teraz napraw ${\ displaystyle k = | U |}$$k$ niech . Konstruujemy dwa skończone zbiory takie, że $fa$$Displaystyle p (L_ {U}) = p (F \ cdot$ , co jest oczywiście półliniowe.

Dla jasności notacji napisz, $oznaczać$ „istnieje wyprowadzenie używające nie więcej (ale prawdopodobnie mniej) niż nieterminali $Z$ , definiujemy następująco: ${\ Displaystyle F, G}$

$${\ Displaystyle F = \ {w \ w L_ {U}:| w | <N ^ {k} \}}$$

$${\ Displaystyle G = \ {xy: 1 \ równoważnik | xy | \ równoważnik N ^ {k} {\ tekst {i istnieje}} A\w U{\text{ takie, że }}A\Rightarrow _{U}^{*}xAy\}}$$

Aby udowodnić ${\ Displaystyle p (L_ {U}) \ podzbiór p (F \ cdot G ^ {*})}$ , indukujemy na długości ${\ displaystyle w \ w L_ {U}}$ .

Jeśli ${\ Displaystyle | w | <N ^ {k}}$ , potem ${\ Displaystyle w \ in F}$ , więc ${\ Displaystyle p (w) \in p(F\cdot G^{*})}$ . $displaystyle U}$ przeciwnym razie, na mocy lematu o wzmocnionym pompowaniu, istnieje wyprowadzenie przy użyciu dokładnie elementów $\$ , i ma postać

$${\ Displaystyle S {\ underset {d_ {0}} {\ stackrel {*} {\ Strzałka w prawo}}} uAv {\ underset {d_ {1}} {\ stackrel {*} {\ Strzałka w prawo }}}ux_{1}Ay_{1}v{\underset {d_{2}}{\stackrel {*}{\strzałka w prawo}}}\cdots {\underset {d_{k}}{\stackrel {*} {\Strzałka w prawo}}}ux_{1}\cdots x_{k}Ay_{k}\cdots y_{1}v{\underset {d_{k+1}}{\stackrel {*}{\Strzałka w prawo}}} ux_{1}\cdots x_{k}zy_{k}\cdots y_{1}v}$$

gdzie ${\ Displaystyle A \ w U}$ , ${\ Displaystyle 1 \ równoważnik | x_ {i} y_ {i} |}$ i ${\ Displaystyle | x_ {1} \ cdots x_ {k} zy_ {k} \ cdots y_ {1} | \ równoważnik N ^ {k}}$ .

Ponieważ są tylko elementy ${\ displaystyle k-1}$$U \ setminus \ {A \}}$$pochodne$ , ale istnieją sub- $d_ {1}, ..., d_ {k}}$$Displaystyle$ w środku, możemy usunąć jedno wyprowadzenie podrzędne krótsze $\ displaystyle w'}$ , który nadal jest w ${\ displaystyle L_ {U}}$ z

$${\ Displaystyle p (w) =p(uzv)+p(x_{1}y_{1})+\cdots +p(x_{k}y_{k})=p(w')+p(x_{i}y_{i}) }$$

${\ Displaystyle p (w ') \ in p (F \ cdot G ^ {*})}$ ∗ i przez ${ \ Displaystyle x_ {i} y_ {i} \ w G}$ , więc ${\ Displaystyle p (w) \ w p (F \ cdot G ^ {*})}$ .

Aby udowodnić ${\ Displaystyle p (L_ {U}) \ supset p (F \ cdot G ^ {*})}$ , indukujemy na długości ${\ Displaystyle w \ w F \ cdot G ^ {*}}$ .

Jeśli ${\ Displaystyle | w | <N ^ {k}}$ następnie przez konstrukcję, ${\ Displaystyle w \ w F \ podzbiór L_ {U}}$ .

$= w'xy}$ w dla niektórych ${\ Displaystyle w'\ in F \ cdot G ^ {*}}$ i ${\ displaystyle xy \ w G}$ .

Przez indukcję ${\ Displaystyle p (w') = p (w'')}$ dla niektórych ${\ Displaystyle w''\ w L_ {U}}$ . Dzięki konstrukcji istnieje pewne takie, że ${\ Displaystyle A \ w U$$}$${\ Displaystyle A \ Strzałka w prawo _ {U} ^ {*} xAy}$ .

Dzięki konstrukcji $dokładnie$ symbol pojawia się $displaystyle$ wyprowadzeniu przy użyciu wszystkich $}$$.$ Następnie możemy interpolować do tego wyprowadzenia, aby uzyskać trochę takie, że ${\ displaystyle w'''\ in L_ {U}}$${\ Displaystyle A \ Rightarrow _ {U} ^ {*} x Ay}$

$${\ Displaystyle p (w''') = p (w'' )+p(xy)=p(w')+p(xy)=p(w)}$$

Wzmocnienie dla języków ograniczonych

Język jest ograniczony , jeśli $\$$Displaystyle L \ podzbiór w_ {1} ^ {*} \ ldots w_ {k} ^ {*}}$ niektórych ustalonych słów ${\ Displaystyle w_ {1}, \ ldots, w_ {k}}$ . Ginsburg i Spanier podali warunek konieczny i wystarczający, podobny do twierdzenia Parikha, dla języków ograniczonych.

Nazwij zbiór liniowy warstwowy , jeśli w swojej definicji dla każdego wektor ma tę $u$ że ma co najwyżej dwie niezerowe współrzędne i $}$ dla każdego ${\ Displaystyle i, j \ geq 1} , jeśli$$}}$ wektorów ma dwie niezerowe współrzędne ${\ Displaystyle i_ {1}<i_ {2}}$ i ${\ Displaystyle j_ {1}<j_ {2}}$ odpowiednio, to ich kolejność nie jest ${\ Displaystyle i_ {1}<j_ {1}<i_ {2}<j_ {2}}$ . Zbiór półliniowy jest warstwowy, jeśli jest sumą skończenie wielu warstwowych podzbiorów liniowych.

Ginsburg-Spanier - Język ograniczony $jest$ bezkontekstowy wtedy i tylko wtedy, gdy $\ Displaystyle \ {(( n_{1},\ldots ,n_{k})\mid w_{1}^{n_{1}}\ldots w_{k}^{n_{k}}\in L\}} jest uwarstwionym$ pół- zestaw liniowy.

Znaczenie

Twierdzenie ma wiele interpretacji. Pokazuje, że język bezkontekstowy nad alfabetem singletonowym musi być językiem regularnym i że niektóre języki bezkontekstowe mogą mieć tylko niejednoznaczne gramatyki . Takie języki nazywane są językami z natury niejednoznacznymi . Z formalnego punktu widzenia gramatyki oznacza to, że niektórych niejednoznacznych gramatyk bezkontekstowych nie można przekształcić w równoważne, jednoznaczne gramatyki bezkontekstowe.