রেগুলার ল্যাঙ্গুয়েজের জন্য পাম্পিং লেমা

class DFA:
    def __init__(self, states, alphabet, transitions, start, accept_states):
        self.states = list(states)
        self.alphabet = set(alphabet)
        self.transitions = transitions
        self.start = start
        self.accept_states = set(accept_states)
        for q in self.states:
            for a in self.alphabet:
                assert (q, a) in self.transitions

    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


# L06-এর "even number of 1s" DFA পুনর্ব্যবহার
even_ones = DFA(
    states=["q0", "q1"], alphabet={"0", "1"},
    transitions={("q0","0"):"q0", ("q0","1"):"q1", ("q1","0"):"q1", ("q1","1"):"q0"},
    start="q0", accept_states={"q0"},
)


def find_pumping_split(dfa, string):
    p = len(dfa.states)
    assert len(string) >= p, "পাম্পিং লেমার জন্য |s| >= p দরকার"
    # state_seq[i] = string[:i] প্রসেস করার পর DFA-র স্টেট
    state_seq = [dfa.start]
    state = dfa.start
    for ch in string[:p]:          # প্রথম p ট্রানজিশন -- p+1টি ভিজিট -- পিজনহোল নিশ্চিত করে একটি পুনরাবৃত্তি
        state = dfa.transitions[(state, ch)]
        state_seq.append(state)

    seen = {}
    first_repeat = None
    for i, st in enumerate(state_seq):
        if st in seen:
            first_repeat = (seen[st], i)   # (প্রথমবার ভিজিট, দ্বিতীয়বার ভিজিট)
            break
        seen[st] = i
    assert first_repeat is not None, "পিজনহোল প্রিন্সিপল অনুযায়ী একটি পুনরাবৃত্তি থাকতেই হবে"

    j, k = first_repeat
    x, y, z = string[:j], string[j:k], string[k:]
    assert len(y) > 0 and len(x) + len(y) <= p and x + y + z == string
    return x, y, z, state_seq


def verify_pumping(dfa, x, y, z, original_string):
    original_result = dfa.accepts(original_string)
    results = {}
    for i in range(4):
        pumped = x + y * i + z
        results[i] = (pumped, dfa.accepts(pumped))
    all_consistent = all(res == original_result for (_, res) in results.values())
    return results, all_consistent


test_string = "1101011"   # |s| = 7 >= p = 2
p = len(even_ones.states)
x, y, z, seq = find_pumping_split(even_ones, test_string)

print(f"DFA states = {even_ones.states}, পাম্পিং লেংথ p = {p}")
print(f"s = {test_string!r} (|s| = {len(test_string)})")
print(f"প্রথম p ট্রানজিশনে ভিজিট করা স্টেট-সিকোয়েন্স: {seq}")
print(f"পিজনহোল-এ পাওয়া split: x={x!r}, y={y!r}, z={z!r}")
print(f"শর্ত (১) |y|>0: {len(y)>0}   শর্ত (২) |xy|<=p: {len(x)+len(y)} <= {p} -> {len(x)+len(y)<=p}")
print(f"মূল স্ট্রিং-এর ফলাফল: accepted = {even_ones.accepts(test_string)}")
print()

results, consistent = verify_pumping(even_ones, x, y, z, test_string)
for i, (pumped, acc) in results.items():
    print(f"  i={i}: xy^{i}z = {pumped!r:15s} -> accepted = {acc}")
print()
print("শর্ত (৩) সব xy^iz-ই মূল ফলাফলের সাথে সঙ্গতিপূর্ণ (পাম্পিং প্রপার্টি সত্য):", consistent)