Ağaca bitişik dilbilgisi - Tree-adjoining grammar

Ağaca bitişik dilbilgisi ( TAG ), Aravind Joshi tarafından tanımlanan bir gramer biçimciliğidir . Ağaca bitişik dilbilgisi, bağlamdan bağımsız gramerlere biraz benzer , ancak yeniden yazmanın temel birimi, sembolden çok ağaçtır. Bağlamdan bağımsız gramerler, sembolleri diğer sembollerin dizileri olarak yeniden yazmak için kurallara sahipken, ağaca bitişik dilbilgileri, ağaçların düğümlerini diğer ağaçlar gibi yeniden yazmak için kurallara sahiptir (bkz. Ağaç (grafik teorisi) ve ağaç (veri yapısı) ).

Tarih

TAG, Joshi ve öğrencilerinin Zellig Harris'in "dizgi grameri" olan adjunction grammars (AG) ailesine yaptığı araştırmalardan kaynaklandı . AG'ler dilin dış merkezli özelliklerini doğal ve etkili bir şekilde ele alırlar , ancak iç merkezli yapıların iyi bir karakterizasyonuna sahip değildir ; tersi, yeniden yazma gramerleri veya kelime öbeği yapısı grameri (PSG) için doğrudur . 1969'da Joshi, iki tür kuralı karıştırarak bu tamamlayıcılığı kullanan bir gramer ailesini tanıttı. Birleştirme kuralları için dizelerin kelime dağarcığını oluşturmak için çok basit birkaç yeniden yazma kuralı yeterlidir. Bu aile, Chomsky-Schützenberger hiyerarşisinden farklıdır ancak ilginç ve dilbilimsel olarak ilgili yollarla kesişir. Merkez dizgileri ve yardımcı dizeler , yeniden yazma sistemlerinin sınırlamalarından tamamen kaçınarak bir bağımlılık dilbilgisi ile de üretilebilir .

Açıklama

Bir ETİKET'teki kurallar, bir kelimeye tutturulmuş , ayak düğümü olarak bilinen özel bir yaprak düğümüne sahip ağaçlardır . TAG'de iki tür temel ağaç vardır: ilk ağaçlar (genellikle ' ' olarak gösterilir) ve yardımcı ağaçlar (' '). İlk ağaçlar temel değerlik ilişkilerini temsil ederken, yardımcı ağaçlar özyinelemeye izin verir. Yardımcı ağaçların kök (üst) düğümü ve aynı sembolle etiketlenmiş ayak düğümü vardır. Bir türetme biri yoluyla birleştiren, ilk ağaç ile başlar ikame ya da birleşim . İkame, bir sınır düğümünü, üst düğümü aynı etikete sahip başka bir ağaçla değiştirir. Yardımcı ağacın kök / dip etiketi, birleştiği düğümün etiketi ile eşleşmelidir. Dolayısıyla birleşme, başka bir ağacın merkezine yardımcı bir ağaç ekleme etkisine sahip olabilir.

TAG'ın diğer varyantları, çok bileşenli ağaçlara , birden çok ayak düğümü olan ağaçlara ve diğer uzantılara izin verir.

Karmaşıklık ve uygulama

Ağaca bitişik gramerler, bağlamdan bağımsız gramerlerden daha güçlüdür ( zayıf üretim kapasitesi açısından ) , ancak doğrusal bağlamdan bağımsız yeniden yazma sistemlerinden , indeksli veya bağlama duyarlı gramerlerden daha az güçlüdür .

ETİKET, karelerin dilini (bazı rasgele dizelerin tekrarlandığı) ve dili tanımlayabilir . Bu tür bir işlem, gömülü bir aşağı açılan otomatla temsil edilebilir . Küpleri olan diller (yani üçlü dizeler) veya eşit uzunlukta dörtten fazla farklı karakter dizisine sahip diller ağaca bitişik gramerler tarafından oluşturulamaz.

Bu nedenlerden dolayı, ağaca bitişik dilbilgisi genellikle biraz içeriğe duyarlı olarak tanımlanır . Bu dilbilgisi sınıflarının , genel durumda verimli bir şekilde çözümlenebilir kalırken, doğal dilleri modelleyecek kadar güçlü olduğu varsayılmaktadır .

Eşdeğerler

Vijay-Shanker ve Weir (1994) göstermektedir endeksli gramerlerin doğrusal , kombinatoriyel ulamsal gramer , ağaç bitişik dilbilgisi ve baş dilbilgisi olan zayıf eşdeğer hepsi aynı dize diller tanımlamak olmasıyla, Biçimsel.

Sözcükselleştirilmiş

Sözcükselleştirilmiş ağaca bitişik gramerler (LTAG), her temel ağacın (ilk veya yardımcı) bir sözcüksel öğe ile ilişkilendirildiği bir TAG çeşididir. Pennsylvania Üniversitesi Bilişsel Bilimler Araştırma Enstitüsü'nün XTAG Araştırma Grubu tarafından İngilizce için sözcükselleştirilmiş bir gramer geliştirilmiştir.

Notlar

Referanslar

Dış bağlantılar