Turingovsky úplná bezkontextová gramatika

Na první pohled se mi zdál článek nějaký divný a po přečtení prvního odstavce se to potvrdilo. Je to skutečně nad moje chápání. Jsem tu jen proto, že mě zaujal stejně divný nadpis :D

Taky tomu zbla nerozumim. Mozna je v tom neco strasne chytreho, ale pokud ten prispevek ma mit nejaky dopad, tak bych to popisoval trosku vice lidsky. Ono i velmi slozita vec se da vysvetlit jednoduchym zpusobem.

Tak gramatiky sa moc ľudsky vysvetliť nedajú, aspoň o tom neviem.

@2 Takto je to popsáno "nejlidštěji", jak to jen jde, @3 má pravdu. Gramatiky zná každý (studovaný) informatik, formální logiku také, jen jejich kombinace je obecně neznámá. Princip je primitivní, ovšem nad detaily je třeba se zamyslet. Což je pro většinu lidí zjevně problém :-)

@2 Na každou otázku existuje spousta jednoduchých, lehce pochopitelných, nesprávných odpovědí.

Nechápu, odkud se v tom příkladu bere gd≈f2 a hd≈f3. Kdyby tam bylo fgd≈2 a fhd≈3, tak bych to ještě chvíli zkoušel.

@6 To byla samozřejmě chyba, díky za upozornění. Zatím jste asi jediný, kdo to pochopil :-)

@3 @4 @5 No tak to bych tak uplne nerekl. Napr. Boost.Spirit/Bi­son/ANTLR maji dokumentaci psanou, ze ji rozumim. Ale asi se opravdu jen nechci zamyslet.

A. co je to preterminal?

B. existuje na to nejaky efektivni algoritmus? Jestli to spravne chapu tak naivni algoritmus by musel:

1. vygenerovat vsechny mozne derivacni stromy te zakladni gramatiky, kterych muze byt obecne exponencialni mnozstvi...
2. pro kazdy derivacni strom sestavit formuli a pomoci SAT/SMT solveru testovat splnitelnost, coz muze mit obecne exponencialni slozitost...

jestli je tohle jediny algoritmus tak to nezni moc uzitecne ;-)

@9 A. Preterminál je neterminál nad terminálem (není mezi nimi jiný neterminál).
B. Velmi dobrá poznámka. Problém je obecně NP úplný. Praktické použití ovšem většinou má max. složitost O(n^3). Naivní algoritmus opravdu vytvoří všechny syntaktické stromy a potom testuje splnitelnost přiřazené formule. K tomu naštěstí existuje relativně efektivní algoritmus (založený na kongruenčních uzávěrech). V praxi se používá tzv. "interleaved" metoda, jež již během parsingu podle pravidel testuje splnitelnost formulí. Protože proces tvorby formulí je monotonní (jen přidáváme další konjunkce), nesplnitelná formule implikuje nesplnitelnost jakékoliv své nadformule, a tedy není třeba v aktuální větvi derivace pokračovat. V praxi tedy na konci (pokud se dostaneme až k počátečnímu symbolu) máme jen ty stromy, ke kterým existuje alespoň jedna splnitelná formule. Zde je zajímavé, že zatímco jakákoliv bezkontextová gramatika se dá zpracovat pro libovolný vstup v čase O(n^3) (jednoznačné gramatiky v O(n^2)), ve spojení s FL je proces analýzy obecně NP úplný. Nicméně praktické úlohy popisují nanejvýš "mildly context sensitive" jazyky a tedy parsing bývá polynomiální.

aha, to jsem prehlidl ze se omezujes jenom na konjunkce. V tom pripade by to melo jit polynomialne.

@11 Vlastně tam může být i disjunkce. Ty formule se v praxi reprezentují tak, že společné části se sdílejí, takže i vyhodnocení splnitelnosti je pak rychlé. Bez újmy na obecnosti lze dokonce použít i regulární gramatiku.

i kdyz tam mas jenom konjunkce? (zadna negace a pod.)

@13 Ano, problémem je disjunkce a ta se dá "nasimulovat". Potom to celé může být NP úplné.

neni problem spis negace? Nemam tady ten algoritmus naprogramovanej, takze jsem mozna neco prehlidl, ale kdyz se snazim si predstavit jak bych upravil CYK, tak u konjunkce a disjunkce zadny problem nevidim.

@15 Problém je ten, že disjunkce vnáší do gramatiky víceznačnost (exponenciálně). Stačí si představit, že každé pravidlo zavede jednu (novou) disjunkci. Potom počet formulí roste exponenciálně.

predpodladam ze jako parsovaci algoritmus pouzivate CYK, kdyz zminujes slozitost n**3. Tam ten problem s disjunkci porad nevidim.

Jediny co me napada je ze kombinace konjunkce a disjunkce by mohla zpusobit exponencialni rust neterminalu pri prevodu do chomskeho normalni formy. Je tohle to co myslis?

Algoritmus testování splnitelnosti vyžaduje formuli v DNF, ale parsingem vzniká konjunkce klauzulí. Když budu mít pravidlo A → A A, u prvního A bude d≈a a u druhého fd≈b ⋁ gd≈b, tak převod výsledné formule do DNF bude exponenciální.

V @10 jsem se nepřesně vyjádřil - během analýzy vznikají konjunkce formulí, ale počáteční formule se berou z lexikonu, takže mohou obsahovat libovolné konektivy. V praxi se ovšem používá i pro preterminály jen formule v KNF bez negace.