রেগুলার ল্যাঙ্গুয়েজের ক্লোজার প্রপার্টি

১ · ক্লোজার প্রপার্টি কী

ক্লোজার প্রপার্টিClosure Propertyএকটি সেট (এখানে: রেগুলার ল্যাঙ্গুয়েজের সংগ্রহ) কোনো একটি অপারেশনের অধীনে "বন্ধ" কি না — অর্থাৎ অপারেশনটি সেটের ভেতরের উপাদানে প্রয়োগ করলে ফলাফল সবসময় সেটের ভেতরেই থাকে কি না। হলো প্রশ্ন — যদি $L_1$ এবং $L_2$ রেগুলার ল্যাঙ্গুয়েজ হয়, তাহলে এদের উপর একটি নির্দিষ্ট অপারেশন (যেমন union) প্রয়োগ করলে ফলাফলও কি নিশ্চিতভাবে রেগুলার? এই পাঠ দেখাবে — হ্যাঁ, পাঁচটি গুরুত্বপূর্ণ অপারেশনের অধীনেই রেগুলার ল্যাঙ্গুয়েজ ক্লোজড, এবং প্রতিটির জন্য একটি গঠনমূলক (constructive) প্রমাণ আছে — অর্থাৎ প্রমাণ নিজেই বলে দেয় কীভাবে ফলাফলের DFA/regex বানাতে হবে।

২ · ইউনিয়ন, কনক্যাটেনেশন, ক্লিন স্টার — regex দিয়ে সরাসরি

L11-এ regex-এর ফরমাল সংজ্ঞা মনে করুন — regex $R \cup S$, $RS$, ও $R^*$ নিজেরাই বৈধ regex। তাই যদি $L_1 = L(R)$ এবং $L_2 = L(S)$ রেগুলার হয় (অর্থাৎ কোনো regex দিয়ে বর্ণিত হয়), তাহলে —

• ইউনিয়ন: $L_1 \cup L_2 = L(R \cup S)$ — সরাসরি regex union, তাই রেগুলার।
• কনক্যাটেনেশন: $L_1 L_2 = L(RS)$ — সরাসরি regex concatenation, তাই রেগুলার।
• ক্লিন স্টার: $L_1^* = L(R^*)$ — সরাসরি regex star, তাই রেগুলার।

এই তিনটির প্রমাণ আসলে নতুন কিছু নয় — L11-এর ক্লিনির থিওরেম-প্রমাণিত regex ⇔ ফাইনাইট অটোমাটা ইকুইভ্যালেন্স সরাসরি পুনর্ব্যবহার করছি মাত্র।

৩ · কমপ্লিমেন্ট — DFA-ভিত্তিক ভিন্ন প্রমাণ

কমপ্লিমেন্টের জন্য regex-ভিত্তিক প্রমাণ সহজ নয়, কিন্তু DFA-ভিত্তিক প্রমাণ চমৎকার সহজ। যদি $L$ রেগুলার হয়, তাহলে L06-এর সংজ্ঞা অনুযায়ী একটি টোটাল DFA $M = (Q, \Sigma, \delta, q_0, F)$ থাকবে যার $L(M) = L$। এখন শুধু accept ও non-accept স্টেট উল্টে দিন —

$$\overline{M} = (Q, \Sigma, \delta, q_0, Q - F)$$

$\overline{M}$ ঠিক সেই স্ট্রিংগুলোই accept করবে যেগুলো $M$ reject করত — অর্থাৎ $L(\overline{M}) = \overline{L} = \Sigma^* - L$। এই প্রমাণের একটি সূক্ষ্ম কিন্তু জরুরি শর্ত আছে — $\delta$ অবশ্যই টোটাল হতে হবে (L06-এ যে রিকোয়্যারমেন্ট দেওয়া হয়েছিল)। যদি DFA-টি আংশিক (partial) হতো — কিছু স্ট্রিং-এ কোনো ট্রানজিশনই না থাকত — তাহলে accept/reject উল্টে দিলে সেই "কোনো ট্রানজিশন নেই" অবস্থার স্ট্রিংগুলো ভুলভাবে reject-ই থেকে যেত, কমপ্লিমেন্টে সেগুলোর accept হওয়ার কথা থাকা সত্ত্বেও।

৪ · ইন্টারসেকশন — প্রোডাক্ট কনস্ট্রাকশন

ইন্টারসেকশনের জন্য একটি সুন্দর, গঠনমূলক কৌশল আছে — প্রোডাক্ট কনস্ট্রাকশন। ধরুন $M_1=(Q_1,\Sigma,\delta_1,q_1,F_1)$ এবং $M_2=(Q_2,\Sigma,\delta_2,q_2,F_2)$ যথাক্রমে $L_1, L_2$-এর DFA। একটি নতুন DFA বানান যা $M_1$ ও $M_2$-কে একসাথে, লকস্টেপে চালায় —

$$M_\cap = (Q_1 \times Q_2,\ \Sigma,\ \delta,\ (q_1,q_2),\ F_1 \times F_2)$$ $$\text{যেখানে } \delta((p,q), a) = (\delta_1(p,a),\ \delta_2(q,a))$$

$M_\cap$-এর প্রতিটি স্টেট আসলে $M_1$ ও $M_2$-এর স্টেটের একটি জোড়া — এবং accept ঘটে শুধু তখনই যখন দুটো কম্পোনেন্ট স্টেটই accepting ($F_1 \times F_2$)। ফলাফল সরাসরি $L_1 \cap L_2$ recognize করে। একই স্টেট-স্পেস $Q_1 \times Q_2$ ব্যবহার করে accept রুল $F_1 \times F_2$-এর বদলে "কমপক্ষে একটি accepting" করলে ঠিক এই একই কনস্ট্রাকশন ইউনিয়নও দেয় — একটিই কাঠামো, দুটো ব্যবহার।

৫ · কোডে যাচাই — complement_dfa ও product_dfa

নিচের কোড সেলে L06-এর DFA ক্লাস পুনর্ব্যবহার করে দুটো real ফাংশন লেখা হলো — complement_dfa (accept/non-accept স্টেট swap, টোটালিটি assert-সহ) এবং product_dfa (mode="intersection" বা "union")। দুটো ছোট উদাহরণ DFA — "even length" (জোড় দৈর্ঘ্য) এবং "contains 01" (উপস্ট্রিং হিসেবে "01" আছে) — নিয়ে তাদের প্রোডাক্ট DFA-র ফলাফল সরাসরি প্রত্যাশিত AND/OR শর্তের বিপরীতে ভেরিফাই করা হচ্ছে।

class DFA:
    def __init__(self, states, alphabet, transitions, start, accept_states):
        self.states = set(states)
        self.alphabet = set(alphabet)
        self.transitions = transitions          # dict (state, symbol) -> state
        self.start = start
        self.accept_states = set(accept_states)
        # টোটালিটি -- প্রতিটি (state, symbol) জোড়ার জন্য ট্রানজিশন থাকতেই হবে
        for q in self.states:
            for a in self.alphabet:
                assert (q, a) in self.transitions, f"delta not total at ({q},{a})"

    def run(self, s):
        state = self.start
        for ch in s:
            state = self.transitions[(state, ch)]
        return state

    def accepts(self, s):
        return self.run(s) in self.accept_states


def complement_dfa(dfa):
    # শুধু accept/non-accept স্টেট উল্টে দিলেই কমপ্লিমেন্ট -- DFA টোটাল হওয়া আবশ্যক
    return DFA(dfa.states, dfa.alphabet, dfa.transitions, dfa.start,
               dfa.states - dfa.accept_states)


def product_dfa(dfa1, dfa2, mode="intersection"):
    assert dfa1.alphabet == dfa2.alphabet
    states = [(q1, q2) for q1 in dfa1.states for q2 in dfa2.states]
    transitions = {}
    for (q1, q2) in states:
        for a in dfa1.alphabet:
            transitions[((q1, q2), a)] = (dfa1.transitions[(q1, a)], dfa2.transitions[(q2, a)])
    start = (dfa1.start, dfa2.start)
    if mode == "intersection":
        accept_states = [(q1, q2) for (q1, q2) in states
                          if q1 in dfa1.accept_states and q2 in dfa2.accept_states]
    else:  # "union"
        accept_states = [(q1, q2) for (q1, q2) in states
                          if q1 in dfa1.accept_states or q2 in dfa2.accept_states]
    return DFA(states, dfa1.alphabet, transitions, start, accept_states)


# DFA1: জোড় দৈর্ঘ্যের স্ট্রিং (even length)
even_len = DFA(
    states={"e", "o"}, alphabet={"0", "1"},
    transitions={("e","0"):"o", ("e","1"):"o", ("o","0"):"e", ("o","1"):"e"},
    start="e", accept_states={"e"},
)

# DFA2: "01" উপস্ট্রিং হিসেবে আছে
contains01 = DFA(
    states={"q0", "q1", "q2"}, alphabet={"0", "1"},
    transitions={
        ("q0","0"):"q1", ("q0","1"):"q0",
        ("q1","0"):"q1", ("q1","1"):"q2",
        ("q2","0"):"q2", ("q2","1"):"q2",
    },
    start="q0", accept_states={"q2"},
)

# কমপ্লিমেন্ট যাচাই -- L(contains01) আর L(complement) সবসময় বিপরীত হওয়া উচিত
comp = complement_dfa(contains01)
test_strings = ["", "0", "1", "01", "10", "0011", "1111", "0101",
                 "0000", "101", "010", "1001", "11011", "0110"]
for s in test_strings:
    assert contains01.accepts(s) != comp.accepts(s)
print("কমপ্লিমেন্ট চেক পাস: সব টেস্ট স্ট্রিং-এ contains01 আর তার complement বিপরীত ফলাফল দিচ্ছে")

inter = product_dfa(even_len, contains01, mode="intersection")
uni = product_dfa(even_len, contains01, mode="union")

print()
print(f"{'string':10s} even_len contains01 -> AND(expect)  OR(expect)")
all_ok = True
for s in test_strings:
    e, c = even_len.accepts(s), contains01.accepts(s)
    i, u = inter.accepts(s), uni.accepts(s)
    exp_i, exp_u = (e and c), (e or c)
    if i != exp_i or u != exp_u:
        all_ok = False
    print(f"{s!r:10s} {str(e):8s} {str(c):10s} -> {str(i):5s}({str(exp_i):5s})  {str(u):5s}({str(exp_u):5s})")

print()
print("প্রোডাক্ট DFA-র ফলাফল সব টেস্ট স্ট্রিং-এ প্রত্যাশিত AND/OR-এর সাথে মিলছে:", all_ok)