Üretim (bilgisayar bilimi) - Production (computer science)

Bu makale için ek alıntılara ihtiyaç var doğrulama. Lütfen yardım et bu makaleyi geliştir tarafından güvenilir kaynaklara alıntılar eklemek. Kaynaksız materyale itiraz edilebilir ve kaldırılabilir. Kaynakları bulun: "Üretim" bilgisayar bilimi  – Haberler  · gazeteler  · kitabın  · akademisyen  · JSTOR (Kasım 2012) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin)

Bir üretim veya üretim kuralı bilgisayar biliminde bir yeniden yazma kuralı yeni sembol dizileri oluşturmak için yinelemeli olarak gerçekleştirilebilecek bir sembol ikamesinin belirtilmesi. Sonlu bir dizi prodüksiyon ${displaystyle P}$ bir şartnamesindeki ana bileşendir resmi gramer (özellikle bir üretken gramer ). Diğer bileşenler sonlu bir kümedir ${displaystyle N}$ nın-nin terminal olmayan semboller, sonlu bir küme (alfabe olarak bilinir) ${displaystyle Sigma}$ nın-nin terminal sembolleri yani ayrık itibaren ${displaystyle N}$ ve seçkin bir sembol ${displaystyle Sin N}$ bu başlama sembolü.

Bir sınırsız dilbilgisi, formda bir üretim ${displaystyle u o v}$, nerede ${displaystyle u}$ ve ${displaystyle v}$ terminallerin ve terminal olmayanların keyfi dizeleridir ve ${displaystyle u}$ olmayabilir boş dize. Eğer ${displaystyle v}$ boş dizedir, bu sembolü ile gösterilir ${displaystyle epsilon}$veya ${displaystyle lambda}$ (sağ tarafı boş bırakmak yerine). Yani prodüksiyonlar, Kartezyen ürün

${displaystyle V ^ {*} NV ^ {*} imes V ^ {*} = (V ^ {*} setminus Sigma ^ {*}) imes V ^ {*}}$,

nerede ${displaystyle V: = Ncup Sigma}$ ... kelime bilgisi, ${displaystyle {} ^ {*}}$ ... Kleene yıldızı Şebeke, ${displaystyle V ^ {*} NV ^ {*}}$ gösterir birleştirme, ${displaystyle cup}$ gösterir birlik kurmak, ve ${displaystyle setminus}$ gösterir eksi ayarla veya farkı ayarla. Başlangıç ​​sembolünün oluşmasına izin vermezsek ${displaystyle v}$ (sağdaki kelime), değiştirmeliyiz ${displaystyle V ^ {*}}$ tarafından ${displaystyle (Vsetminus {S}) ^ {*}}$ kartezyen ürün sembolünün sağ tarafında.^[1]

Diğer biçimsel dilbilgisi türleri Chomsky hiyerarşisi bir üretimi neyin oluşturduğuna ek kısıtlamalar getirir. Özellikle bir bağlamdan bağımsız gramer, bir üretimin sol tarafı tek bir terminal olmayan sembol olmalıdır. Yani prodüksiyonlar şu şekildedir:

${displaystyle N o (Ncup Sigma) ^ {*}}$

Dilbilgisi oluşturma

Dilde bir dizi oluşturmak için, kişi yalnızca tek bir dizeden oluşan bir dizeyle başlar. başlama sembolüve ardından bu dizeyi yeniden yazmak için kuralları (herhangi bir sayıda, herhangi bir sırada) art arda uygular. Bu, sadece terminalleri içeren bir dizge elde ettiğimizde durur. Dil, bu şekilde oluşturulabilen tüm dizelerden oluşur. Bu yeniden yazma işlemi sırasında alınan belirli bir yasal seçim dizisi, dilde belirli bir dizgi oluşturur. Bu tek dizgeyi oluşturmanın birden fazla farklı yolu varsa, dilbilgisinin şöyle olduğu söylenir: belirsiz.

Örneğin, alfabenin şunlardan oluştuğunu varsayalım: ${displaystyle a}$ ve ${displaystyle b}$, başlangıç ​​simgesiyle ${displaystyle S}$ve aşağıdaki kurallara sahibiz:

1. ${displaystyle Sightarrow aSb}$

2. ${displaystyle Sightarrow ba}$

sonra başlarız ${displaystyle S}$ve ona uygulanacak bir kural seçebilir. 1. kuralı seçersek, değiştiririz ${displaystyle S}$ ile ${displaystyle aSb}$ ve dizeyi elde edin ${displaystyle aSb}$. Tekrar 1. kuralı seçersek, ${displaystyle S}$ ile ${displaystyle aSb}$ ve dizeyi elde edin ${displaystyle aaSbb}$. Bu işlem, yalnızca alfabeden semboller elde edene kadar tekrarlanır (ör. ${displaystyle a}$ ve ${displaystyle b}$). Şimdi 2. kuralı seçersek, ${displaystyle S}$ ile ${displaystyle ba}$ ve dizeyi elde edin ${displaystyle aababb}$ve yapılır. Bu seçenekler serisini sembolleri kullanarak daha kısaca yazabiliriz: ${displaystyle SRightarrow aSbRightarrow aaSbbRightarrow aababb}$. Dilbilgisinin dili, bu işlem kullanılarak oluşturulabilen tüm dizelerin kümesidir: ${displaystyle {ba, abab, aababb, aaababbb, dotsc}}$.

Ayrıca bakınız

• Biçimsel gramer
• Sonlu otomata
• Üretken gramer
• L sistemi
• Kuralı yeniden yaz
• Backus-Naur formu (Bağlamdan bağımsız bir dilbilgisinin prodüksiyonlarını yazmak için kompakt bir form.)
• Kelime öbeği yapısı kuralı
• Kanonik sistemi yayınla (Emil Post'un üretim sistemleri - bir hesaplama modeli.)

Referanslar