Dize işlemleri - String operations
Gelen bilgisayar bilimleri , alanında resmi dil teorisi , sık kullanım çeşitliliği yapılır dize fonksiyonları ; Bunun için kullanılan gelen ancak kullanılan gösterim farklıdır bilgisayar programlama ve programlarken teorik alanda yaygın olarak kullanılan bazı fonksiyonlar nadiren kullanılmaktadır. Bu makale, bu temel terimlerin bazıları tanımlar.
içindekiler
Dizeler ve diller
Bir katar karakterler sonlu dizisidir. Boş bir dize ile gösterilir . İki dize birleştirme ve ile gösterilir , ya tarafından kısa . Boş dize ile Birleştirilmesi hiç fark etmez: . Dizeleri Birleştirme çağrışımlı: .
Örneğin, .
Bir dil dizeleri sonlu veya sonsuz kümesidir. Vb birlik, kavşak gibi olağan küme işlemleri yanı sıra, birleştirme dillere uygulanabilir: Her iki takdirde ve olan dilleri, onların birleştirme herhangi dize concatenations kümesi olarak tanımlanır ve herhangi bir dize resmen . Yine, birleştirme nokta genellikle kısalık için kullanılmaz.
Dil sadece boş dize oluşan boş dilden ayırt edilmelidir . Herhangi bir değişiklik yapmaz eski ile herhangi bir dil Birleştirilmesi: ikincisi ile birleştirerek ederken, her zaman boş dilini verir: . Dillerin Birleştirme çağrışımlı: .
Örneğin, abbreviating , her üç haneli ondalık sayıların kümesi olarak elde edilir . İstenilen uzunlukta tüm ondalık sayılar kümesi sonsuz dil için bir örnektir.
Bir dize Alfabe
Bir dize alfabe belirli bir dizesinde meydana karakterlerin hepsi kümesidir. Eğer s dizesidir, onun alfabesi ile işaret edilmektedir
Bir dilin alfabesi herhangi dizesinde gerçekleşen tüm karakterlerin kümesidir resmen: .
Örneğin, set dize alfabesi olan ve yukarıda alfabesini oluşturuyor yukarıdaki dili tüm ondalık sayıların dili yanı sıra.
Dize ikamesi
Let L bir olmak dil ve Σ alfabesi olsun. Bir dize ikamesi ya da sadece bir ikame bir eşleme olan f (muhtemelen farklı bir alfabede) dilleri a- karakterleri eşler. Bu durumda, örneğin, bir karakter verdiği bir ∈ Σ bir sahiptir f ( a ) = L a L bir ⊆ Δ * alfabe Δ bazı dildir. Bu eşleme olarak dizeleri için uzatılabilir
- f (ε =) ε
için boş dize ε ve
- f ( sa ) = f ( ler ) f ( a )
dize için s ∈ L ve karakter bir ∈ Σ. Dize değiştirmelerin olarak tüm dillere uzatılabilir
Düzenli diller dize ikamesi altında kapatılır. Yani normal bir dilin alfabesinde her karakter başka düzenli bir dille ikame edilirse, sonuç hala düzenli bir dildir vardır. Benzer şekilde, bağlam-bağımsız diller dize ikamesi altında kapatılır.
Basit bir örnek dönüşüm ön uc (.) Aşağıdaki şekilde örneğin tanımlanabilir büyük harfe:
karakter | dile eşleştirilmiş | düşünce |
---|---|---|
x | f uc ( x ) | |
< A > | {< A >} | Büyük harf kömürü karşılık gelen küçük kömürü map |
< A > | {< A >} | kendisine büyük kömürü map |
< Ss > | {< SS >} | İki Char dizeye hiçbir büyük harf karakter, harita |
<0> | {Ε} | boş bir dizeye haritası haneli |
<!> | {} | Boş dile harita, noktalama korusun |
... | diğer karakter için benzer |
Uzatılması için f uc dizeleri nedeniyle, örneğin var
- f uc (<Strasse ') = {<S>} ⋅ {<T>} ⋅ {<R>} ⋅ {<a>} ⋅ {<SS>} ⋅ {<E>} = {<STRASSE>},
- f uc (<u2 ') = {<u>} ⋅ {ε} = {<U>} ve
- f uc (<Geri! ') = {<G>} ⋅ {<Ç>} ⋅ {} = {}.
Uzatılması için f uc dillere, biz örneğin var
- f uc ({<Strasse>, <u2>, <Go!>}) = {<STRASSE>} ∪ {<U>} ∪ {} = {<STRASSE>, <U>}.
Dize homomorfizması
Bir dize homomorfizması (genellikle bir olarak basitçe ifade homomorfizmasının içinde biçimsel dil teorisine ) her karakter tek bir dize ile değiştirilir şekilde bir dize değiştirmedir. Yani, nerede her karakter için bir dizidir .
Dize homomorfizmleri olan monoid morfizimler üzerinde serbest Monoid boş dize ve koruyarak ikili operasyonu ait karakter dizisi birleştirme . Bir dil Verilen set denir homomorfik görüntü içinde . Ters homomorfik görüntüsü bir dizenin olarak tanımlanır
Bir dilin ters homomorfik görüntüsü ise olarak tanımlanır
Genel olarak, bir var iken
ve
Herhangi bir dil için .
Düzenli dillerin sınıf homomorfizmalarının ve ters homomorfizmalar altında kapalıdır. Benzer şekilde, bağlam-bağımsız diller homomorfizmalarının ve ters homomorfizmalar altında kapatılır.
Bir dize homomorfizması ε içermeyen (veya e-free) eğer olduğu söylenir herkes için bir alfabe ile . Basit tek harfli ikame şifrelere (ε-free) dize homomorfizması örnekleridir.
Bir örnek dize homomorfizmi g uc da benzer tanımlayarak elde edilebilir yukarıda : ikame g uc (<a>) = <A>, ..., g uc (<0> =) ε, ancak izin g uc tanımlanmamış noktalama karakter üzerinde. Ters homomorfik görüntüler için örnekler
- g uc -1 ({<SSS>}) = {<sss>, <SSS>, <SSS>}, çünkü g UC (<sss>) = gr UC (<SSS ') = gr UC (<SSS>) = <SSS> ve
- g uc -1 ({<A>, <bb>}) = {<a>}, çünkü g uc (<a>) = <A>, <bb> tarafından ulaşılamayan süre gr uc .
İkinci dil için, g uc ( g uc -1 ({<A>, <bb>})) = gr UC ({<a>}) = {<a>} ≠ {<A>, <bb>} . Homomorfizmi gr uc o örn <0> s eşleştiren beri, ε-özgür değildir.
Sadece bir karaktere her bir karakteri eşleştiren bir çok basit dize homomorfizmi örnek bir dönüşüm olduğunu EBCDIC için kodlanmış dize ASCII .
Dize projeksiyon
Eğer s bir dize ve bir alfabe olduğunu dize projeksiyon ait s olmayan tüm karakterleri kaldırarak sonuçlanan dizedir . Sanki yazılır . Bu resmen Sağ taraftan karakterlerin çıkarılması ile tanımlanır:
İşte gösterir boş dize . Bir dize çıkıntı esas olarak aynıdır ilişkisel cebir projeksiyon .
Dize projeksiyon terfi edilebilir bir dilin projeksiyon . Bir Verilen biçimsel dil L , onun izdüşümü verilir
Sağ bölüm
Sağ bölüm bir karakter ait a bir dize gelen ın karakteri bölümünün kesilmesidir a dize içinde s Sağ taraftan. Bu şekilde ifade edilir . Dize yoksa bir sağ tarafta, sonuç boş bir dize. Böylece:
Boş dize bölüm alınabilir:
Benzer şekilde, bir alt-kümesi verilen bir Monoid arasında , tek bir şekilde bölüm alt kümesini tanımlayabilir
Sol quotients operasyonlar bir dize solunda yer alarak, benzer şekilde tanımlanabilir.
Hopcroft ve Ullman (1979) bölüm tanımlar L Madde 1 / L 2 dil L 1 ve L 2 aynı alfabe üzerinde L 1 / L 2 = { s | ∃ t ∈ L 2 . St ∈ L 1 }. Bu, yukarıda verilen tanımlamaların bir genelleme değildir, çünkü bir dizi için lar ve farklı karakterler , bir , b , Hopcroft en ve Ullman tanımı {ima sa } / { b yerine} {elde}, {ε}.
Bir tek dil (Hopcroft 1979 Ullman benzer tanımlanan) sol bölüm L 1 ve isteğe bağlı bir dil L 2 olarak bilinen Brzozowski türevi ; Eğer L 2 bir ile temsil edilir normal ifade , yani sol bölüm olabilir.
sözdizimsel ilişki
Bir alt sağ bölüm bir Monoid ait bir tanımlayan denklik ilişkisi olarak adlandırılır, sağ sözdizimsel bir ilişki içinde S . Bu verilir
ilişki sonlu indeksli açıkça ve sadece aile doğru quotients eğer sonlu ise (denklik sınıflarının sınırlı sayıda vardır); eğer vardır
sonlu. Durumda M herhangi bir alfabede kelimelerin monoid olduğunu S sonra ise düzenli dil bir tarafından kabul edilebilir bir dil, yani sonlu durum otomat . Bu yazıda da daha ayrıntılı olarak ele alınmıştır sözdizimsel Monoids .
Sağ iptal
Sağ iptal bir karakteri a bir dize gelen ın karakteri ilk geçtiği çıkarılmasıdır a dizge s sağ taraftan başlanarak. Bu şekilde ifade edilir ve ardışık olarak tanımlanır
Boş dize her zaman iptal edilemez:
Açıkçası, sağ iptal ve projeksiyon gidip :
Önekleri
Bir dize önekleri tüm kümesidir önekleri , belirli bir dil bakımından, bir dizeye:
nerede .
Bir dilin önek kapatılması olduğunu
Örnek:
Bir dil denir önek kapalı ise .
Önek kapatma operatörüdür İdempotent :
Önek ilişki bir olduğunu ikili ilişki öyle ancak ve ancak . Bu ilişki, bir belirli bir örneği önek için .
Ayrıca bakınız
- programlama dillerinin karşılaştırılması (dize fonksiyonları)
- Levi'nin lemma
- Dize (bilgisayar bilimi) - tanım ve dizeleri üzerinde daha temel operasyonların uygulanması
notlar
Referanslar
- Hopcroft, John E .; Ullman, Jeffrey D. (1979). Otomata Teorisi, Dil ve Hesaplamaya Giriş . Okuma, Massachusetts: Addison-Wesley Publishing. ISBN 0-201-02988-X . ZBL 0426.68001 . (Bölüm 3.)