Yazan: Şadi Evren ŞEKER
Bir dilde tanımlı olan ve o dildeki alfabenin üyesi olan semboller ile üretilmiş her dizginin alt dizgisi olabilir. Alt dizgi o dizginin belirli bir kısmına verilen isimdir. Buna göre örneğin boş dizgi her dizginin alt dizgisidir.
Örneğin bir dildeki alfabe aşağıdaki şekilde tanımlı olsun:
∑1 = {0,1}
Buna göre dilimizde sadece “0″ ve “1″ sembolleri tanımlı demektir. Bu dilde örneğin w1=0 veya w2=10101011010 gibi bir dizgi elde etmek mümkündür.
Bir dizginin belirli bir kımını içeren dizgiye ise alt dizgi adı verilir. Örneğin w3=1011 dizgisi w2 dizgisinin bir altdizgisidir.