In matematik , bilgisayar bilimi ve dilbilim , bir biçimsel dil kümesidir kelime . Resmi bir dilin alfabesi, dilin sözcüklerini oluşturmak için kullanılan semboller, harfler veya sözlük birimleridir; çoğu zaman bu alfabenin bittiği varsayılır. Amacı biçimsel dil teorisine biçimsel dilleri tanımlamaktır.
Sözcükler bu alfabenin öğelerinin dizileridir; Belirli bir biçimsel dile ait olan sözcüklere bazen iyi biçimlendirilmiş sözcükler veya iyi biçimlendirilmiş formüller denir . Resmi bir dil genellikle cebirsel gramerler gibi resmi bir dilbilgisi ile tanımlanır ve otomata tarafından analiz edilir .
Biçimsel diller teorisi , bu tür dillerin tamamen sözdizimsel yönlerini , yani biçimsel iç yapılarını inceler . Dil teorisi , doğal dillerin sözdizimsel düzenliliklerini anlamanın bir aracı olarak dilbilimden kaynaklanır :
Biçimsel dillerin incelenmesi, üretim için biçimsel gramerler ve tanıma için otomatlar gibi bu dillerin tüm açıklama ve analiz araçlarını içerir , ancak aynı zamanda makine öğrenimi ve otomatik diller ile de ilgilenir . Çeviri alanında, dil teorisi programlama dili derleyicileri için geçerlidir .
Kendimize , öğelerine harf adı verilen, alfabe adı verilen bir küme veririz .
Bu iç bileşim yasası birleştiricidir ve nötr öğe için boş sözcüğü kabul eder (bu, gösterimi haklı çıkarır ). Sonuç olarak, bu yasa ile sağlanan küme bir monoiddir . Bu bir olan serbest monoid cebir anlamında.
Bir resmi dil bir kısmını demek ki sonlu alfabesi, kelimelerin bir dizi ücretsiz Monoid bu alfabenin üzerine.
Resmi dillere bazı örnekler:
Resmi bir dil farklı yollarla belirtilebilir. Aranan, genel olarak sonsuz bir dil üretmeyi veya analiz etmeyi mümkün kılan sonlu ve açık bir yöntem veya mekanizmadır. Bu yöntemler arasında şunlar vardır:
Resmi bir dil hakkında kendimize sorduğumuz tipik sorular şunlardır:
Bu soruların hesaplanabilirlik ve karmaşıklık teorisi ile bağlantıları vardır .
Diller, dil aileleri halinde gruplandırılmıştır. Chomsky Hiyerarşisi bize her biri bir dil ailesi oluşturan dört tür dilbilgisi verir.
Bu dil kümelerinin tümü birbirine dahildir ve burada en büyük kümeden en küçüğüne kadar verilmiştir. Bütün Yani rasyonel dil olan cebirsel , hangi kendisidir içeriksel kendisi olan ardışık enumerable .
Bu 4 dil ailesi arasında, Chomsky hiyerarşisinin bir parçası olmayan, ancak tanımları ve özellikleri ile dikkat çekici olan aileler not edilebilir. Deterministik bağlam-bağımsız diller tarafından tanınan dillerdir otomata deterministik yığını ve kesinlikle cebirsel dilleri ailesine dahildir. Özyinelemeli diller olan tamamlayıcı aynı zamanda bir Turing makinesi tarafından tanınan bir Turing makinesi ve tanıdığı dillerdir. Bu nedenle, yinelemeli olarak numaralandırılabilir dillere kesinlikle dahil edilirler .
Verilen dillerden yeni diller oluşturmak için çeşitli işlemler kullanılabilir. L ve M'nin bazı ortak alfabedeki diller olduğunu varsayalım .
Küme işlemleri kesişim , birleşim ve tümleme , herhangi bir küme için olduğu gibi tanımlanır.
Birleştirme bölgesinin L ve M , sadece belirtildiği şekilde bir deyişle setidir xy , X bir kelime L ve orada bir kelime M .
Sola bölüm arasında bir kelimenin kelime kümesidir gibi aittir . Soldaki bölüme artık denir .
Sağa doğru bölüm arasında bir kelime kelime grubu olarak simetrik tanımlandığı gibi aittir .
Soldaki bölüm ve sağdaki bölüm dillere uzanır. Böylece, solundaki bölüm dile simgelenen , dillerin birliktir için de .
Kleene yıldızı ait L fark kümesidir formun kelimelerin oluşan ile ve . Bu küme boş kelimesini içerir .
Ters ait L kaydetti veya içerdiği ayna sözlerinin sözlerini L sözler demek ki, L , sağdan sola doğru okunan.
Karışım bir L ve M gösterilen, L Ш M yazılabilir sözcük grubu olduğu yerde ve şekilde (muhtemelen boş) kelime olan bir kelime ya da L ve bir kelime ya da M . Örneğin Ш .
Bir uygulama bir olan morfizmanın veya homomorfizmi si bütün kelimeleri arasında . Bir dil homomorfik görüntüsü tarihinde adlı dizi
.Dilin kötüye kullanılmasıyla, ters morfizmi , bir morfizmin tersi olarak adlandırırız. Ters morfizmi, tarafından tanımlanan parçalar kümesinde belirtilen işlevidir .
.Genellikle bir morfizm değildir. Bir dilin ters morfizmalar görüntü üzerinde dildir
.Bir morfizmanın olan olmayan silme veya artan İngilizce taklit yoluyla ya, ε içermeyen bir mektup görüntü boş bir kelime asla ise. Bu durumda, bir kelimenin görüntüsünün uzunluğu, kelimenin uzunluğundan büyük veya ona eşittir.
Bu işlemlerle ilgili ortak bir soru, bu işlemlerin her biri için her dil ailesinin kapanış özelliklerini bilmektir, yani bir işlemden kaynaklanan dil, geldiği dillerle aynı dil ailesinde kalırsa.
rasyonel diller |
Deterministik cebirsel diller |
cebirsel diller |
bağlamsal diller |
özyinelemeli diller |
Özyinelemeli olarak numaralandırılabilir diller |
|
---|---|---|---|---|---|---|
Birlik | Kapalı | Çit YOK | Kapalı | Kapalı | Kapalı | Kapalı |
kavşak | Kapalı | Çit YOK | Çit YOK | Kapalı | Kapalı | Kapalı |
Tamamlayıcı | Kapalı | Kapalı | Çit YOK | Kapalı | Kapalı | Çit YOK |
birleştirme | Kapalı | Çit YOK | Kapalı | Kapalı | Kapalı | Kapalı |
Kleene Yıldızı | Kapalı | Çit YOK | Kapalı | Kapalı | Kapalı | Kapalı |
Ayna | Kapalı | Çit YOK | Kapalı | Kapalı | Kapalı | Kapalı |
Karışık | Kapalı | Çit YOK | Çit YOK | Çit YOK | Çit YOK | Çit YOK |
biçimcilik | Kapalı | Çit YOK | Kapalı | Çit YOK | Çit YOK | Kapalı |
Büyüyen morfizm | Kapalı | Çit YOK | Kapalı | Kapalı | Kapalı | Kapalı |
ters morfizm | Kapalı | Kapalı | Kapalı | Kapalı | Kapalı | Kapalı |