অটোমাটা থিওরি বাস্তবে — কম্পাইলার ও টেক্সট প্রসেসিং

# অংশ ১ -- এই কোর্সের তত্ত্ব ও বাস্তব প্রয়োগের সংশ্লেষণ টেবিল

applications = {
    "লেক্সিক্যাল অ্যানালাইসিস": {
        "theoretical_foundation": "DFA (M2), মিনিমাইজেশন থিওরেম (M3)",
        "this_courses_lesson_reference": "L06, L15-L16",
        "practical_benefit": "দ্রুত, সিঙ্গল-পাস, প্রেডিক্টেবল টোকেনাইজিং",
    },
    "পার্সিং": {
        "theoretical_foundation": "CNF, PDA-CFG ইকুইভ্যালেন্স, DCFL",
        "this_courses_lesson_reference": "L20, L24, L25",
        "practical_benefit": "LL/LR পার্সার -- নির্ভরযোগ্য, ব্যাকট্র্যাকিং-মুক্ত পার্সিং",
    },
    "টেক্সট সার্চ": {
        "theoretical_foundation": "ক্লিনির থিওরেম -- regex ⇔ ফাইনাইট অটোমাটা",
        "this_courses_lesson_reference": "L10, L11",
        "practical_benefit": "লিনিয়ার-টাইম প্যাটার্ন ম্যাচিং",
    },
}

print(f"{'বাস্তব প্রয়োগ':22s} | {'তাত্ত্বিক ভিত্তি':38s} | {'এই কোর্সের পাঠ'}")
print("-" * 90)
for app, info in applications.items():
    print(f"{app:22s} | {info['theoretical_foundation']:38s} | {info['this_courses_lesson_reference']}")

print()

# অংশ ২ -- L10-L11-এর regex-to-NFA-to-DFA পাইপলাইন পুনর্ব্যবহার করে একটি সত্যিকারের টেক্সট-সার্চ টুল

class Counter:
    def __init__(self):
        self.n = 0
    def new_state(self):
        s = self.n
        self.n += 1
        return s

def build_nfa(ast, counter, transitions):
    # regex AST-এর প্রতিটি recursive case-এর জন্য থম্পসন-স্টাইল ε-NFA fragment তৈরি (L11)
    kind = ast[0]
    if kind == 'eps':
        s, a = counter.new_state(), counter.new_state()
        transitions.setdefault(s, []).append((None, a))
        return s, a
    if kind == 'sym':
        ch = ast[1]
        s, a = counter.new_state(), counter.new_state()
        transitions.setdefault(s, []).append((ch, a))
        return s, a
    if kind == 'union':
        s1, a1 = build_nfa(ast[1], counter, transitions)
        s2, a2 = build_nfa(ast[2], counter, transitions)
        s, a = counter.new_state(), counter.new_state()
        transitions.setdefault(s, []).extend([(None, s1), (None, s2)])
        transitions.setdefault(a1, []).append((None, a))
        transitions.setdefault(a2, []).append((None, a))
        return s, a
    if kind == 'concat':
        s1, a1 = build_nfa(ast[1], counter, transitions)
        s2, a2 = build_nfa(ast[2], counter, transitions)
        transitions.setdefault(a1, []).append((None, s2))
        return s1, a2
    if kind == 'star':
        s1, a1 = build_nfa(ast[1], counter, transitions)
        s, a = counter.new_state(), counter.new_state()
        transitions.setdefault(s, []).extend([(None, s1), (None, a)])
        transitions.setdefault(a1, []).extend([(None, s1), (None, a)])
        return s, a
    raise ValueError("অজানা regex node")

def regex_to_nfa(ast):
    counter = Counter()
    transitions = {}
    start, accept = build_nfa(ast, counter, transitions)
    return {'start': start, 'accept': {accept}, 'transitions': transitions}

def epsilon_closure(transitions, states):
    # L09-এর ফিক্সড-পয়েন্ট ε-closure অ্যালগরিদম
    stack = list(states)
    closure = set(states)
    while stack:
        s = stack.pop()
        for (sym, t) in transitions.get(s, []):
            if sym is None and t not in closure:
                closure.add(t)
                stack.append(t)
    return closure

def subset_construction(nfa, alphabet):
    # L08-এর সাবসেট কনস্ট্রাকশন -- NFA-কে সমতুল্য DFA-তে রূপান্তর
    trans = nfa['transitions']
    start_set = frozenset(epsilon_closure(trans, {nfa['start']}))
    dfa_states = {start_set}
    dfa_transitions = {}
    unmarked = [start_set]
    accept_nfa = nfa['accept']
    while unmarked:
        S = unmarked.pop()
        for ch in alphabet:
            move = set()
            for s in S:
                for (sym, t) in trans.get(s, []):
                    if sym == ch:
                        move.add(t)
            if not move:
                continue
            T = frozenset(epsilon_closure(trans, move))
            dfa_transitions[(S, ch)] = T
            if T not in dfa_states:
                dfa_states.add(T)
                unmarked.append(T)
    dfa_accept = {S for S in dfa_states if S & accept_nfa}
    return {'start': start_set, 'transitions': dfa_transitions, 'accept': dfa_accept}

def dfa_accepts(dfa, string):
    state = dfa['start']
    for ch in string:
        key = (state, ch)
        if key not in dfa['transitions']:
            return False
        state = dfa['transitions'][key]
    return state in dfa['accept']

def search_pattern(dfa, text):
    # প্রতিটি সম্ভাব্য শুরু-অবস্থান থেকে DFA দিয়ে ম্যাচ খোঁজা -- বাস্তব regex ইঞ্জিনের core loop-এর সরলীকৃত সংস্করণ
    matches = []
    n = len(text)
    for i in range(n):
        state = dfa['start']
        for j in range(i, n):
            key = (state, text[j])
            if key not in dfa['transitions']:
                break
            state = dfa['transitions'][key]
            if state in dfa['accept']:
                matches.append((i, j + 1, text[i:j + 1]))
    return matches

# regex (a|b)*a -- L10-এর ঠিক একই উদাহরণ, "শেষে a"-যুক্ত a/b স্ট্রিং
regex_ast = ('concat', ('star', ('union', ('sym', 'a'), ('sym', 'b'))), ('sym', 'a'))
nfa = regex_to_nfa(regex_ast)
dfa = subset_construction(nfa, ['a', 'b'])

# পুরো-স্ট্রিং অ্যাকসেপ্টেন্স যাচাই -- L10-এর বর্ণনার সাথে মিলছে কি না
for s in ["", "a", "b", "aab", "bba"]:
    expected = len(s) > 0 and s[-1] == 'a'
    print(f"পুরো-স্ট্রিং: {s!r:6s} -> DFA={dfa_accepts(dfa, s)}  (প্রত্যাশিত={expected})")
    assert dfa_accepts(dfa, s) == expected

# এবার আসল সার্চ -- একটি দীর্ঘ টেক্সটে প্যাটার্নের সব ম্যাচ খুঁজে বের করা
text = "baabab"
matches = search_pattern(dfa, text)
print(f"\nটেক্সট {text!r}-এ '(a|b)*a' প্যাটার্নের সব ম্যাচ:")
for start, end, matched in matches:
    print(f"  পজিশন [{start},{end}) -> {matched!r}")
print(f"\nমোট ম্যাচ পাওয়া গেছে: {len(matches)}টি")