Özyinelemeli dil - Recursive language

In matematik , mantık ve bilgisayar bilimleri , bir biçimsel dil (bir dizi sonlu dizilerin sembollerinden sabit alınan alfabesi ) olarak adlandırılır özyinelemeli bir ise özyinelemeli alt küme dilin alfabesi üzerinde olası tüm sonlu dizilerin dizi. Eşdeğer olarak, giriş olarak sonlu bir sembol dizisi verildiğinde, dile aitse kabul eden ve aksi takdirde reddeden toplam bir Turing makinesi ( verilen her giriş için duran bir Turing makinesi) varsa, biçimsel bir dil özyinelemelidir . Özyinelemeli diller de karar verilebilir olarak adlandırılır .

Karar verilebilirlik kavramı, diğer hesaplama modellerine genişletilebilir . Örneğin, deterministik olmayan bir Turing makinesinde kararlaştırılabilir dillerden bahsedilebilir . Bu nedenle, bir belirsizlik mümkün olduğunda, "yinelemeli dil" için kullanılan eşanlamlı , basitçe karar verilebilir değil , Turing tarafından karar verilebilir dildir .

Tüm özyinelemeli dillerin sınıfına genellikle R denir , ancak bu ad RP sınıfı için de kullanılır .

Bu tür bir dil, Chomsky'nin ( Chomsky 1959 ) Chomsky hiyerarşisinde tanımlanmamıştır . Tüm özyinelemeli diller aynı zamanda özyinelemeli olarak numaralandırılabilir . Tüm normal , bağlamdan bağımsız ve içeriğe duyarlı diller özyinelemelidir.

Tanımlar

Özyinelemeli bir dil kavramı için iki eşdeğer ana tanım vardır:

1. Bir özyinelemeli resmi dili olan özyinelemeli alt kümesi içinde sette üzerinde mümkün olan tüm kelimelerin alfabenin bir dille .
2. Özyinelemeli bir dil, herhangi bir sonlu girdi dizgisi ile sunulduğunda , dizginin dilde olup olmadığını kabul eden ve aksi takdirde durduran ve reddeden bir Turing makinesinin bulunduğu resmi bir dildir . Turing makinesi her zaman durur: karar verici olarak bilinir ve özyinelemeli dile karar verdiği söylenir .

İkinci tanımla, herhangi bir karar probleminin , tüm girdilerde sona eren bir algoritma sergileyerek karar verilebilir olduğu gösterilebilir . Bir karar verilemeyen bir problem Karar verilebilen olmayan bir sorundur.

Örnekler

Yukarıda belirtildiği gibi, bağlama duyarlı her dil özyinelemelidir. Bu nedenle, özyinelemeli bir dilin basit bir örneği L={abc, aabbcc, aaabbbccc, ...} kümesidir ; daha resmi olarak, küme

${\displaystyle L=\{\,w\in \{a,b,c\}^{*}\mid w=a^{n}b^{n}c^{n}{\mbox{ bazıları için }}n\geq 1\,\}}$

bağlama duyarlıdır ve bu nedenle özyinelemelidir.

Bağlama duyarlı olmayan karar verilebilir dil örneklerinin tanımlanması daha zordur. Böyle bir örnek için, matematiksel mantığa biraz aşinalık gereklidir: Presburger aritmetiği , toplamalı (ancak çarpmasız) doğal sayıların birinci dereceden teorisidir. Presburger aritmetiğinde iyi biçimlendirilmiş formüller kümesi bağlamdan bağımsız olsa da, Presburger aritmetiğinde doğru ifadeler kümesini kabul eden her deterministik Turing makinesi , bazı sabit c >0 için en azından en kötü durum çalışma süresine sahiptir ( Fischer & Rabin 1974). ). Burada n , verilen formülün uzunluğunu gösterir. Bağlama duyarlı her dil, doğrusal sınırlı bir otomat tarafından kabul edilebildiğinden ve böyle bir otomat, belirli bir c sabiti için en fazla en kötü durum çalışma süresiyle deterministik bir Turing makinesi tarafından simüle edilebildiğinden , Presburger aritmetiğindeki geçerli formüller kümesi değildir. bağlama duyarlı. Pozitif tarafta, içinde triply üstel en fazla vakit kaybetmeden bir deterministik Turing makinesi olduğu bilinmektedir n (Presburger aritmetik gerçek formüllerin kümesini karar Oppen 1978 ). Bu nedenle, bu karar verilebilir ancak bağlama duyarlı olmayan bir dil örneğidir. ${\ Displaystyle 2^{2^{cn}}}$${\görüntüleme stili c^{n}}$

Kapatma özellikleri

Özyinelemeli diller aşağıdaki işlemler altında kapatılır . Yani, L ve P iki özyinelemeli dil ise, aşağıdaki diller de özyinelemelidir:

• Kleene yıldızı ${\görüntüleme stili L^{*}}$
• Bir e-serbest homomorfizma altında görüntü φ(L) φ
• birleştirme ${\ Displaystyle L\circ P}$
• birlik ${\ Displaystyle L\cup P}$
• kavşak ${\ Displaystyle L\cap P}$
• tamamlayıcısı ${\görüntüleme stili L}$
• set farkı ${\ Displaystyle LP}$

Son özellik, küme farkının kesişim ve tümleyen olarak ifade edilebilmesi gerçeğinden kaynaklanmaktadır.

Ayrıca bakınız

• Özyinelemeli olarak numaralandırılabilir dil
• özyineleme

Referanslar

• Michael Sipser (1997). "Karar verilebilirlik" . Hesaplama Teorisine Giriş . PWS Yayıncılık. s.  151–170 . ISBN'si 978-0-534-94728-6.
• Chomsky, Noam (1959). "Dilbilgilerinin belirli biçimsel özellikleri üzerine" . Bilgi ve Kontrol . 2 (2): 137–167. doi : 10.1016/S0019-9958(59)90362-6 .
• Fischer, Michael J .; Rabin, Michael O. (1974). "Presburger Aritmetiğinin Süper Üstel Karmaşıklığı" . Uygulamalı Matematikte SIAM-AMS Sempozyumu Tutanakları . 7 : 27-41.
• Oppen, Derek C. (1978). " Presburger Aritmetiğinin Karmaşıklığı Üzerine 2 ^{2 2 pn} Üst Sınır" . J. Bilgisayar. Sist. Sci . 16 (3): 323-332. doi : 10.1016/0022-0000(78)90021-1 .