Otomata teorisi, bilgisayar bilimi ve matematiğin teorik bir dalıdır. Soyut makinelerin ve bu makineleri kullanarak çözülebilecek hesaplama problemlerinin incelenmesidir. Soyut makineye otomata denir. Otomata teorisini geliştirmenin ardındaki temel motivasyon, ayrık sistemlerin dinamik davranışını tanımlamaya ve analiz etmeye yönelik yöntemler geliştirmekti.
Bu otomat durumlar ve geçişlerden oluşur. Durum tarafından temsil edilir daireler , ve Geçişler tarafından temsil edilir oklar .
Otomata, girdi olarak bir dizi alan ve bu girdinin sonlu sayıda durumdan geçerek son duruma girebilen türde bir makinedir.
Otomatlarda önemli olan ve sıklıkla kullanılan temel terminolojiler vardır:
Semboller:
Semboller herhangi bir harf, alfabe veya herhangi bir resim olabilen bir varlık veya bireysel nesnelerdir.
Örnek:
1, a, b, #
Alfabeler:
Alfabeler sınırlı sayıda sembolden oluşur. ∑ ile gösterilir.
Örnekler:
∑ = {a, b} ∑ = {A, B, C, D} ∑ = {0, 1, 2} ∑ = {0, 1, ....., 5] ∑ = {#, β, Δ} Sicim:
Alfabedeki sembollerin sınırlı bir koleksiyonudur. Dize w ile gösterilir.
Örnek 1:
Eğer ∑ = {a, b} ise, ∑'den üretilebilecek çeşitli diziler şunlardır: {ab, aa, aaa, bb, bbb, ba, aba.....}.
- Sıfır sembol oluşumuna sahip bir dize, boş dize olarak bilinir. ε ile temsil edilir.
- Bir w dizesindeki sembollerin sayısına dizenin uzunluğu denir. |w| ile gösterilir.
Örnek 2:
w = 010 Number of Sting |w| = 3
Dil:
Dil, uygun dizelerden oluşan bir koleksiyondur. Σ üzerinden oluşturulan bir dil olabilir Sonlu veya Sonsuz .
Örnek 1
L1 = {Set of string of length 2} = {aa, bb, ba, bb} <strong>Finite Language</strong> Örnek: 2
L2 = {Set of all strings starts with 'a'} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>