ফিনাইট স্টেট অটোমাটা

১ · DFA-র আনুষ্ঠানিক সংজ্ঞা

একটি Deterministic Finite Automaton (DFA)DFAএকটি গাণিতিক মডেল যা এক-এক করে ইনপুট সিম্বল পড়ে, প্রতিটি সিম্বলে একটি নির্দিষ্ট (deterministic) নিয়মে এক স্টেট থেকে আরেক স্টেটে যায়, এবং শেষে একটি accepting স্টেটে থাকলে ইনপুটটি "গ্রহণ" করে। একটি ৫-টাপল $(Q, \Sigma, \delta, q_0, F)$ দিয়ে সংজ্ঞায়িত —

২ · Worked উদাহরণ — জোড় সংখ্যক 1 চেনা

লক্ষ্য: এমন একটি DFA বানানো যা শুধু সেই বাইনারি স্ট্রিং-গুলো গ্রহণ করবে যেখানে 1-এর সংখ্যা জোড় (even) — শূন্যও একটি জোড় সংখ্যা হিসেবে গণ্য, তাই খালি স্ট্রিং ও সব-0 স্ট্রিং-ও গ্রহণযোগ্য।

ধাপে-ধাপে রান — ইনপুট "1010": শুরু $q_{even}$ → পড়ি 1 → $q_{odd}$ → পড়ি 0 → $q_{odd}$ → পড়ি 1 → $q_{even}$ → পড়ি 0 → $q_{even}$। শেষ স্টেট $q_{even} \in F$ — গ্রহণ (accept)। সত্যিই, "1010"-এ দুটি 1 আছে — জোড়।

ইনপুট "111": $q_{even} \to q_{odd} \to q_{even} \to q_{odd}$। শেষ স্টেট $q_{odd} \notin F$ — প্রত্যাখ্যান (reject)। "111"-এ তিনটি 1 — বিজোড়, ঠিক আছে।

delta = {
    ('q_even', '0'): 'q_even',
    ('q_even', '1'): 'q_odd',
    ('q_odd', '0'): 'q_odd',
    ('q_odd', '1'): 'q_even',
}

def run_dfa(s):
    state = 'q_even'  # start state q0
    for ch in s:
        state = delta[(state, ch)]
    return state == 'q_even'  # F = {q_even}

for s in ["1010", "111", "0", "11011"]:
    ones = s.count("1")
    result = "accept (গ্রহণযোগ্য)" if run_dfa(s) else "reject (প্রত্যাখ্যাত)"
    print(f"'{s}' -> {ones}টি 1 -> {result}")

৩ · DFA-র "ভাষা" (Language)

একটি DFA যে ভাষা চেনে (recognize করে) তা হলো সেই সব স্ট্রিং-এর সেট যা $q_0$ থেকে শুরু করে চালালে $F$-এর কোনো স্টেটে গিয়ে থামে। উপরের DFA-র ভাষা হলো "জোড় সংখ্যক 1 সম্বলিত সব বাইনারি স্ট্রিং" — একটি অসীম সেট (infinite set), কিন্তু মাত্র দুটি স্টেট দিয়ে সসীমভাবে (finitely) বর্ণনা করা গেছে।

৪ · NFA — সংক্ষিপ্ত পরিচিতি

একটি NFA (Nondeterministic Finite Automaton)NFADFA-র মতোই, কিন্তু একটি স্টেট থেকে একই সিম্বলে একাধিক পরবর্তী স্টেটে যাওয়া যায় (বা কোনোটিতেই না) — "nondeterministic" আচরণ। -এ একটি স্টেট থেকে একই ইনপুটে একাধিক (বা শূন্য) পরবর্তী স্টেটে যাওয়া সম্ভব। বিস্ময়করভাবে, এই বাড়তি নমনীয়তা গণনাশক্তি বাড়ায় না — প্রতিটি NFA-র জন্য একটি সমতুল্য DFA আছে (subset construction পদ্ধতিতে বানানো যায়, এখানে বিস্তারিত ডেরাইভ করব না)। তাই DFA ও NFA ঠিক একই শ্রেণীর ভাষা চেনে — regular languages, যা L35-এ আরও বিস্তারিত দেখব।