CFG, bağlamdan bağımsız dilbilgisi anlamına gelir. Belirli bir resmi dilde tüm olası dizi kalıplarını oluşturmak için kullanılan resmi bir dilbilgisidir. Bağlamdan bağımsız dilbilgisi G, dört tanımlama grubuyla şu şekilde tanımlanabilir:
G = (V, T, P, S)
Nerede,
G bir dizi üretim kuralından oluşan dilbilgisidir. Bir dilin dizesini oluşturmak için kullanılır.
T bir terminal sembolünün son kümesidir. Küçük harflerle gösterilir.
İÇİNDE terminal olmayan bir sembolün son kümesidir. Büyük harflerle gösterilir.
P bir dizideki terminal olmayan sembolleri (üretimin sol tarafında) diğer terminal veya terminal olmayan sembollerle (üretimin sağ tarafında) değiştirmek için kullanılan bir dizi üretim kuralıdır.
salman khan'ın yaşı
S dizeyi türetmek için kullanılan başlangıç sembolüdür. Tüm terminal olmayanlar terminal sembolleriyle değiştirilene kadar, terminal olmayan bir şeyi üretimin sağ tarafıyla tekrar tekrar değiştirerek diziyi türetebiliriz.
Örnek 1:
∑= {a} kümesi üzerinde herhangi bir sayıda a'ya sahip dil için CFG'yi oluşturun.
Çözüm:
Yukarıdaki dilin düzenli ifadesi bildiğimiz gibi
r.e. = a*
Normal ifadenin üretim kuralı aşağıdaki gibidir:
S → aS rule 1 S → ε rule 2
Şimdi 'aaaaaa' dizesini türetmek istiyorsak başlangıç sembolleriyle başlayabiliriz.
S aS aaS rule 1 aaaS rule 1 aaaaS rule 1 aaaaaS rule 1 aaaaaaS rule 1 aaaaaaε rule 2 aaaaaa
Orada. = a* bir dizi {ε, a, aa, aaa,.....} dizisi oluşturabilir. Boş bir dizgeye sahip olabiliriz çünkü S bir başlangıç sembolüdür ve kural 2 S → ε değerini verir.
Örnek 2:
Düzenli ifade için bir CFG oluşturun (0+1)*
Çözüm:
dizeyi json nesnesine dönüştür
CFG şu şekilde verilebilir:
Production rule (P): S → 0S | 1S S → ε
Kurallar, başlangıç simgesiyle birlikte 0 ve 1'lerin birleşiminden oluşur. (0+1)* {ε, 0, 1, 01, 10, 00, 11, ....}'ı gösterdiğinden. Bu kümede ε bir dizedir, dolayısıyla kuralda S → ε kuralını ayarlayabiliriz.
Örnek 3:
L = w € (a, b)* dili için bir CFG oluşturun.
Çözüm:
birleştirme sıralaması java
Belirli bir dil için üretilebilecek dize şöyledir: {aacaa, bcb, abcba, bacab, abbcbba, ....}
Dilbilgisi şöyle olabilir:
S → aSa rule 1 S → bSb rule 2 S → c rule 3
Şimdi 'abbcbba' dizesini türetmek istiyorsak başlangıç sembolleriyle başlayabiliriz.
S → aSa S → abSba from rule 2 S → abbSbba from rule 2 S → abbcbba from rule 3
Dolayısıyla bu türden herhangi bir dizi, verilen üretim kurallarından türetilebilir.
Örnek 4:
L = a dili için bir CFG oluşturunNB2nburada n>=1.
Çözüm:
Belirli bir dil için üretilebilecek dize {abb, aabbbb, aaabbbbbb....} şeklindedir.
Dilbilgisi şöyle olabilir:
S → aSbb | abb
Şimdi 'aabbbb' dizesini türetmek istiyorsak başlangıç sembolleriyle başlayabiliriz.
S → aSbb S → aabbbb