Chomsky-Schützenberger sayım teoremi - Chomsky–Schützenberger enumeration theorem

İçinde resmi dil teorisi, Chomsky-Schützenberger sayım teoremi tarafından türetilen bir teorem Noam Chomsky ve Marcel-Paul Schützenberger bir tarafından oluşturulan belirli bir uzunluktaki kelimelerin sayısı hakkında kesin bağlamdan bağımsız gramer. Teorem, teorisi arasında beklenmedik bir bağlantı sağlar. resmi diller ve soyut cebir.

Beyan

Teoremi ifade etmek için cebir ve biçimsel dil teorisinden birkaç fikre ihtiyaç vardır.

İzin Vermek negatif olmayan tamsayılar kümesini gösterir. Bir güç serisi bitmiş bir sonsuz seriler şeklinde

katsayılarla içinde . çarpma işlemi iki resmi güç serisi ve beklenen şekilde tanımlanır: kıvrım dizilerin ve :

Özellikle yazıyoruz , , ve benzeri. Benzetme olarak cebirsel sayılar, bir güç serisi denir cebirsel bitmiş , sonlu bir polinom kümesi varsa her biri ile akılcı katsayılar öyle ki

Bağlamdan bağımsız bir gramer olduğu söyleniyor kesin eğer her biri dizi dilbilgisi tarafından oluşturulan benzersiz bir ayrıştırma ağacını veya eşdeğer olarak yalnızca bir en soldaki türev Gerekli kavramlar oluşturulduktan sonra teorem aşağıdaki gibi ifade edilir.

Chomsky-Schützenberger teoremi. Eğer bir bağlamdan bağımsız dil net bir bağlamdan bağımsız dilbilgisi kabul etmek ve uzunluktaki kelimelerin sayısıdır içinde , sonra bir güç dizisi bu cebirseldir .

Bu teoremin kanıtları şu şekilde verilmiştir: Kuich ve Salomaa (1985) ve tarafından Panholzer (2005).

Kullanım

Asimptotik tahminler

Teorem kullanılabilir analitik kombinatorik uzunluktaki kelimelerin sayısını tahmin etmek n belirli bir bağlamdan bağımsız gramer tarafından oluşturulmuş, n büyür. Aşağıdaki örnek, Gruber, Lee ve Shallit (2012): kesin bağlamdan bağımsız gramer G alfabenin üzerinde {0,1} başlangıç ​​sembolüne sahiptir S ve aşağıdaki kurallar

SM | U
M → 0M1M | ε
U → 0S | 0M1U.

Kuvvet serisinin cebirsel gösterimini elde etmek için belirli bir bağlamdan bağımsız dilbilgisi ile ilişkili G, grameri bir denklem sistemine dönüştürür. Bu, bir uçbirim sembolünün her oluşumunu şu şekilde değiştirerek elde edilir: x, her seferinde ε '1' tamsayısıyla, '=' ile her '→' oluşumu ve '|' sırasıyla '+' ile. Her kuralın sağ tarafındaki birleştirme işlemi, bu şekilde elde edilen denklemlerdeki çarpma işlemine karşılık gelir. Bu, aşağıdaki denklem sistemini verir:

S = M + U
M = M²x² + 1
U = Sx + MUx²

Bu denklem sisteminde, S, M, ve U fonksiyonlarıdır x, böylece biri de yazabilir , , ve . Denklem sistemi sonra çözülebilir S, tek bir cebirsel denklemle sonuçlanır:

.

Bu ikinci dereceden denklemin iki çözümü vardır: Sbunlardan biri cebirsel kuvvet serisidir . Karmaşık analizden bu denkleme yöntemler uygulayarak, sayı uzunluktaki kelimelerin n tarafından oluşturuldu G olarak tahmin edilebilir n büyür. Bu durumda elde edilen fakat her biri için . Görmek (Gruber, Lee ve Shallit 2012 ) detaylı bir sergi için.

İçsel belirsizlik

Klasik biçimsel dil teorisinde teorem, belirli bağlamdan bağımsız dillerin doğası gereği belirsiz Örneğin, Goldstine dili alfabenin üzerinde kelimelerden oluşurile , için , ve bazı .

Dilin gösterilmesi nispeten kolaydır. bağlamdan bağımsızdır (Berstel ve Boasson 1990 ). İşin zor kısmı, ortaya çıkaran kesin bir dilbilgisi olmadığını göstermektir. . Bu şu şekilde kanıtlanabilir: Eğer uzunluktaki kelimelerin sayısını gösterir içinde , daha sonra ilişkili güç serisi tutmaları içinYöntemleri kullanarak karmaşık analiz, bu fonksiyonun cebirsel olmadığını kanıtlayabiliriz. . Chomsky-Schützenberger teoremi ile şu sonuca varılabilir: kesin bir bağlamdan bağımsız dilbilgisi kabul etmez. Görmek (Berstel ve Boasson 1990 ) detaylı hesap için.

Referanslar

Berstel, Jean; Boasson, Luc (1990). "Bağlamdan bağımsız diller" (PDF). Van Leeuwen'de, Jan (ed.). Teorik Bilgisayar Bilimi El Kitabı, Cilt B: Biçimsel Modeller ve Anlambilim. Elsevier ve MIT basın. s. 59–102. ISBN  0-444-88074-7.CS1 bakimi: ref = harv (bağlantı)
Chomsky, Noam; Schützenberger, Marcel-Paul (1963). "Bağlamdan Bağımsız Dillerin Cebirsel Teorisi" (PDF). P. Braffort ve D. Hirschberg, editörler, Bilgisayar Programlama ve Biçimsel Sistemler (sayfa 118–161). Amsterdam: Kuzey-Hollanda.CS1 bakimi: ref = harv (bağlantı)
Flajolet, Philippe; Sedgewick, Robert (2009). Analitik Kombinatorik. Cambridge: Cambridge University Press. ISBN  978-0-521-89806-5.CS1 bakimi: ref = harv (bağlantı)
Gruber, Hermann; Lee, Jonathan; Shallit Jeffrey (2012). "Normal ifadeleri ve dillerini numaralandırma". arXiv:1204.4982 [cs.FL ].CS1 bakimi: ref = harv (bağlantı)
Kuich, Werner; Salomaa, Arto (1985). Yarı mamuller, Otomatlar, Diller. Berlin: Springer-Verlag. ISBN  978-3-642-69961-0.CS1 bakimi: ref = harv (bağlantı)
Panholzer Alois (2005). "Gröbner Tabanları ve Bağlamdan Bağımsız Dilbilgisi Oluşturma Fonksiyonunun Tanımlanması Polinomu". Otomata, Diller ve Kombinatorik Dergisi. 10: 79–97.CS1 bakimi: ref = harv (bağlantı)