Greibachova věta - Greibachs theorem - Wikipedia

v teoretická informatika, zejména v teorie formálního jazyka, Greibachova věta uvádí, že určité vlastnosti formální jazyk třídy jsou nerozhodnutelný. Je pojmenována po počítačovém vědci Sheila Greibachová, který to poprvé dokázal v roce 1963.^[1][2]

Definice

Vzhledem k množině Σ, často nazývané „abeceda“, (nekonečná) množina všech struny vytvořený z členů Σ je označen Σ^*.A formální jazyk je podmnožinou Σ^*.Li L₁ a L₂ jsou formální jazyky, jejich produkt L₁L₂ je definována jako množina { w₁w₂ : w₁ ∈ L₁, w₂ ∈ L₂ } ze všech zřetězení řetězce w₁ z L₁ s provázkem w₂ z L₂.Li L je formálním jazykem a A je symbol od Σ, jejich podíl L/A je definována jako množina { w : wa ∈ L } ze všech řetězců, z nichž lze vytvořit členy L připojením AZ teorie formálního jazyka jsou známy různé přístupy k označení formálního jazyka konečným popisem, například a formální gramatika nebo a konečný stavový stroj.

Například pomocí abecedy Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} bude sada Σ^* skládá se ze všech (desetinných reprezentací) přirozených čísel s povolenými úvodními nulami a prázdného řetězce označeného jako ε. L_div3 všech přirozených dělitelných dělitelností 3 je nekonečný formální jazyk nad Σ; lze to konečně popsat následujícím způsobem běžná gramatika s počáteční symbol S₀:

S0 →	ε |	0 S0	| 1 S2	| 2 S1	| 3 S0	| 4 S2	| 5 S1	| 6 S0	| 7 S2	| 8 S1	| 9 S0
S1 →		0 S1	| 1 S0	| 2 S2	| 3 S1	| 4 S0	| 5 S2	| 6 S1	| 7 S0	| 8 S2	| 9 S1
S2 →		0 S2	| 1 S1	| 2 S0	| 3 S2	| 4 S1	| 5 S0	| 6 S2	| 7 S1	| 8 S0	| 9 S2

Příklady konečných jazyků jsou {ε, 1,2} a {0,2,4,6,8}; jejich součin {ε, 1,2} {0,2,4,6,8} poskytuje sudá čísla až 28. Kvocient množiny prvočísel až 100 podle symbolu 7, 4 a 2 poskytuje jazyk {ε, 1,3,4,6,9}, {} a {ε}.

Formální tvrzení věty

Greibachova věta je nezávislá na konkrétním přístupu k popisu formálního jazyka, uvažuje pouze o množině C formálních jazyků nad abecedou Σ∪ {#} takové

• každý jazyk v C má konečný popis,
• každý běžný jazyk nad Σ∪ {#} je v C,^{[poznámka 1]}
• dané popisy jazyků L₁, L₂ ∈ C a běžného jazyka R ∈ C, popis produktů L₁R a RL₁a unie L₁∪L₂ lze efektivně vypočítat a
• je nerozhodnutelný pro jakýkoli členský jazyk L ∈ C s L ⊆ Σ^* zda L = Σ^*.

Nechat P být libovolnou netriviální podmnožinou C který obsahuje všechny běžné množiny nad Σ∪ {#} a je uzavřen pod kvocient každým jednotlivým symbolem v Σ∪ {#}.^{[poznámka 2]}Pak otázka, zda L ∈ P pro daný popis jazyka L ∈ C je nerozhodnutelný.

Důkaz

Nechat M ⊆ Σ^*, takový, že M ∈ C, ale M ∉ P.^{[Poznámka 3]}Pro všechny L ∈ C s L ⊆ Σ^*, definujte φ (L) = (M# Σ^*) ∪ (Σ^*#L). Z popisu L, popis φ (L) lze efektivně vypočítat.

Pak L = Σ^* právě když φ (L) ∈ P:

• Li L = Σ^*, pak φ (L) = Σ^*# Σ^* je běžný jazyk, a tedy v P.
• Jinak někteří w ∈ Σ^* \ L existuje a kvocient φ (L)/(#w) rovná se M. Proto opakovanou aplikací vlastnosti uzavření kvocientu φ (L) ∈ P by znamenalo M = φ (L)/(#w) ∈ P, v rozporu s definicí M.

Proto, pokud členství v P bude rozhodnutelné pro φ (L) z jeho popisu, tak by to bylo LJe rovnost s Σ^* z jeho popisu, který je v rozporu s definicí C.^[3]

Aplikace

Pomocí Greibachovy věty lze ukázat, že následující problémy jsou nerozhodnutelné:

• Vzhledem k bezkontextová gramatika, popisuje to a běžný jazyk ?

Důkaz: Třída bezkontextových jazyků a sada běžných jazyků splňují výše uvedené vlastnosti C, a P, resp.^{[poznámka 4][4]}

• Vzhledem k bezkontextový jazyk, je to ze své podstaty nejednoznačný ?

Důkaz: Třída bezkontextových jazyků a sada bezkontextových jazyků, které nejsou ve své podstatě nejednoznačné, splňují výše uvedené vlastnosti C, a P, resp.^[5]

• Vzhledem k kontextová gramatika, popisuje to a bezkontextový jazyk ?

Viz také Bezkontextová gramatika # Být na nižší nebo vyšší úrovni Chomského hierarchie.

Poznámky

Reference