boolesk grammatik

Booleska grammatiker , introducerad av Okhotin , är en klass av formell grammatik som studeras i formell språkteori. De utökar den grundläggande typen av grammatik, de sammanhangsfria grammatikerna , med konjunktions- och negationsoperationer . Förutom dessa explicita operationer tillåter booleska grammatiker implicit disjunktion representerad av flera regler för en enda icke-terminal symbol, vilket är det enda logiska bindemedlet som kan uttryckas i kontextfria grammatiker. Konjunktion och negation kan särskilt användas för att specificera korsning och komplement av språk. En mellanklass av grammatiker känd som konjunktiv grammatik tillåter konjunktion och disjunktion, men inte negation.

Reglerna för en boolesk grammatik är av formen

$A\to \alpha _{1}\And \ldots \And \alpha _{m}\And \lnot \beta _ {1}\And \ldots \And \lnot \beta _{n}$

där $A$ är en icke-terminal, $m+n\geq 1$ och ${\displaystyle \alpha _{1}} ,$ ..., $\ alpha _{m}$ , $\beta _{1}$ , ..., $\beta _{n}$ är strängar som bildas av symboler i $\Sigma$ och $N$ . Informellt hävdar en sådan regel att varje sträng $w$ över $\Sigma$ som uppfyller vart och ett av de syntaktiska villkoren representerade av ${\displaystyle \alpha _{1}} ,$ ..., $\alpha _{m}$ och inget av de syntaktiska villkoren representerade av ${\displaystyle \beta _{1}} ,$ ..., $\beta _{n}$ uppfyller därför villkoret definierat av $A$ .

Det finns flera formella definitioner av språket som genereras av en boolesk grammatik. De har en sak gemensamt: om grammatiken representeras som ett system av språkekvationer med union, skärningspunkt, komplement och sammanlänkning, måste språken som genereras av grammatiken vara lösningen på detta system. Semantiken skiljer sig åt i detaljer, en del definierar språken med hjälp av språkekvationer, en del bygger på idéer från området för logisk programmering . Dessa icke-triviala frågor om formell definition är dock för det mesta irrelevanta för praktiska överväganden, och man kan konstruera grammatik enligt den givna informella semantiken. De praktiska egenskaperna hos modellen liknar de för konjunktiva grammatiker , medan beskrivningsförmågan förbättras ytterligare. Speciellt några praktiskt användbara egenskaper som ärvts från kontextfria grammatiker , såsom effektiva parsningsalgoritmer, behålls, se Okhotin (2010) .

• Okhotin, Alexander (2004-10-10). "Booleska grammatiker" . Information och beräkning . 194 (1): 19–48. doi : 10.1016/j.ic.2004.03.006 .
• Okhotin, Alexander (2006). Nio öppna problem om konjunktiv och boolesk grammatik (PDF) (Teknisk rapport). TUCS. 794.
• Kountouriotis, Vassilis; Nomikos, Christos; Rondogiannis, Panos (2009). "Välgrundad semantik för boolesk grammatik" (PDF) . Information och beräkning . 207 (9): 945–967. doi : 10.1016/j.ic.2009.05.002 .
• Okhotin, Alexander (2010). "Snabb analys för boolesk grammatik: en generalisering av Valiants algoritm". I Gao, Y.; Lu, H.; Seki, S.; Yu, S. (red.). Utveckling inom språkteori . 14:e internationella konferensen, DLT 2010, London, ON, Kanada, 17-20 augusti 2010, Proceedings . Föreläsningsanteckningar i datavetenskap . Vol. 6224. s. 340–351. Förtryck tillgängligt online, arkiverat 3 mars 2016 på Wayback Machine .

externa länkar

• Okhotins sida om boolesk grammatik