Chomsky-Schützenberger temsil teoremi - Chomsky–Schützenberger representation theorem

İçinde resmi dil teorisi, Chomsky-Schützenberger temsil teoremi tarafından türetilen bir teorem Noam Chomsky ve Marcel-Paul Schützenberger verileni temsil etmek hakkında bağlamdan bağımsız dil iki basit dil açısından. Bu iki basit dil, yani a normal dil ve bir Dyck dili, bir vasıtasıyla birleştirilir kavşak ve bir homomorfizm.

Biçimsel dil teorisinden birkaç fikir sıralanmıştır. Bağlamdan bağımsız bir dil düzenli, eğer bir Düzenli ifade veya eşdeğer olarak, bir tarafından kabul edilirse sonlu otomat. Bir homomorfizm, bir işleve dayanır ${ displaystyle h}$ bir alfabedeki sembolleri eşleyen ${ displaystyle Gama}$ başka bir alfabenin üzerindeki kelimelere ${ displaystyle Sigma}$; Bu işlevin etki alanı sözcükleri kapsayacak şekilde genişletilirse ${ displaystyle Gama}$ doğal yolla, izin vererek ${ displaystyle h (xy) = h (x) h (y)}$ tüm kelimeler için ${ displaystyle x}$ ve ${ displaystyle y}$, bu bir homomorfizm ${ displaystyle h: Gama ^ {*} ila Sigma ^ {*}}$. Bir eşleşen alfabe ${ displaystyle T cup { overline {T}}}$ iki eşit büyüklükte kümeden oluşan bir alfabedir; bunu bir dizi parantez türü olarak düşünmek uygundur, burada ${ displaystyle T}$ açılış parantez simgelerini içerirken, içindeki simgeler ${ displaystyle { overline {T}}}$ kapanış parantez simgelerini içerir. Eşleşen bir alfabe için ${ displaystyle T cup { overline {T}}}$, Dyck dili ${ displaystyle D_ {T}}$ tarafından verilir

${ displaystyle D_ {T} = {, w in (T cup { overline {T}}) ^ {*} mid w { text {doğru şekilde iç içe geçmiş bir parantez dizisidir}} , }}$

iyi iç içe geçmiş parantezler olan kelimeler ${ displaystyle T cup { overline {T}}}$.

Chomsky-Schützenberger teoremi. Dil L alfabenin üzerinde ${ displaystyle Sigma}$ yalnızca ve ancak varsa bağlamdan bağımsızdır

• eşleşen bir alfabe ${ displaystyle T cup { overline {T}}}$
• normal bir dil ${ displaystyle R}$ bitmiş ${ displaystyle T cup { overline {T}}}$,
• ve bir homomorfizm ${ displaystyle h: (T cup { overline {T}}) ^ {*} - Sigma ^ {*}}$

öyle ki ${ displaystyle L = h (D_ {T} cap R)}$.

Bu teoremin kanıtları birkaç ders kitabında bulunur, örn. Autebert, Berstel ve Boasson (1997) veya Davis, Sigal ve Weyuker (1994).

Referanslar

• Autebert, Jean-Michel; Berstel, Jean; Boasson, Luc (1997). "Bağlamdan Bağımsız Diller ve Aşağı Açılan Otomatlar" (PDF). G. Rozenberg ve A. Salomaa, eds. Resmi Diller El Kitabı, Cilt. 1: Kelime, Dil, Dilbilgisi (sayfa 111–174). Berlin: Springer-Verlag. ISBN  3-540-60420-0.CS1 bakimi: ref = harv (bağlantı)
• Davis, Martin D .; Sigal, Ron; Weyuker, Elaine J. (1994). Hesaplanabilirlik, Karmaşıklık ve Diller: Teorik Bilgisayar Biliminin Temelleri (2. baskı). Elsevier Science. s. 306. ISBN  0-12-206382-1.CS1 bakimi: ref = harv (bağlantı)