Gramatyka boolowska

Gramatyki boolowskie , wprowadzone przez Okhotina , to klasa gramatyk formalnych studiowana w teorii języka formalnego . Rozszerzają podstawowy typ gramatyk, gramatyk bezkontekstowych , o operacje koniunkcji i negacji . Oprócz tych jawnych operacji, gramatyki boolowskie dopuszczają niejawną dysjunkcję reprezentowaną przez wiele reguł dla pojedynczego symbolu nieterminalnego, który jest jedynym łącznikiem logicznym możliwym do wyrażenia w gramatykach bezkontekstowych. Koniunkcji i negacji można użyć w szczególności do określenia przecięcia i dopełnienia języków. Pośrednia klasa gramatyk, znana jako gramatyki koniunkcyjne, dopuszcza koniunkcję i dysjunkcję, ale nie negację.

Reguły gramatyki boolowskiej mają formę

${\ Displaystyle A \ do \ alfa _ {1} \ I \ ldots \ I \ alfa _ {m} \ I \ lnot \ beta _ {1}\I \ldots \I \lnot \beta _{n}}$

gdzie jest ${$ , ${\ Displaystyle m + n \ geq 1}$ i $\ Displaystyle \ alpha _ {1}}$ , ..., ${\ Displaystyle \ alfa _ {m}}$ , ${\ Displaystyle \ beta _ {1}}$ , ..., ${\ Displaystyle \ beta _ {n}}$ to ciągi utworzone z symboli w ${\ Displaystyle \ Sigma}$ i ${\ Displaystyle N}$ . Nieformalnie $spełnia każdy$ reguła stwierdza, że ​​​​każdy ciąg $powyżej$$,$ warunków składniowych reprezentowanych przez ... , ${\ Displaystyle \ alpha _ {m}}$ i żaden z warunków składniowych reprezentowanych przez ${\ Displaystyle \ beta _ {1}}$ , ..., ${\ Displaystyle \ beta _ {n}}$ spełnia zatem warunek określony przez ${\ displaystyle A}$ .

Istnieje kilka formalnych definicji języka generowanego przez gramatykę boolowską. Łączy je jedno: jeśli gramatyka jest reprezentowana jako system równań językowych z sumą, przecięciem, uzupełnieniem i konkatenacją, języki generowane przez gramatykę muszą być rozwiązaniem tego systemu. Semantyka różni się w szczegółach, niektóre definiują języki za pomocą równań językowych, niektóre czerpią z pomysłów z dziedziny programowania logicznego . Jednak te nietrywialne kwestie definicji formalnej są w większości nieistotne z praktycznych względów i można konstruować gramatyki zgodnie z zadaną nieformalną semantyką. Praktyczne właściwości modelu są podobne do gramatyk koniunkcyjnych , natomiast możliwości opisowe są jeszcze udoskonalone. W szczególności zachowane są niektóre praktycznie użyteczne właściwości odziedziczone z gramatyk bezkontekstowych , takie jak wydajne algorytmy analizy składniowej, patrz Okhotin (2010) .

• Ochotin, Aleksander (2004-10-10). „Gramatyka boolowska” . Informacja i obliczenia . 194 (1): 19–48. doi : 10.1016/j.ic.2004.03.006 .
• Okhotin, Aleksander (2006). Dziewięć otwartych problemów dotyczących gramatyk koniunkcyjnych i boolowskich (PDF) (raport techniczny). TUCS. 794.
• Kountouriotis, Wasilis; Nomikos, Christos; Rondogiannis, Panos (2009). „Dobrze uzasadniona semantyka dla gramatyk boolowskich” (PDF) . Informacja i obliczenia . 207 (9): 945–967. doi : 10.1016/j.ic.2009.05.002 .
• Okhotin, Aleksander (2010). „Szybkie analizowanie gramatyk boolowskich: uogólnienie algorytmu Valianta”. W Gao, Y.; Lu, H.; Seki, S.; Yu, S. (red.). Rozwój teorii języka . 14th International Conference, DLT 2010, Londyn, ON, Kanada, 17-20 sierpnia 2010 r., Proceedings . Notatki z wykładów z informatyki . Tom. 6224. s. 340–351. Preprint dostępny online, zarchiwizowany 3 marca 2016 r. W Wayback Machine .

Linki zewnętrzne

• Strona Okhotina poświęcona gramatyce boolowskiej