এই পর্বে যা শিখবেন
- যেকোনো regex-কে syntax tree-তে ভেঙে Thompson-এর ছয় নিয়মে ধাপে ধাপে ε-NFA বানানো
- Structural induction দিয়ে নির্মাণটির সঠিকতা আর আকারের সীমা প্রমাণ করা
- ε-closure ধরে NFA-টিকে একটি string-এ চালানো, আর subset construction-এ DFA-তে নেওয়া
- Star-এর শর্টকাট কেন ভুল, তা একটি পাল্টা-উদাহরণ দিয়ে দেখানো
- নিজের নির্মাণকে Python-এর
reআর automata-lib-এর সঙ্গে brute force-এ মেলানো
১ · কেন regex থেকে যন্ত্র — বাজারঘরের validator
বাজারঘরের admin panel-এ একজন কর্মী নতুন অফারের কোডের নিয়ম লেখেন একটি regular expression দিয়ে, যেমন “BG- তারপর চারটি অঙ্ক”। কিন্তু সার্ভার regex “বোঝে” না; সার্ভার শুধু একটি program চালাতে পারে, যা অক্ষর এক এক করে পড়ে আর একটি সিদ্ধান্ত দেয়। অর্থাৎ লেখা নিয়মটিকে একটি যন্ত্রে বদলাতে হবে। কোন যন্ত্র? পর্ব ০৭ থেকে আপনি জানেন, অক্ষর পড়ে সিদ্ধান্ত দেওয়ার সবচেয়ে সরল যন্ত্র একটি finite automaton. এই পর্বের প্রশ্ন: যেকোনো regex থেকে যন্ত্রিকভাবে, কোনো চতুরতা ছাড়াই, একটি সঠিক automaton কীভাবে বানানো যায়?
উত্তরটি এসেছে Ken Thompson-এর ১৯৬৮ সালের একটি ছোট প্রবন্ধ থেকে, আর এর মূল কৌশল খুব সাধারণ: regex যেভাবে ছোট অংশ জুড়ে বড় হয়, যন্ত্রটিও ঠিক সেভাবে ছোট টুকরো জুড়ে বড় হবে। জোড়ার আঠা হলো ε-তীর, যে তীর ধরে কোনো চিহ্ন না পড়েই এক state থেকে আরেক state-এ যাওয়া যায়।
পুরান ঢাকার একটি বিয়েবাড়ির প্যান্ডেল বানানোর কথা ভাবুন। কারিগররা আগে থেকে তৈরি কয়েক ধরনের ফ্রেম আনেন: একটি সোজা খুঁটি, একটি দরজা, একটি খিলান। প্রতিটি ফ্রেমের ঠিক একটি ঢোকার মুখ আর একটি বের হওয়ার মুখ। বড় প্যান্ডেল বানাতে তাঁরা ফ্রেমের ভেতরে হাত দেন না; শুধু এক ফ্রেমের বের হওয়ার মুখ পরের ফ্রেমের ঢোকার মুখে ফাঁকা একটি করিডোর দিয়ে জুড়ে দেন। Thompson construction-এ প্রতিটি NFA-টুকরো একটি ফ্রেম, শুরু আর accepting state তার দুই মুখ, আর ε-তীর সেই ফাঁকা করিডোর, যেখানে হাঁটতে কোনো চিহ্ন “খরচ” হয় না।
এই পর্বে তিনটি পূর্ববর্তী ধারণা লাগবে, প্রতিটি এক লাইনে মনে করিয়ে দিই। প্রথমত, regex-এর formal সংজ্ঞা (পর্ব ১৩): Σ-এর ওপর ∅, ε আর প্রতিটি a ∈ Σ হলো regex; R1, R2 regex হলে (R1 ∪ R2), (R1R2) আর (R1)∗-ও regex. Precedence: star সবচেয়ে আগে, তারপর concatenation, শেষে union; তাই ab∗ ∪ c মানে (a(b∗)) ∪ c. বইভেদে union-কে “+” লেখা হয়, আর বাস্তব tool-এ “|”; এই পৃষ্ঠার কোডেও “|”. দ্বিতীয়ত, NFA (পর্ব ০৯): অন্তত একটি পথ accepting state-এ শেষ হলেই string গৃহীত। তৃতীয়ত, ε-NFA (পর্ব ১১): NFA-তে ε-তীরও থাকতে পারে।
এই পর্বের notation: ε-NFA N = (Q, Σ, δ, q0, F), যেখানে δ : Q × Σε → P(Q) আর Σε = Σ ∪ {ε}. ε হলো ফাঁকা string (কিছু বইয়ে λ). একটি পথের label মানে পথের তীরগুলোর চিহ্ন পরপর জুড়ে পাওয়া string, যেখানে ε-তীর কিছুই যোগ করে না। p থেকে q-তে label w-এর একটি পথ থাকলে লেখা হবে p ⇝w q. তাহলে w ∈ L(N) ⇔ কোনো f ∈ F-এর জন্য q0 ⇝w f. একটি state-সেট S-এর ε-closure E(S) = S থেকে শুধু ε-তীর ধরে পৌঁছানো সব state, S নিজেও (বিস্তারিত পর্ব ১১-এ)। State-এর নাম q0, q1, … ল্যাটিন অক্ষরে।
এই পর্বের লক্ষ্য একটি উপপাদ্যের অর্ধেক। Kleene-এর উপপাদ্য বলে: একটি language কোনো regex দিয়ে বর্ণনা করা যায় ⇔ কোনো finite automaton সেটি চেনে। এখানে প্রমাণ হবে “⇒” দিক: প্রতিটি regex R-এর জন্য একটি ε-NFA N(R) আছে যাতে L(N(R)) = L(R). উল্টো দিক, automaton থেকে regex, পর্ব ১৫-এর বিষয়। দুই দিক মিলিয়ে regex, NFA আর DFA ঠিক একই শ্রেণির language বর্ণনা করে: regular language. ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৭৪-এ নির্মাণটির নিয়মগুলো এক টেবিলে দেখেছেন; এখানে প্রতিটি নিয়ম, তার প্রমাণ আর তার ফাঁদগুলো পুরোটা দেখা হবে।
২ · ছয়টি নিয়ম — তিন ভিত্তি আর তিন জোড়া
প্রথম কাজ regex-কে একটি syntax tree-তে ভাঙা: পাতায় চিহ্ন, ε বা ∅, আর ভেতরের প্রতিটি node-এ একটি operator: ∪, concatenation (·) বা ∗. বন্ধনী আর precedence গাছের আকারেই ধরা থাকে। যেমন (a ∪ b)∗abb-এর গাছের মূলে একটি concatenation, যার বাঁ দিকে আরও concatenation, আর সবচেয়ে গভীরে (a ∪ b)∗. এরপর গাছের নিচ থেকে ওপরে উঠতে উঠতে প্রতিটি node-এর জন্য একটি NFA-টুকরো বানানো হয়।
Σ-এর ওপর প্রতিটি regex R-এর জন্য ε-NFA N(R), যার একটি শুরু s আর একটি accepting state f, R-এর গঠনের ওপর recursion-এ সংজ্ঞায়িত:
ভিত্তি ১, R = ∅: দুটি নতুন state s, f; কোনো তীর নেই।
ভিত্তি ২, R = ε: দুটি নতুন state s, f আর একটি তীর s –ε→ f.
ভিত্তি ৩, R = a (a ∈ Σ): দুটি নতুন state s, f আর একটি তীর s –a→ f.
Union, R = R1 ∪ R2: N(R1) (শুরু s1, শেষ f1) আর N(R2) (s2, f2) নিন, state-নাম আলাদা রেখে। দুটি নতুন state s, f; চারটি ε-তীর: s → s1, s → s2, f1 → f, f2 → f. শুধু f accepting.
Concatenation, R = R1R2: একটি ε-তীর f1 → s2. নতুন state নেই; শুরু s1, শেষ f2.
Star, R = R1∗: দুটি নতুন state s, f; চারটি ε-তীর: s → s1, s → f (শূন্য বার), f1 → s1 (আবার একবার), f1 → f (এখানেই শেষ)।
প্রতিটি নিয়মের পেছনে একটি সহজ অর্থ আছে। Union-এ যন্ত্র শুরুতেই অনুমান করে কোন শাখায় যাবে, তারপর যে শাখা শেষ হয় সেখান থেকে সাধারণ শেষ f-এ চলে আসে। Concatenation-এ প্রথম অংশ মেলা শেষ হলে বিনা খরচে দ্বিতীয় অংশের শুরুতে যাওয়া যায়। Star-এ দুটি বিকল্প পথ: সরাসরি s → f, যা ε-কে গ্রহণ করে, আর ভেতরের যন্ত্রটি একবার পার হয়ে f1 থেকে হয় আবার s1-এ ফেরা, নয়তো বের হয়ে যাওয়া।
Thompson-এর নিয়ম — ভিত্তি, union, concatenation আর star
দুই দাগের বৃত্ত accepting state. ধূসর ডট-দাগের বাক্স একটি আগে বানানো টুকরো N(R1) বা N(R2); তার ভেতরের f1, f2 জোড়ার পর আর accepting থাকে না।
ছবিটি দেখে চারটি ধর্ম লক্ষ করুন, কারণ প্রমাণ এদের ওপরই দাঁড়াবে। (১) প্রতিটি টুকরোর ঠিক একটি accepting state f, আর f ≠ s. (২) শুরু s-এ কোনো তীর ঢোকে না। (৩) শেষ f থেকে কোনো তীর বের হয় না। (৪) প্রতিটি state থেকে বড়জোর দুটি তীর বের হয়, আর যে state থেকে একটি চিহ্নের তীর বের হয়, তার আর কোনো তীর নেই। অংশ ৬-এ দেখবেন, (২) আর (৩) ভাঙলেই নির্মাণটি ভুল হতে পারে।
৩ · ধাপে ধাপে — (a ∪ b)∗abb-এর NFA
Σ = {a, b}-এর ওপর (a ∪ b)∗abb মানে “abb দিয়ে শেষ হওয়া সব string”, যেমন abb, aabb, babb, ababb. এটি compiler আর automata পাঠ্যবইয়ের একটি ক্লাসিক উদাহরণ। নিচের stepper গাছের নিচ থেকে ওপরে উঠে NFA-টি বানায়; state-এর নম্বর দেওয়া হয়েছে যে ক্রমে তারা তৈরি হয়।
1syntax tree বানানো2পাতা a আর b3a ∪ b4(a ∪ b)∗5· a6· b7· b (মূল node)
| নতুন state | |
| নতুন তীর | |
| টুকরো (শুরু, শেষ) | |
| মোট state / তীর |
- গাছ। Precedence অনুযায়ী star সবচেয়ে কাছে বাঁধে, তারপর concatenation বাঁ থেকে ডানে। তাই মূল node শেষ concatenation, আর সবচেয়ে গভীরে a ∪ b. নির্মাণ চলবে postorder-এ: আগে সন্তান, পরে বাবা-node.
- দুই পাতা। a-এর জন্য q0 –a→ q1, b-এর জন্য q2 –b→ q3. প্রতিটি ভিত্তি-টুকরোয় দুটি state আর একটি তীর।
- Union. নতুন শুরু q4 আর নতুন শেষ q5. q4 থেকে ε-তে দুই শাখার শুরু q0, q2; দুই শাখার শেষ q1, q3 থেকে ε-তে q5. এখন q1, q3 আর accepting নয়।
- Star. নতুন q6, q7. চারটি ε: q6 → q4 (ভেতরে ঢোকা), q6 → q7 (শূন্য বার), q5 → q4 (আবার একবার), q5 → q7 (বের হওয়া)। টুকরোটি এখন (a ∪ b)∗, শুরু q6, শেষ q7.
- Concatenation-এ a. প্রথমে পাতা a: q8 –a→ q9. তারপর জোড়া: q7 –ε→ q8. নতুন state শুধু পাতার দুটি; জোড়ায় কোনো state লাগে না। টুকরোর শুরু q6, শেষ q9.
- Concatenation-এ b. পাতা q10 –b→ q11, জোড়া q9 –ε→ q10. মোট ১২টি state, ১৪টি তীর।
- শেষ b. পাতা q12 –b→ q13, জোড়া q11 –ε→ q12. পুরো NFA-তে ১৪টি state আর ১৬টি তীর, যার ১১টি ε. শুরু q6, একমাত্র accepting state q13.
শুরু state-এর নাম q6 দেখে অবাক হবেন না: নম্বরগুলো শুধু তৈরির ক্রম। পুরো যন্ত্রটি নিচের ছবিতে। উপরের অংশ (a ∪ b)∗, যেখানে q5 → q4 তীর লুপ আর q6 → q7 তীর “শূন্য বার”-এর বাইপাস; নিচের সারিতে ডান থেকে বাঁয়ে abb-এর শিকল।
N((a ∪ b)∗abb) — ১৪টি state, ১৬টি তীর
নাম না লেখা তীরগুলো ε-তীর। নিচের সারি ডান থেকে বাঁয়ে পড়ুন: q7 → q8 –a→ q9 → q10 –b→ q11 → q12 –b→ q13.
এবার একই কাজ ব্রাউজারের Python-এ। প্রথম ব্লকটি একটি ছোট recursive-descent parser: regex-এর লেখা থেকে syntax tree বানায়, আর গাছটিকে পুরো বন্ধনী দিয়ে ছাপে, যাতে precedence চোখে দেখা যায়। কোডে union লেখা হয় “|”, ফাঁকা string “ε”, ফাঁকা সেট “∅”. এই পৃষ্ঠার চারটি Python ব্লক একটি namespace ভাগ করে (data-shared), তাই ক্রম ধরে চালান।
def parse(r): # union "|", empty string "ε", empty set "∅"
pos = 0
def peek(): return r[pos] if pos < len(r) else ""
def union():
nonlocal pos
t = concat()
while peek() == "|": pos += 1; t = ("|", t, concat())
return t
def concat():
t = None
while peek() not in ("", "|", ")"):
f = atom(); t = f if t is None else (".", t, f)
return t or ("ε",)
def atom():
nonlocal pos
c = r[pos]; pos += 1
if c == "(": t = union(); pos += 1 # pos += 1 skips ")"
else: t = (c,) # a symbol, "ε" or "∅"
while peek() == "*": pos += 1; t = ("*", t)
return t
return union()
def show(t): # fully bracketed: makes precedence visible
if len(t) == 1: return t[0]
if t[0] == "*": return "(" + show(t[1]) + ")*"
return "(" + show(t[1]) + (" ∪ " if t[0] == "|" else "·") + show(t[2]) + ")"
for R in ["(a|b)*abb", "ab|c*", "ab*", "(ab)*", "a|", "BG-dddd"]:
print(f"{R:10} ->", show(parse(R)))আসল আউটপুট (ব্রাউজারের Python):
(a|b)*abb -> (((((a ∪ b))*·a)·b)·b)
ab|c* -> ((a·b) ∪ (c)*)
ab* -> (a·(b)*)
(ab)* -> ((a·b))*
a| -> (a ∪ ε)
BG-dddd -> ((((((B·G)·-)·d)·d)·d)·d)
প্রথম লাইনটি stepper-এর ধাপ ১-এর গাছ। দ্বিতীয় লাইনে precedence-এর দুই নিয়ম একসঙ্গে: ab|c* পড়া হয়েছে (a·b) ∪ (c)*, অর্থাৎ star শুধু c-কে বাঁধে আর union সবার শেষে। তৃতীয় আর চতুর্থ লাইনে বন্ধনীর পার্থক্য: ab* মানে a তারপর যত খুশি b, আর (ab)* মানে ab-এর পুনরাবৃত্তি। পঞ্চম লাইনটি একটি সূক্ষ্ম কথা: “a|” লেখায় union-এর ডান দিক ফাঁকা, আর parser সেটিকে ε ধরেছে, তাই a ∪ ε. শেষ লাইনে বাজারঘরের অর্ডার কোড (পর্ব ১০-এর মতো alphabet {B, G, -, d}, d মানে যেকোনো অঙ্ক) শুধু concatenation-এর একটি শিকল।
দ্বিতীয় ব্লক সংজ্ঞা ২.১-এর ছয় নিয়ম হুবহু কোডে লেখে। প্রতিটি node তৈরি হলে একটি লাইন লগে যায়: কোন operator, টুকরোর শুরু আর শেষ, এখন পর্যন্ত মোট state আর তীর। naive parameter-টি অংশ ৬-এর একটি ভুল শর্টকাটের জন্য রাখা; এখন সেটি বন্ধ।
# needs parse() from the block above (shared namespace)
def thompson(R, naive=False): # -> (states, edges, start, accept, log)
E, log, n = [], [], [0] # edge (p, label, q); label "" means ε
def new(): n[0] += 1; return n[0] - 1
def build(t):
op = t[0]
if len(t) == 1: # base: two fresh states
s, f = new(), new()
if op != "∅": E.append((s, "" if op == "ε" else op, f))
elif op == ".": # glue: f1 --ε--> s2
(s, f1), (s2, f) = build(t[1]), build(t[2])
E.append((f1, "", s2))
elif op == "*" and naive: # WRONG shortcut (part 6)
s, f = build(t[1]); E.extend([(s, "", f), (f, "", s)])
else: # "|" or "*": fresh s, f
parts = [build(x) for x in t[1:]]
s, f = new(), new()
for s1, f1 in parts: E.extend([(s, "", s1), (f1, "", f)])
if op == "*": E.extend([(s, "", f), (f1, "", s1)])
log.append(f"{op:2} start q{s:<2} accept q{f:<2} states {n[0]:2} edges {len(E)}")
return s, f
s, f = build(parse(R))
return n[0], E, s, f, log
N = thompson("(a|b)*abb")
print(*N[4], sep="\n")
print("start", N[2], "accept", N[3], "| ε-edges:", sum(a == "" for _, a, _ in N[1]))আসল আউটপুট (ব্রাউজারের Python):
a start q0 accept q1 states 2 edges 1
b start q2 accept q3 states 4 edges 2
| start q4 accept q5 states 6 edges 6
* start q6 accept q7 states 8 edges 10
a start q8 accept q9 states 10 edges 11
. start q6 accept q9 states 10 edges 12
b start q10 accept q11 states 12 edges 13
. start q6 accept q11 states 12 edges 14
b start q12 accept q13 states 14 edges 15
. start q6 accept q13 states 14 edges 16
start 6 accept 13 | ε-edges: 11
দশটি লাইন syntax tree-এর দশটি node, ঠিক postorder-এ: a, b, ∪, ∗, তারপর তিনবার “পাতা, তারপর ·”. প্রতিটি লাইনের সংখ্যা stepper-এর ধাপগুলোর সঙ্গে হুবহু মেলে: union-এর পর ৬টি state ও ৬টি তীর, star-এর পর ৮ ও ১০, শেষে ১৪ ও ১৬. লক্ষ করুন, “.” লাইনগুলোতে state-সংখ্যা বাড়েনি, বেড়েছে শুধু একটি তীর; আর প্রতিটি “.”-এর শুরু q6-ই থেকে গেছে, কারণ concatenation-এর শুরু বাঁ টুকরোর শুরু। ১৬টি তীরের ১১টি ε; চিহ্নের তীর ঠিক ৫টি, regex-এ যতবার চিহ্ন লেখা আছে ততটি।
৪ · সঠিকতার প্রমাণ — regex-এর গঠনের ওপর induction
একটি উদাহরণে নির্মাণটি কাজ করেছে। সব regex-এ করবে কি? Regex নিজেই recursive-ভাবে সংজ্ঞায়িত একটি সেট: তিন ধরনের ভিত্তি আর তিনটি গড়ার নিয়ম। এমন সেটের প্রতিটি সদস্যে কিছু প্রমাণ করার স্বাভাবিক হাতিয়ার structural induction (পর্ব ০৪; গণিতের ভিত্তি ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ১২-এ): প্রতিটি ভিত্তিতে দাবিটি দেখাতে হবে, আর প্রতিটি নিয়মে দেখাতে হবে যে অংশগুলোতে দাবি সত্য হলে পুরোটিতেও সত্য।
প্রথমে একটি সহায়ক lemma, যা ছবির চার ধর্মকে একটি প্রমাণিত দাবিতে বদলায়। এর প্রমাণে শুধু গোনা আর দেখা লাগে।
প্রতিটি regex R-এর জন্য N(R)-এ (I1) ঠিক একটি accepting state f আছে, আর f ≠ s; (I2) s-এ কোনো তীর ঢোকে না; (I3) f থেকে কোনো তীর বের হয় না; (I4) প্রতিটি state থেকে বড়জোর দুটি তীর বের হয়, আর চিহ্নের তীর থাকলে সেটিই একমাত্র।
প্রমাণ (R-এর গঠনের ওপর induction): ভিত্তি-টুকরোয় দুটি state আর বড়জোর একটি তীর s → f, তাই চারটিই সরাসরি দেখা যায়। Union আর star-এ s আর f দুটিই নতুন; নতুন তীরগুলো s থেকে বের হয় বা f-এ ঢোকে, তাই (I2), (I3) টিকে থাকে। পুরোনো f1, f2 থেকে আগে কোনো তীর ছিল না (hypothesis-এর I3), এখন বড়জোর দুটি হলো, আর s থেকে দুটি; অন্য কোনো state-এর বের-হওয়া তীর বদলায়নি, তাই (I4). Concatenation-এ একমাত্র নতুন তীর f1 → s2; s1-এ এখনো কিছু ঢোকে না আর f2 থেকে কিছু বের হয় না, আর f1-এর এখন একটিমাত্র তীর। প্রতিটি নিয়মে accepting state একটিই থাকে। ∎
এখন মূল উপপাদ্য। (I1) থাকায় L(N(R)) = {w : s ⇝w f}, অর্থাৎ শুধু শুরু থেকে একমাত্র শেষের পথগুলো দেখলেই চলে।
Σ-এর ওপর প্রতিটি regex R-এর জন্য L(N(R)) = L(R). ফলে প্রতিটি regex-এর language কোনো ε-NFA চেনে, অর্থাৎ regular.
প্রমাণ (R-এর গঠনের ওপর structural induction; প্রতিটি টুকরোর শুরু s, শেষ f):
- ভিত্তি, R = ∅: কোনো তীর নেই আর s ≠ f, তাই s থেকে f-এ কোনো পথ নেই; L(N(∅)) = ∅ = L(∅). — সংজ্ঞা ২.১, I1
- ভিত্তি, R = ε বা a: একমাত্র তীর s → f, আর f থেকে কিছু বের হয় না, তাই একমাত্র পথ ওই একটি তীর; label যথাক্রমে ε বা a. L(N(R)) = {ε} বা {a} = L(R). — সংজ্ঞা ২.১, I3
- Hypothesis: R1 আর R2-এ দাবি সত্য: si ⇝w fi (N(Ri)-এর ভেতরে) ⇔ w ∈ L(Ri). — অংশগুলোতে দাবি সত্য ধরা
- Union: s থেকে বের হওয়ার তীর শুধু s → s1 আর s → s2. ধরুন পথটি s1-এ গেল। N(R1) থেকে বের হওয়ার একমাত্র তীর f1 → f, আর s-এ ফেরার কোনো তীর নেই (I2). তাই পথটি হলো s → s1 ⇝w f1 → f, যার মাঝের অংশ পুরোটা N(R1)-এর ভেতরে; hypothesis-এ w ∈ L(R1). উল্টো দিকে w ∈ L(R1) হলে এই পথটিই বানানো যায়। R2-এর জন্য একই। তাই L = L(R1) ∪ L(R2). — I2, I3, hypothesis
- Concatenation: N(R1) থেকে N(R2)-এ যাওয়ার একমাত্র তীর f1 → s2, আর ফেরার কোনো তীর নেই। তাই s1 থেকে f2-এর প্রতিটি পথ s1 ⇝u f1 → s2 ⇝v f2, প্রথম অংশ N(R1)-এ, দ্বিতীয়টি N(R2)-এ; label w = uv, যেখানে u ∈ L(R1), v ∈ L(R2). উল্টো দিকে এমন u, v থেকে পথটি জোড়া যায়। তাই L = L(R1)L(R2). — hypothesis, concatenation-এর সংজ্ঞা
- Star, ⊆: s থেকে f-এর একটি পথ নিন। হয় এটি সরাসরি s → f (label ε), নয়তো s → s1, তারপর N(R1)-এর ভেতরে চলে, আর প্রতিবার f1-এ এসে হয় f1 → s1 নেয়, নয়তো f1 → f নিয়ে শেষ করে। প্রতিটি f1-এ পথটিকে কাটুন। পাওয়া যায় k ≥ 1টি খণ্ড s1 ⇝wj f1, প্রতিটি পুরো N(R1)-এর ভেতরে (কারণ N(R1)-এর ভেতরে f1 থেকে কোনো তীর নেই, I3), তাই hypothesis-এ প্রতিটি wj ∈ L(R1). Label w = w1⋯wk ∈ L(R1)k ⊆ L(R1)∗, আর সরাসরি পথে ε ∈ L(R1)∗. — পথ কাটা, I3, hypothesis
- Star, ⊇: w ∈ L(R1)∗ হলে w = ε, তখন s → f; নয়তো w = w1⋯wk, k ≥ 1, প্রতিটি wj ∈ L(R1). Hypothesis থেকে প্রতিটি wj-এর একটি পথ s1 ⇝ f1 আছে; s → s1, তারপর খণ্ডগুলো মাঝে মাঝে f1 → s1 দিয়ে জুড়ে, শেষে f1 → f. তাই L = L(R1)∗. ∎ — Kleene star-এর সংজ্ঞা
প্রমাণের হৃদয় একটি বাক্য: প্রতিটি টুকরোয় ঢোকার আর বের হওয়ার পথ ঠিক একটি করে। তাই বাইরের পথ ভেতরের টুকরোর মাঝখানে লাফিয়ে ঢুকতে বা মাঝখান থেকে বেরিয়ে যেতে পারে না, আর প্রতিটি খণ্ডে hypothesis খাটানো যায়। নিচের stepper প্রমাণটিকে আবার, এবার ক্ষেত্র ধরে ধরে, পথের আকার দেখিয়ে সাজায়।
1দাবি P(R)2ভিত্তি: ∅, ε, a3Hypothesis4Union5Concatenation6Star7উপসংহার
| s থেকে f-এর পথ | |
| label | |
| মূল যুক্তি |
- দাবি। P(R): “N(R)-এ s থেকে f-এ label w-এর পথ আছে ⇔ w ∈ L(R).” Lemma ৪.১-এর (I1) অনুযায়ী accepting state একটিই, তাই এটিই L(N(R)) = L(R).
- ভিত্তি। ∅-এ কোনো তীর নেই, তাই কোনো পথ নেই; ε-এ একটিমাত্র ε-তীর, a-তে একটিমাত্র a-তীর। তিনটি language ∅, {ε}, {a}: সংজ্ঞার সঙ্গে হুবহু।
- Hypothesis. বড় regex-এর প্রতিটি সরাসরি অংশ (R1, R2) ছোট, তাই তাদের জন্য P সত্য ধরা যায়। লক্ষ করুন, hypothesis কথা বলে শুধু N(Ri)-এর ভেতরের পথ নিয়ে।
- Union. s থেকে বের হওয়ার দুটি তীরের একটি নিতেই হয়। ঢোকার পর পথটি শাখার ভেতরেই থাকে, কারণ s-এ ফেরার তীর নেই আর শাখা থেকে বের হওয়ার একমাত্র দরজা fᵢ → f.
- Concatenation. দুই টুকরোর মাঝে একটিমাত্র সেতু f1 → s2, তাও এক দিকে। পথটি সেতুতে দুই ভাগ হয়, প্রথম ভাগের label u, দ্বিতীয়টির v, আর hypothesis দুই ভাগেই খাটে।
- Star. পথটি প্রতিবার f1-এ এলে কাটুন। প্রতিটি খণ্ড N(R1)-এর ভেতরের একটি s1 ⇝ f1 পথ, তাই তার label L(R1)-এ। খণ্ড শূন্যটি হলে বাইপাস s → f, label ε. উল্টো দিকে খণ্ডগুলো জুড়ে পথ বানানো যায়।
- উপসংহার। ছয় ক্ষেত্রেই P টিকে থাকে, তাই প্রতিটি regex-এ L(N(R)) = L(R). এটি Kleene-এর উপপাদ্যের “regex ⇒ automaton” দিক; subset construction মিলিয়ে প্রতিটি regex-এর জন্য একটি DFA-ও আছে।
Stephen Kleene ১৯৫৬ সালে প্রকাশিত “Representation of Events in Nerve Nets and Finite Automata” প্রবন্ধে regular event (আজকের regular expression) আর finite automaton-এর সমতা দেখান; লেখাটির একটি আগের রূপ ১৯৫১ সালের একটি RAND প্রতিবেদন বলে উল্লেখ আছে। তাঁর প্রবন্ধে আজকের ε-NFA ছিল না; NFA-র formal সংজ্ঞা আসে Rabin–Scott-এর ১৯৫৯ সালের প্রবন্ধে (পর্ব ০৯)। Regex থেকে automaton বানানোর একটি পদ্ধতি McNaughton আর Yamada ১৯৬০ সালে দেন, আর Ken Thompson-এর ১৯৬৮ সালের প্রবন্ধ “Regular Expression Search Algorithm” (Communications of the ACM) ε-তীর দিয়ে জোড়ার যে সরল, যন্ত্রিক রূপ দেয়, সেটিই আজ তাঁর নামে পরিচিত।
৫ · আকারের সীমা আর simulation-এর খরচ
সঠিক হওয়াই যথেষ্ট নয়; যন্ত্রটি ছোটও হতে হবে। ধরুন |R| মানে R-এর syntax tree-এর node-সংখ্যা: যতগুলো চিহ্ন, ε আর ∅ লেখা আছে, তার সঙ্গে যতগুলো ∪, ∗ আর concatenation (concatenation লেখায় অদৃশ্য, কিন্তু গাছে একটি node). বন্ধনী গোনা হয় না। যেমন (a ∪ b)∗abb-এ ৫টি পাতা, ১টি ∪, ১টি ∗ আর ৩টি concatenation, তাই |R| = 10.
ধরুন R-এ ℓটি পাতা, uটি union আর kটি star. তাহলে N(R)-এ ঠিক 2(ℓ + u + k) ≤ 2|R|টি state আর বড়জোর 4|R|টি তীর। N(R) বানানো যায় |R|-এর অনুপাতে সময়ে, আর দৈর্ঘ্য m-এর একটি string N(R)-এ গৃহীত কি না তা ঠিক করা যায় |R| · m-এর অনুপাতে সময়ে।
প্রমাণ:
- প্রতিটি পাতা ঠিক ২টি state আনে, প্রতিটি union আর star ঠিক ২টি নতুন state, আর concatenation একটিও না। তাই |Q| = 2ℓ + 2u + 2k. যেহেতু ℓ + u + k ≤ |R| (বাকি node-গুলো concatenation), |Q| ≤ 2|R|. — সংজ্ঞা ২.১-এর প্রতিটি নিয়ম গোনা
- Lemma ৪.১-এর (I4) অনুযায়ী প্রতিটি state থেকে বড়জোর ২টি তীর বের হয়, তাই তীর ≤ 2|Q| ≤ 4|R|. — I4
- প্রতিটি node-এ বড়জোর ২টি state আর ৪টি তীর যোগ হয়, তাই postorder-এ গাছ একবার ঘুরলেই নির্মাণ শেষ: সময় |R|-এর অনুপাতে (parse করাও রৈখিক)। — প্রতিটি node-এ ধ্রুবক কাজ
- Simulation-এ বর্তমান state-সেট S রাখা হয়। শুরুতে S = E({s}); প্রতিটি চিহ্ন c পড়ে S-এর প্রতিটি state-এর c-তীর ধরে নতুন সেট, তারপর তার ε-closure. একটি ধাপে প্রতিটি state আর প্রতিটি তীর বড়জোর একবার দেখা হয় (graph-এর BFS বা DFS), তাই ধাপপ্রতি কাজ |Q| + তীর-সংখ্যার অনুপাতে, অর্থাৎ |R|-এর অনুপাতে। m ধাপে |R| · m. শেষে f ∈ S কি না দেখা। ∎ — I4, ε-closure-এর BFS
(a ∪ b)∗abb-এ ℓ = 5, u = 1, k = 1, তাই state = 2 · 7 = 14, ঠিক stepper-এর সংখ্যা; সীমা 2|R| = 20. সংখ্যাটি regex-এর দৈর্ঘ্যের সঙ্গে রৈখিক, এটাই বড় কথা। পর্ব ১০-এ দেখেছেন, NFA থেকে DFA-তে গেলে state ঘাতের হারে বাড়তে পারে; কিন্তু regex থেকে NFA-তে আসার ধাপে কোনো বিস্ফোরণ নেই। নিচের stepper N((a ∪ b)∗abb)-কে “aabb” পড়ায়, ঠিক ধাপ ৪-এর পদ্ধতিতে: প্রতিটি চিহ্নে আগে চিহ্নের তীর, তারপর ε-closure.
1শুরু: E({q6})2পড়া হলো a3পড়া হলো a4পড়া হলো b5পড়া হলো b (শেষ)6সিদ্ধান্ত
| এ পর্যন্ত পড়া | |
| চিহ্নের তীর | |
| ε-closure-এর পর | |
| সেটের আকার |
- শুরু। কিছু পড়ার আগেই ε-closure: q6 থেকে q4 আর q7; q4 থেকে q0, q2; q7 থেকে q8. সেট {0, 2, 4, 6, 7, 8}: যন্ত্র একসঙ্গে “লুপের ভেতরে a বা b পড়তে” আর “abb-এর a পড়তে” প্রস্তুত।
- a পড়া। সেটের যে state-গুলো থেকে a-তীর আছে: q0 → q1 আর q8 → q9. তারপর closure: q1 → q5 → q4, q7 → q0, q2, q8; আর q9 → q10. নতুন সেটে ৯টি state; q10 মানে “abb-এর a দেখা হয়েছে, এবার b চাই”.
- আবার a. একই দুটি a-তীর, একই closure, তাই একই সেট। অর্থও এক: শেষ চিহ্ন a. DFA-র ভাষায় এটি একই state-এ থেকে যাওয়া।
- b পড়া। b-তীর q2 → q3 আর q10 → q11. Closure-এ q3 → q5 → লুপের সব, আর q11 → q12. q12 মানে “ab দেখা হয়েছে”; আগের q9, q10 ঝরে পড়েছে, কারণ সেখান থেকে b-তীর নেই।
- আবার b, শেষ। q2 → q3 আর q12 → q13. Closure-এ লুপের state-গুলো ফেরে, আর q13-এর বের হওয়ার তীর নেই (I3). সেটে ৮টি state, তার একটি q13.
- সিদ্ধান্ত। শেষ সেটে একমাত্র accepting state q13 আছে, তাই aabb গৃহীত। প্রতিটি ধাপে বড়জোর ১৪টি state আর ১৬টি তীর দেখা হয়েছে: সময় |R| · m-এর অনুপাতে, যেমন উপপাদ্য ৫.১ বলে।
তৃতীয় ব্লক এই simulation-টিই কোডে করে, তারপর একটি স্বাধীন যাচাই চালায়: পাঁচটি regex-এর প্রতিটির জন্য দৈর্ঘ্য 0 থেকে 8-এর সব 511টি string-এ নিজের NFA আর Python-এর re.fullmatch-এর উত্তর মেলায়, আর উপপাদ্য ৫.১-এর সীমাও দেখায়। re নিজে একটি backtracking engine (অংশ ৮), কিন্তু এই সরল pattern-গুলোর অর্থ সে ঠিকই জানে, তাই সে একটি ভালো স্বাধীন রেফারেন্স।
import re
from itertools import product
def closure(S, E): # ε-closure by a stack (DFS)
S, todo = set(S), list(S)
while todo:
p = todo.pop()
for x, a, q in E:
if x == p and a == "" and q not in S:
S.add(q); todo.append(q)
return frozenset(S)
def run(N, w, show=False):
n, E, s, f, _ = N
S = closure({s}, E)
for i, c in enumerate(w):
if show: print(f"{w[:i] or 'ε':5} {len(S):2} states:", *sorted(S))
S = closure({q for p, a, q in E if p in S and a == c}, E)
if show: print(f"{w or 'ε':5} {len(S):2} states:", *sorted(S))
return N[3] in S
N = thompson("(a|b)*abb")
print("aabb accepted:", run(N, "aabb", show=True))
def agree(R, sigma="ab", n=8): # vs Python's re on all strings
M, py = thompson(R), R.replace("ε", "()")
ws = ["".join(t) for k in range(n + 1) for t in product(sigma, repeat=k)]
return sum(run(M, w) != bool(re.fullmatch(py, w)) for w in ws), len(ws)
size = lambda t: 1 + sum(size(x) for x in t[1:]) # symbols + operators
for R in ["(a|b)*abb", "a*b*", "(ab|ba)*", "(a|ε)b*", "((a*b)*a)*"]:
M, k = thompson(R), size(parse(R))
print(f"{R:11} |R|={k:2} states {M[0]:2} ≤ {2*k:2} wrong/tested:", agree(R))আসল আউটপুট (ব্রাউজারের Python):
ε 6 states: 0 2 4 6 7 8
a 9 states: 0 1 2 4 5 7 8 9 10
aa 9 states: 0 1 2 4 5 7 8 9 10
aab 9 states: 0 2 3 4 5 7 8 11 12
aabb 8 states: 0 2 3 4 5 7 8 13
aabb accepted: True
(a|b)*abb |R|=10 states 14 ≤ 20 wrong/tested: (0, 511)
a*b* |R|= 5 states 8 ≤ 10 wrong/tested: (0, 511)
(ab|ba)* |R|= 8 states 12 ≤ 16 wrong/tested: (0, 511)
(a|ε)b* |R|= 6 states 10 ≤ 12 wrong/tested: (0, 511)
((a*b)*a)* |R|= 8 states 12 ≤ 16 wrong/tested: (0, 511)
প্রথম পাঁচ লাইন stepper-এর পাঁচটি সেট, হুবহু; প্রতিটি লাইনের বাঁয়ে এ পর্যন্ত পড়া অংশ। শেষে q13 আছে, তাই True. পরের পাঁচ লাইনে প্রতিটি regex-এ অমিল 0, 511টির মধ্যে। State-সংখ্যা প্রতিবার সূত্র 2(ℓ + u + k) মানে: a∗b∗-এ ২টি পাতা আর ২টি star, তাই 8; (ab ∪ ba)∗-এ ৪টি পাতা, ১টি union, ১টি star, তাই 12. সীমা 2|R| কখনো ভাঙেনি, আর concatenation বেশি থাকলে সংখ্যাটি সীমা থেকে তত দূরে। Python-এর re-এ ε লেখা যায় না, তাই কোডে ε-কে (), অর্থাৎ ফাঁকা group, দিয়ে বদলানো হয়েছে।
৬ · নতুন state কেন লাগে — star-এর শর্টকাট আর DFA-তে রূপান্তর
Star-এর নিয়মে দুটি নতুন state খরচ হয়। একটি সহজ শর্টকাট মনে আসতে পারে: নতুন state না বানিয়ে N(R1)-এর নিজের s1 আর f1-এর মধ্যে দুটি ε-তীর দেওয়া, s1 → f1 (শূন্য বার) আর f1 → s1 (আবার)। শুনতে ঠিক, আর a∗-এর মতো সরল ক্ষেত্রে ঠিকই কাজ করে। কিন্তু এতে Lemma ৪.১-এর (I2) আর (I3) ভেঙে যায়: এখন শুরুতে একটি তীর ঢোকে, আর শেষ থেকে একটি বের হয়। এই টুকরোটি যখন আরেকটি টুকরোর ভেতরে বসে, তখন বাইরের তীর ভেতরের লুপের সঙ্গে মিশে নতুন, অনাকাঙ্ক্ষিত পথ তৈরি করে।
(a∗b)∗ দিয়ে দেখা যাক। শর্টকাটে ভেতরের a∗-এর শুরু sa একই সঙ্গে পুরো (a∗b)-এর শুরু, আর বাইরের star সেখান থেকে শেষ পর্যন্ত একটি ε-বাইপাস দেয়। এখন “a” পড়ার পথ: sa –a→ fa, তারপর ভেতরের লুপ fa –ε→ sa, তারপর বাইরের বাইপাস sa –ε→ শেষ। অর্থাৎ যন্ত্রটি একটি a পড়ে b ছাড়াই শেষে পৌঁছে যায়, অথচ (a∗b)∗-এর প্রতিটি অশূন্য string b দিয়ে শেষ হয়। প্রমাণের ভাষায়: Star-এর ⊆ ধাপে আমরা বলেছিলাম “প্রতিটি খণ্ড পুরো N(R1)-এর ভেতরে”; শর্টকাটে বাইরের পথ ভেতরের টুকরোর মাঝখানে, sa-এ, ঢুকে বা বের হয়ে যেতে পারে, তাই ধাপটি আর খাটে না। চতুর্থ ব্লক প্রতিটি star-এ শর্টকাট নিয়ে চারটি regex-এ পাল্টা-উদাহরণ খোঁজে, তারপর সঠিক NFA-কে subset construction-এ DFA বানায়।
import re
from itertools import product # uses thompson(), closure(), run()
for R in ["a*", "(a|b)*", "(a*b)*", "(ab*)*"]:
M = thompson(R, naive=True) # star without fresh states
ws = ["".join(t) for k in range(5) for t in product("ab", repeat=k)]
bad = [w for w in ws if run(M, w) != bool(re.fullmatch(R, w))]
print(f"naive {R:7} wrong on:", bad[:4] or "none up to length 4")
def to_dfa(N, sigma="ab"): # subset construction with closure
n, E, s, f, _ = N
start = closure({s}, E)
seen, todo = [start], [start]
while todo:
S = todo.pop(0)
for c in sigma:
T = closure({q for p, a, q in E if p in S and a == c}, E)
if T not in seen: seen.append(T); todo.append(T)
return seen
N = thompson("(a|b)*abb")
D = to_dfa(N)
print("NFA states:", N[0], " DFA states:", len(D),
" accepting:", sum(N[3] in S for S in D))আসল আউটপুট (ব্রাউজারের Python):
naive a* wrong on: none up to length 4
naive (a|b)* wrong on: none up to length 4
naive (a*b)* wrong on: ['a', 'aa', 'ba', 'aaa']
naive (ab*)* wrong on: ['b', 'ba', 'bb', 'baa']
NFA states: 14 DFA states: 5 accepting: 1
প্রথম দুটি regex-এ শর্টকাট কোনো ভুল করেনি; এখানেই ফাঁদটি বিপজ্জনক, কারণ সরল পরীক্ষায় সব ঠিক দেখায়। (a∗b)∗-এ “a”, “aa”, “ba”, “aaa” ভুলভাবে গৃহীত হয়েছে: সবগুলো a দিয়ে শেষ, ঠিক উপরের ব্যাখ্যার মতো। (ab∗)∗-এ উল্টো সমস্যা: “b” গৃহীত, অথচ প্রতিটি অশূন্য string a দিয়ে শুরু হওয়ার কথা। শেষ লাইনে সঠিক ১৪-state NFA থেকে subset construction-এ মাত্র ৫টি DFA state এসেছে, যার একটি accepting.
শেষ লাইনের ৫টি DFA state নিচের টেবিলে, নাম A থেকে E. প্রতিটি DFA state NFA-র state-এর একটি সেট; শুরু state হলো শুরুর ε-closure, আর প্রতিটি চিহ্নের পর আবার closure. এটি পর্ব ১০-এর subset construction, শুধু প্রতিটি ধাপে ε-closure যোগ করে, যা পর্ব ১১-এর বিষয়। সেটগুলো scratch-এর একটি script দিয়ে মেলানো।
| DFA state | NFA state-সেট (q-নম্বর) | a পড়লে | b পড়লে |
|---|---|---|---|
| → A (শুরু) | {0, 2, 4, 6, 7, 8} | B | C |
| B | {0, 1, 2, 4, 5, 7, 8, 9, 10} | B | D |
| C | {0, 2, 3, 4, 5, 7, 8} | B | C |
| D | {0, 2, 3, 4, 5, 7, 8, 11, 12} | B | E |
| ∗ E (accepting) | {0, 2, 3, 4, 5, 7, 8, 13} | B | C |
টেবিলে A আর C-এর সারি হুবহু এক (a-তে B, b-তে C), আর দুটিই non-accepting. তাই কোনো ভবিষ্যৎ string এদের আলাদা করতে পারে না, আর এদের মিশিয়ে ৪ state-এর DFA পাওয়া যায়: “শেষে abb-এর কোনো অংশ নেই”, “শেষে a”, “শেষে ab”, “শেষে abb”. এটিই সবচেয়ে ছোট DFA, যা পর্ব ১৯-এর minimization-এ যন্ত্রিকভাবে আসবে আর অংশ ৭-এর library-ও দেখাবে। পুরো যাত্রাপথ তাহলে এমন: regex (|R| = 10) → Thompson-এ ε-NFA (১৪ state) → subset construction-এ DFA (৫ state) → minimization-এ ৪ state. প্রথম ধাপ সবসময় রৈখিক; দ্বিতীয় ধাপে বিস্ফোরণের ঝুঁকি থাকে, যদিও এখানে আসেনি।
৭ · সত্যিকারের run — automata-lib-এর regex থেকে NFA
নিজের লেখা কোডকে নিজের লেখা কোড দিয়ে যাচাই করা যথেষ্ট নয়। automata-lib হলো finite automaton, PDA আর Turing machine-এর একটি Python library (MIT licence), যার NFA.from_regex একটি regex থেকে ε-NFA বানায়। নিচের কোডটি ডেস্কটপে uv দিয়ে বানানো একটি ছোট প্রকল্পে চালানো হয়েছে: automata-lib 9.2.0, Python 3.12. Library-র কোডে কোনো network বা usage-reporting অংশ নেই (scratch-এ উৎস-কোড খুঁজে দেখা হয়েছে)। প্রকল্পে mine.py নামে এই পৃষ্ঠার parser আর Thompson builder-এর একটি কপিও আছে, যাতে দুই নির্মাণ দৈর্ঘ্য 10 পর্যন্ত সব string-এ মেলানো যায়। Library-র regex-এ union “|”, star “*”, আর “-” একটি সাধারণ চিহ্ন।
from importlib.metadata import version
from itertools import product
from automata.fa.nfa import NFA
from automata.fa.dfa import DFA
from automata.regex.regex import isequal
import mine # our own Thompson builder (mine.py)
print("automata-lib", version("automata-lib"))
tests = [("(a|b)*abb", "ab", 10), ("(0|1)*1", "01", 10),
("BG-dddd", "BG-d", 8), ("(a*b)*", "ab", 10)]
for rx, sig, n in tests:
lib = NFA.from_regex(rx, input_symbols=set(sig))
eps = sum(len(t.get("", ())) for t in lib.transitions.values())
own = mine.thompson(mine.parse(rx))
words = ["".join(p) for k in range(n + 1) for p in product(sig, repeat=k)]
bad = sum(lib.accepts_input(w) != mine.accepts(own, w) for w in words)
dfa = DFA.from_nfa(lib) # minify=True by default
print(f"{rx:10} lib {len(lib.states):2} states {eps:2} eps-edges"
f" {len(lib.final_states)} final | own {own[0]:2} states"
f" | minimal DFA {len(dfa.states)} | disagree {bad}/{len(words)}")
print(isequal("(a|b)*abb", "(a*b*)*abb", input_symbols={"a", "b"}))
print(isequal("(a|b)*abb", "(a|b)*ab*b", input_symbols={"a", "b"}))সত্যিকারের run (ডেস্কটপ, automata-lib 9.2.0, Python 3.12):
~/bazarghar-toc$ uv run python thompson_check.py
automata-lib 9.2.0
(a|b)*abb lib 12 states 10 eps-edges 1 final | own 14 states | minimal DFA 4 | disagree 0/2047
(0|1)*1 lib 8 states 8 eps-edges 1 final | own 10 states | minimal DFA 2 | disagree 0/2047
BG-dddd lib 14 states 6 eps-edges 1 final | own 14 states | minimal DFA 8 | disagree 0/87381
(a*b)* lib 6 states 6 eps-edges 2 final | own 8 states | minimal DFA 2 | disagree 0/2047
True
False
চারটি regex-এ library-র NFA আর আমাদের নির্মাণ সব string-এ একমত: অর্ডার কোডে 40 + ⋯ + 48 = 87381টি string, বাকিগুলোতে 2047টি। কিন্তু state-সংখ্যা আলাদা, আর কারণটি library-র উৎস-কোডে পড়ে দেখা গেছে: এটি Thompson-এর একটি রূপভেদ। Union-এ শুধু নতুন শুরু যোগ হয়, নতুন শেষ নয়; দুই শাখার accepting state দুটিই accepting থাকে। Star-এ একটি নতুন শুরু আসে, আর পুরোনো শুরুকে accepting করা হয়। তাই (a ∪ b)∗abb-এ ১২টি state, আমাদের ১৪টি নয়, আর (a∗b)∗-এ শেষ যন্ত্রে ২টি accepting state: আমাদের (I1) ধর্মটি এখানে নেই। এই রূপভেদ সঠিক, কারণ library-র টুকরোর শুরুতে star-এর আগে কোনো তীর ঢোকে না; অংশ ৬-এর ফাঁদটি এড়ানো হয়েছে অন্য পথে। Minimal DFA-র সংখ্যাও শিক্ষণীয়: (a ∪ b)∗abb-এ ৪টি, অংশ ৬-এর হিসাবের মতো; অর্ডার কোডে ৮টি, কারণ এই library dead state ছাড়া partial DFA রাখে (total DFA-তে ৯টি, পর্ব ১০-এর মতো)। শেষ দুই লাইনে library-র language-সমতা পরীক্ষা: (a∗b∗)∗abb আর (a ∪ b)∗abb একই language, কিন্তু (a ∪ b)∗ab∗b ভিন্ন, যেমন “abbb” দ্বিতীয়টিতে আছে, প্রথমটিতে নেই।
৮ · বাস্তবে Thompson — grep, backtracking আর অন্য নির্মাণ
Thompson-এর ১৯৬৮ সালের প্রবন্ধের আসল লক্ষ্য তত্ত্ব ছিল না, ছিল একটি text editor-এ দ্রুত খোঁজা। তাঁর পদ্ধতিতে regex থেকে NFA বানিয়ে, অংশ ৫-এর মতো state-এর সেট ধরে, লেখার ওপর একবার চালানো হতো; সময় তাই লেখার দৈর্ঘ্য আর pattern-এর আকারের গুণফলের অনুপাতে, কোনো pattern-এ বিস্ফোরণ ছাড়াই। Thompson-এর QED আর পরে Unix-এর ed editor-এ regex খোঁজার সুবিধা ছিল, আর grep নামটি ed-এর একটি কমান্ড “g/re/p” (global, regular expression, print) থেকে এসেছে বলে সুপরিচিত বর্ণনা আছে।
Formal regex আর বাস্তব regex এক জিনিস নয়। এই পর্বের regex-এ শুধু ∅, ε, চিহ্ন, ∪, concatenation আর ∗. Python-এর re বা JavaScript-এর RegExp-এ আরও অনেক কিছু আছে: character class ([0-9]), anchor (^, $), lazy quantifier, lookaround আর backreference (\1, “আগে যা মিলেছে, হুবহু আবার”)। প্রথম কয়েকটি শুধু সংক্ষেপ, যেমন [0-9] = (0 ∪ 1 ∪ ⋯ ∪ 9), তাই Thompson-এর নিয়মে বসে। কিন্তু backreference গণিতের অর্থে regular নয়, আর তার জন্য কোনো finite automaton নেই। এ কারণেই এই engine-গুলো Thompson-এর সেট-পদ্ধতি না নিয়ে একটি backtracking matcher ব্যবহার করে: একবারে একটি পথ, ব্যর্থ হলে পিছিয়ে আরেকটি। সুবিধা বাড়ে, কিন্তু কিছু pattern-এ চেষ্টার সংখ্যা ঘাতের হারে বাড়তে পারে। দুই ধরনের engine-এর তুলনা আর ReDoS নিরাপত্তা সমস্যা পর্ব ২১-এর বিষয়; ব্যবহারিক regex লেখা শিখতে Python কোর্সের পর্ব ৩০ বা JavaScript কোর্সের পর্ব ৩০ দেখুন।
Thompson-এর পদ্ধতি regex থেকে automaton বানানোর একমাত্র উপায় নয়। একটি বড় বিকল্প Glushkov automaton, যাকে position automaton-ও বলা হয়। Regex-এর প্রতিটি চিহ্নের অবস্থানকে আলাদা নাম দেওয়া হয়; ফল একটি ε-ছাড়া NFA, যার state-সংখ্যা অবস্থান-সংখ্যার চেয়ে ঠিক ১ বেশি, (a ∪ b)∗abb-এ ৬টি। কিন্তু তীর regex-এর দৈর্ঘ্যের বর্গের মাপে হতে পারে, যেখানে Thompson-এ তীর রৈখিক। আরেকটি পথ Brzozowski derivative: regex R-এর a-derivative হলো এমন regex, যার language {w : aw ∈ L(R)}. প্রতিটি derivative-কে একটি state ধরলে, সরলীকরণের কিছু নিয়ম মেনে, সরাসরি একটি DFA পাওয়া যায়।
আরও গভীরে: Glushkov-এর নির্মাণ সাধারণত ১৯৬১ সালের কাজ হিসেবে, আর McNaughton–Yamada-র ১৯৬০ সালের পদ্ধতির সঙ্গে ঘনিষ্ঠ বলে উল্লেখ করা হয়; Brzozowski-এর derivative ১৯৬৪ সালের Journal of the ACM-এর প্রবন্ধে। Antimirov ১৯৯৬ সালে “partial derivative” দিয়ে এমন NFA দেন যার state বড়জোর অবস্থান-সংখ্যা + 1, আর পরে আরও ছোট “follow automaton” প্রস্তাবিত হয়। Regex-এর সমতা যাচাই সাধারণভাবে PSPACE-complete বলে প্রমাণিত (Meyer–Stockmeyer, ১৯৭০-এর দশকের শুরু); তাই কোনো নির্মাণই দুটি regex-এর তুলনা সস্তা করে দেয় না, যদি না P = PSPACE হয়, যা খোলা প্রশ্ন।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- একটি regex, যেমন (ab ∪ b)∗, থেকে Thompson-এর ε-NFA আঁকুন। আগে syntax tree, তারপর postorder-এ ছয় নিয়ম; প্রতিটি টুকরোর এক শুরু, এক শেষ।
- Thompson NFA-তে কতটি state? 2(পাতা + union + star), বড়জোর 2|R|; concatenation কোনো state আনে না (merge-করা রূপে প্রতিটি concatenation একটি state কমায়)।
- Thompson-এর NFA-কে DFA বানান। শুরু = শুরুর ε-closure, প্রতিটি চিহ্নের পর আবার closure; শেষ সেটে accepting state থাকলে accepting.
- Star-এ নতুন state কেন লাগে? শুরুতে তীর ঢুকলে বা শেষ থেকে বের হলে বাইরের তীর ভেতরের লুপের সঙ্গে মিশে বাড়তি string গ্রহণ করতে পারে; (a∗b)∗-এ “a”.
- Kleene-এর উপপাদ্যের কোন দিক Thompson প্রমাণ করে? regex ⇒ ε-NFA; উল্টো দিক state elimination বা Arden-এর সূত্রে (পর্ব ১৫)।
৯ · AI-এর যুগে Thompson construction
AI assistant Thompson-এর নিয়মগুলো নির্ভুল টেবিলে লিখে দিতে পারে, কিন্তু একটি নির্দিষ্ট regex-এ পুরো NFA আঁকতে বা গুনতে গেলে প্রায়ই ছোট ভুল করে। ছবিটি দেখতে পরিপাটি হয়, তাই ভুল সহজে চোখ এড়ায়। এই বিষয়ে যে ভুলগুলো বারবার দেখা যায়:
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
| Precedence গুলিয়ে ab∗-কে (ab)∗ ধরা, বা union-কে concatenation-এর আগে বাঁধা | আগে syntax tree পুরো বন্ধনী দিয়ে লেখানো, তারপর NFA |
| Star-এ “শূন্য বার”-এর বাইপাস বাদ দেওয়া, ফলে ε গৃহীত হয় না | সবসময় ফাঁকা string "" দিয়ে আলাদা পরীক্ষা |
| Star-এর শর্টকাট (নতুন state ছাড়া দুটি ε) নিয়ে “এটাও Thompson” বলা | (a∗b)∗-এ “a” চালিয়ে দেখা |
| Union-এ দুই শাখার accepting state রেখে আবার নতুন f-ও accepting রাখা, বা concatenation-এ f1-কে accepting রেখে দেওয়া | accepting state গোনা: Thompson-এ ঠিক একটি |
| State-সংখ্যার ভুল হিসাব, যেমন concatenation-এও ২টি state যোগ করা | 2(পাতা + union + star) সূত্রে মেলানো |
| DFA-তে নেওয়ার সময় শুরুর ε-closure না নেওয়া | Python-এ NFA আর DFA-কে সব ছোট string-এ মেলানো |
| বাস্তব regex-এর backreference-কেও “Thompson দিয়ে NFA বানানো যায়” বলা | মনে রাখা: backreference regular নয় (পর্ব ২১) |
| ভুল সাল বা বানানো রেফারেন্স, যেমন Thompson-কে Kleene-এর আগে বসানো | Sipser বা Hopcroft–Motwani–Ullman-এ নিজে খুঁজে দেখা |
AI-কে ভালোভাবে কাজে লাগানোর উপায়: শুধু ছবি না চেয়ে তীরের পূর্ণ তালিকা আর একটি স্বাধীন যাচাইয়ের কোড চাওয়া, তারপর কোডটি নিজে চালানো।
(নিজে যাচাই করুন: সঠিক NFA-তে ১০টি state আর ১২টি তীর; "", "b", "ab" আর "bab" গৃহীত, "ba" নয়। অনুশীলন ১-এ পুরো উত্তর আছে।)
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Thompson NFA বানানোর পর বাস্তব টুলগুলো কেন প্রায়ই পুরো DFA বানায় না, আবার কেউ কেউ কেন NFA-ও চালায় না, backtracking বেছে নেয়?
Thompson construction regex-কে রৈখিক আকারের একটি NFA দেয়। এর পরের ধাপে তিনটি পথ খোলা, আর প্রতিটির খরচ আলাদা। প্রথম পথ পুরো DFA আগে বানানো: পড়ার সময় প্রতি অক্ষরে একটিমাত্র টেবিল-দেখা, সবচেয়ে দ্রুত। কিন্তু পর্ব ১০-এ দেখেছেন, “শেষ থেকে n-তম চিহ্ন 1”-এর মতো pattern-এ DFA-তে 2nটি state লাগে, আর (a ∪ b)∗a(a ∪ b)20-এর মতো একটি ছোট regex-ই কয়েক লাখ state দাবি করতে পারে। দ্বিতীয় পথ Thompson-এর নিজের: NFA-কে state-এর সেট ধরে চালানো, সময় |R| · m-এর অনুপাতে, কোনো বিস্ফোরণ নেই, কিন্তু প্রতি অক্ষরে পুরো সেট হালনাগাদ করতে হয়। তৃতীয় পথ মাঝামাঝি: lazy DFA, যেখানে চলার পথে যে subset আসে শুধু তার সারি বানিয়ে cache-এ রাখা হয়।
তাহলে backtracking কেন? ইতিহাস আর সুবিধা দুটিই কারণ। Perl-এর মতো ভাষার জনপ্রিয়তার সঙ্গে regex-এ এমন সুবিধা আসে, যেমন backreference, যা গণিতের অর্থে regular নয়; সেগুলো কোনো finite automaton দিয়ে করা যায় না। একটি একটি পথ চেষ্টা করা engine-এ এমন বাড়তি সুবিধা যোগ করা সহজ। Backreference-সহ regex মেলানোর সমস্যা সাধারণভাবে NP-complete বলে প্রমাণিত বলে উল্লেখ আছে (Alfred Aho-র ১৯৯০ সালের একটি সমীক্ষায়), তাই সেখানে বহুপদী সময়ের নিশ্চয়তা আশা করাও বাস্তবসম্মত নয়, যদি না P = NP. মূল্য হলো, (a ∪ aa)∗b-এর মতো নিরীহ pattern-এও কিছু ইনপুটে চেষ্টার সংখ্যা ঘাতের হারে বাড়ে।
Russ Cox ২০০৭ সালে “Regular Expression Matching Can Be Simple And Fast” নামের একটি বহুল পঠিত প্রবন্ধে এই পার্থক্য সংখ্যা দিয়ে দেখান আর Thompson-এর পদ্ধতিকে নতুন করে আলোচনায় আনেন। এরপর বেশ কিছু আধুনিক regex library automaton-ভিত্তিক পথ বেছে নেয় আর backreference সমর্থন ইচ্ছাকৃতভাবে বাদ দেয়, যাতে প্রতিটি মেলানোর সময় ইনপুটের দৈর্ঘ্যের সঙ্গে রৈখিক থাকে। অবিশ্বস্ত ইনপুট নেয় এমন সার্ভারে এই নিশ্চয়তা নিরাপত্তার প্রশ্ন; Cybersecurity কোর্সের পর্ব ৪৬-এ ReDoS নিরাপদ কোডিংয়ের অংশ হিসেবে আছে।
মূল উপলব্ধি: Thompson construction প্রতিটি regex-কে একটি ছোট NFA-তে আনে; তারপর কোন পথে চালানো হবে তা একটি প্রকৌশলী সিদ্ধান্ত, যেখানে গতি, মেমরি, বাড়তি সুবিধা আর সবচেয়ে খারাপ ক্ষেত্রের নিশ্চয়তার মধ্যে বেছে নিতে হয়।
প্র ০২ε-তীর ছাড়াই কি regex থেকে NFA বানানো যায়? Thompson আর Glushkov-এর নির্মাণের লেনদেন কী?
যায়, আর এর একটি সুন্দর পথ Glushkov automaton বা position automaton. ধারণাটি হলো regex-এর প্রতিটি চিহ্নের অবস্থানকে আলাদা করে নাম দেওয়া। (a ∪ b)∗abb-এ পাঁচটি অবস্থান: a1, b2, a3, b4, b5. এবার তিনটি সেট হিসাব করা হয়: কোন অবস্থান দিয়ে একটি string শুরু হতে পারে (First), কোন অবস্থানে শেষ হতে পারে (Last), আর কোন অবস্থানের ঠিক পরে কোন অবস্থান আসতে পারে (Follow). এখানে First = {a1, b2, a3}, Last = {b5}, আর যেমন Follow(a1) = {a1, b2, a3}. প্রতিটি অবস্থান একটি state, সঙ্গে একটি শুরু; x থেকে y-তে y-এর চিহ্নে তীর, যদি y ∈ Follow(x). ε-তীর একটিও নেই।
লেনদেনটি স্পষ্ট। Glushkov-এ state-সংখ্যা অবস্থান-সংখ্যা + 1, এখানে ৬টি, Thompson-এর ১৪টির চেয়ে অনেক কম, আর ε না থাকায় simulation-এ closure লাগে না। কিন্তু তীর বাড়তে পারে: প্রতিটি অবস্থানের Follow-সেট বড় হলে তীর অবস্থান-সংখ্যার বর্গের মাপে, যেমন (a1 ∪ a2 ∪ ⋯ ∪ an)∗-ধরনের regex-এ প্রতিটি অবস্থানের পরে সবগুলো আসতে পারে। Thompson-এ তীর সবসময় বড়জোর 4|R|. অর্থাৎ একটি পদ্ধতি state বাঁচায়, অন্যটি তীর।
ইতিহাসে দুটি ধারা প্রায় একই সময়ের। McNaughton আর Yamada-র ১৯৬০ সালের প্রবন্ধে অবস্থান-ভিত্তিক ধারণাটি ছিল, আর V. M. Glushkov-এর ১৯৬১ সালের কাজ সাধারণত এর পূর্ণ রূপ হিসেবে উল্লেখ করা হয়; Thompson এসেছেন ১৯৬৮ সালে, একটি বাস্তব প্রয়োগের প্রয়োজনে। Glushkov-এর আরেকটি সুন্দর ধর্ম আছে: কোনো state-এ ঢোকা সব তীরের label একই চিহ্ন, কারণ তীরের label হলো গন্তব্য অবস্থানের চিহ্ন। এই ধর্ম কিছু hardware বা bit-parallel matching পদ্ধতিতে কাজে লাগে বলে গবেষণায় দেখা যায়। আবার Thompson-এর নির্মাণের সুবিধা হলো প্রমাণ আর কোড দুটিই খুব সরল, আর প্রতিটি state-এর বড়জোর দুটি তীর থাকায় যন্ত্রটি একটি ছোট “instruction”-তালিকার মতো সাজানো যায়।
মূল উপলব্ধি: ε-তীর অপরিহার্য নয়, কিন্তু সুবিধাজনক আঠা। Glushkov কম state আর ε-ছাড়া যন্ত্র দেয়, তীর বেশি হওয়ার ঝুঁকিতে; Thompson বেশি state দেয়, কিন্তু তীর রৈখিক আর গঠন অত্যন্ত নিয়মিত।
প্র ০৩Brzozowski derivative কী, আর regex থেকে সরাসরি DFA বানানোর এই পথ Thompson-এর পথ থেকে কীভাবে আলাদা?
Janusz Brzozowski ১৯৬৪ সালে Journal of the ACM-এ একটি প্রবন্ধে derivative-এর ধারণা দেন। Regex R আর চিহ্ন a-এর derivative ∂aR এমন একটি regex, যার language = {w : aw ∈ L(R)}: “a পড়ার পর বাকি কী মেলাতে হবে”। নিয়মগুলো regex-এর গঠন ধরে recursive: ∂aa = ε, ∂ab = ∅ (b ≠ a), ∂a(R ∪ S) = ∂aR ∪ ∂aS, ∂a(R∗) = (∂aR)R∗; concatenation-এ একটু সতর্কতা: ∂a(RS) = (∂aR)S, আর ε ∈ L(R) হলে তার সঙ্গে ∪ ∂aS. একটি string w গৃহীত কি না জানতে w-এর চিহ্ন ধরে পরপর derivative নিন, শেষ regex-এ ε আছে কি না দেখুন।
এখান থেকে DFA আসে সরাসরি: প্রতিটি derivative একটি state, আর ∂a হলো a-তীর। Brzozowski দেখান, কিছু সরল সরলীকরণের নিয়ম (union-এর সহযোজ্যতা, বিনিময়যোগ্যতা আর একই অংশ দুবার না রাখা) মানলে ভিন্ন ভিন্ন derivative সসীম সংখ্যক, তাই যন্ত্রটি সসীম। এখানে কোনো NFA মাঝপথে বানাতে হয় না, subset construction-ও নয়; regex নিজেই state-এর নাম। তবে সবচেয়ে খারাপ ক্ষেত্রে derivative-এর সংখ্যা ঘাতের হারে হতে পারে, কারণ শেষ পর্যন্ত এটি একটি DFA, আর পর্ব ১০-এর নিম্নসীমা সব DFA-তেই খাটে।
দীর্ঘদিন ধারণাটি পাঠ্যবইয়ের কোণে ছিল। ২০০৯ সালে Owens, Reppy আর Turon-এর “Regular-expression derivatives re-examined” প্রবন্ধ দেখায় যে বাস্তব lexer generator-এ এটি ভালো কাজ করে, আর পরে কিছু functional programming ভাষার টুলে এটি ব্যবহৃত হয় বলে জানা যায়। একটি বড় সুবিধা: intersection আর complement-এর মতো operator-ও derivative-এর নিয়মে সহজে বসে (∂a(¬R) = ¬∂aR), যেখানে Thompson-এর নির্মাণে complement-এর কোনো সরাসরি নিয়ম নেই; NFA-র complement নিতে আগে DFA বানাতে হয় (পর্ব ১০)। Antimirov ১৯৯৬ সালে “partial derivative” দেন, যা একটি regex-কে কয়েকটি ছোট regex-এর সেটে ভাঙে আর একটি ছোট NFA দেয়।
মূল উপলব্ধি: একই language-এর যন্ত্র বানানোর একাধিক রাস্তা আছে: Thompson (ε-NFA, রৈখিক), Glushkov (ε-ছাড়া NFA), Brzozowski (সরাসরি DFA). প্রতিটি পথ সঠিক, কিন্তু কোন operator সহজে বসে, আর মাঝপথে কত বড় যন্ত্র আসে, তাতে তারা আলাদা।
প্র ০৪এই পর্বের প্রমাণে structural induction কেন এত স্বাভাবিকভাবে মিলে গেল? Compiler আর অন্য program-এর সঠিকতা প্রমাণে এই ধারণা কোথায় কাজে লাগে?
Thompson construction নিজেই একটি recursive function: syntax tree-এর প্রতিটি node-এর জন্য সন্তানদের ফল নিয়ে একটি নতুন ফল বানায়। এমন function-এর সঠিকতা প্রমাণের স্বাভাবিক পদ্ধতি হলো একই গঠন ধরে induction: function যে ক্রমে কাজ করে, প্রমাণও সেই ক্রমে চলে। এখানে প্রমাণটি সহজ হওয়ার আসল কারণ Lemma ৪.১-এর invariant: প্রতিটি টুকরোর ঠিক একটি ঢোকার আর একটি বের হওয়ার পথ। এই ধর্মকে বলা যায় compositionality: একটি টুকরোর বাইরের আচরণ তার ভেতরের খুঁটিনাটি না জেনেই বলা যায়। অংশ ৬-এর শর্টকাট এই ধর্মটিই ভাঙে, আর সঙ্গে সঙ্গে প্রমাণও ভাঙে।
একটি compiler-ও ঠিক এভাবে কাজ করে। একটি expression যেমন x + y * z-কে syntax tree-তে ভেঙে প্রতিটি node-এর জন্য কয়েকটি machine instruction বানায়, আর সন্তানদের কোড জুড়ে দেয়। “Compiler সঠিক” দাবিটির অর্থ: প্রতিটি expression-এর জন্য, তৈরি হওয়া কোড চালালে যে মান আসে, সেটি expression-এর গাণিতিক মানের সমান। প্রমাণ আবার structural induction, আর তার চাবিকাঠি আবার একটি invariant, যেমন “প্রতিটি টুকরোর কোড শুধু stack-এর ওপরে একটি মান রেখে যায়, নিচের কিছু ছোঁয় না”। Thompson-এর (I2), (I3)-এর সঙ্গে মিলটি লক্ষ করুন।
এই ধারণা গবেষণায় অনেক দূর গেছে। Xavier Leroy আর সহকর্মীদের CompCert প্রকল্পে (২০০৬ সালের দিক থেকে প্রকাশিত কাজ) C ভাষার একটি বাস্তব compiler-এর সঠিকতা একটি proof assistant-এ যন্ত্রিকভাবে প্রমাণ করা হয়েছে বলে সুপরিচিত; প্রমাণের বড় অংশ এই ধরনের induction. Regex-এর ক্ষেত্রেও Thompson-ধরনের নির্মাণ বা derivative-ভিত্তিক matcher-এর সঠিকতা proof assistant-এ যাচাই করার কাজ প্রকাশিত হয়েছে। এর একটি ব্যবহারিক শিক্ষা: যখন কোনো AI বা সহকর্মী একটি recursive রূপান্তর লিখে দেন, তখন জিজ্ঞেস করুন, “প্রতিটি টুকরো কোন invariant রক্ষা করে?” উত্তর না থাকলে প্রমাণও নেই, আর অংশ ৬-এর মতো লুকোনো ভুল থাকার সম্ভাবনা বেশি।
মূল উপলব্ধি: Recursive নির্মাণের সঠিকতা প্রমাণের চাবিকাঠি একটি ভালো invariant, যা প্রতিটি নিয়ম রক্ষা করে আর যা দিয়ে টুকরোগুলোকে বাইরে থেকে বোঝা যায়। Thompson-এর “এক মুখ ঢোকার, এক মুখ বের হওয়ার” নিয়ম তার একটি ছোট, নিখুঁত উদাহরণ।
প্র ০৫Regex থেকে NFA রৈখিক, NFA থেকে DFA ঘাতের হারে। তাহলে দুটি regex একই language বর্ণনা করে কি না, তা যাচাই করা কত কঠিন? Regex-এ নতুন operator যোগ করলে কী হয়?
সরল পথটি এই পর্ব আর আগের পর্বগুলো মিলিয়ে: দুটি regex থেকে Thompson-এ দুটি NFA, subset construction-এ দুটি DFA, তারপর product construction-এ দেখা কোনো string একটিতে গৃহীত আর অন্যটিতে বাতিল হয় কি না (পর্ব ০৮ আর ২০)। প্রথম ধাপ রৈখিক, শেষ ধাপ DFA-র আকারের গুণফলের অনুপাতে। ঝুঁকি মাঝের ধাপে: DFA ঘাতের হারে বড় হতে পারে। অংশ ৭-এ automata-lib-এর isequal এই ধরনের পরীক্ষাই চালিয়েছে, ছোট উদাহরণে সঙ্গে সঙ্গে উত্তর দিয়ে।
এই ঝুঁকি কি এড়ানো যায়? তত্ত্ব বলে, সাধারণভাবে সম্ভবত না। সাধারণ regex-এর সমতা, এমনকি “এই regex কি Σ∗-এর সমান?” প্রশ্নটিও, PSPACE-complete বলে প্রমাণিত; ফলটি সাধারণত Meyer আর Stockmeyer-এর ১৯৭০-এর দশকের শুরুর কাজের সঙ্গে যুক্ত করা হয়। এর অর্থ, polynomial সময়ের কোনো algorithm থাকলে P = PSPACE হতো, যা এখনো খোলা প্রশ্ন, যদিও বেশিরভাগ বিশেষজ্ঞ এটি অসত্য বলে মনে করেন।
Operator যোগ করলে ছবি আরও নাটকীয়। একই গবেষণায় দেখানো হয়, regex-এ “বর্গ” operator (R2 = RR, লেখায় সংক্ষিপ্ত) যোগ করলে সমতা EXPSPACE-complete হয়ে যায়, কারণ ছোট লেখায় ঘাতের হারে বড় regex লুকিয়ে রাখা যায়: (⋯((a2)2)⋯)2, k বার, মানে a2k. Complement (¬R) যোগ করলে অবস্থা আরও খারাপ: প্রতিটি ¬-এর জন্য একটি করে subset construction লাগতে পারে, আর জটিলতা কোনো নির্দিষ্ট ঘাতের টাওয়ারে বাঁধা থাকে না (non-elementary), যা Stockmeyer-এর ১৯৭৪ সালের গবেষণা হিসেবে উল্লেখ করা হয়। লক্ষ করুন, এই সব operator language-শ্রেণি বাড়ায় না: regular language complement, intersection আর বর্গে বন্ধ (পর্ব ১৬)। বদলায় শুধু বর্ণনার সংক্ষিপ্ততা, আর তার সঙ্গে যাচাইয়ের খরচ।
বাস্তবে তাই ছোট দৈর্ঘ্যের সব string-এ brute force, lazy নির্মাণ আর প্রথম পার্থক্যেই থামা খুব কাজের, যেমনটা এই পর্বের Python ব্লকগুলো করেছে। দুটি DFA-র state m আর k হলে, তারা ভিন্ন হলে দৈর্ঘ্য m · k-এর কম একটি পার্থক্যকারী string থাকবেই; কিন্তু regex থেকে আসা DFA-র m নিজেই বিশাল হতে পারে।
মূল উপলব্ধি: Language-শ্রেণি আর বর্ণনার খরচ দুটি আলাদা প্রশ্ন। Thompson construction regex-কে সস্তায় NFA-তে আনে, কিন্তু দুটি regex তুলনা করা মৌলিকভাবে কঠিন হতে পারে, আর সংক্ষিপ্ত operator যত বাড়ে, কঠিনতা তত বাড়ে।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। প্রতিটি উত্তর উপরের Python ব্লকে regex বদলে বসিয়েও যাচাই করতে পারেন।
-
নির্মাণ: Σ = {a, b}-এর ওপর (ab ∪ b)∗. (ক) Syntax tree লিখুন। (খ) Thompson-এর নিয়মে ε-NFA বানান, state-এর নাম তৈরির ক্রমে q0, q1, … দিয়ে, আর state ও তীর গুনুন। (গ) "", "bab" আর "ba" গৃহীত কি না, ε-closure ধরে দেখান।
(ক) ((a · b) ∪ b)∗: মূলে star, তার নিচে union, union-এর বাঁ দিকে concatenation a · b, ডান দিকে b.
(খ) a: q0 –a→ q1. b: q2 –b→ q3. a · b: ε-তীর q1 → q2; শুরু q0, শেষ q3. দ্বিতীয় b: q4 –b→ q5. Union: নতুন q6, q7; ε q6 → q0, q6 → q4, q3 → q7, q5 → q7. Star: নতুন q8, q9; ε q8 → q6, q8 → q9, q7 → q6, q7 → q9. শুরু q8, accepting শুধু q9. পাতা ৩টি, union ১টি, star ১টি, তাই state 2 · 5 = 10; তীর: চিহ্নের ৩টি, concatenation-এর ১টি, union-এর ৪টি, star-এর ৪টি, মোট ১২টি। Scratch-এর builder-এ হুবহু এই তালিকা এসেছে।
(গ) শুরু: E({q8}) = {q0, q4, q6, q8, q9}; q9 আছে, তাই "" গৃহীত। "bab": b পড়ে q4 → q5, closure {q0, q4, q5, q6, q7, q9}; a পড়ে q0 → q1, closure {q1, q2}; b পড়ে q2 → q3, closure {q0, q3, q4, q6, q7, q9}: q9 আছে, গৃহীত (b · ab). "ba": b-এর পর একই সেট, a-এর পর {q1, q2}, যেখানে q9 নেই: বাতিল, কারণ শেষের a-এর পরে b আসেনি। Scratch-এ simulation-এ এই সেটগুলোই এসেছে।
-
প্রমাণের ভুল ধরুন: দাবি: “Star-এর জন্য নতুন state লাগে না। N(R1)-এ s1 → f1 আর f1 → s1 দুটি ε-তীর যোগ করলেই L(R1)∗ পাওয়া যায়।” যুক্তি: “s1 → f1 দিয়ে ε গৃহীত। আর যেকোনো পথ f1 → s1 লুপে কয়েকবার N(R1) পার হয়, প্রতিবার L(R1)-এর একটি string পড়ে; induction hypothesis-এ প্রতিটি খণ্ড ঠিক। ∎” ভুল কোথায়? একটি পাল্টা-উদাহরণ দিন।
ভুলটি “প্রতিটি খণ্ড N(R1) পার হয়” কথায়। Hypothesis শুধু N(R1)-এর ভেতরে s1 থেকে f1-এর পথ নিয়ে কথা বলে। কিন্তু নতুন তীর দুটি s1-এ ঢোকে আর f1 থেকে বের হয়। যদি N(R1)-এর ভেতরেই এমন কোনো state থাকে যেখান থেকে s1-এ বা যেখানে f1 থেকে ফেরা যায় (ভেতরের কোনো star-এর লুপ), তাহলে একটি পথ একটি খণ্ডের মাঝখান থেকে নতুন তীরে উঠে যেতে পারে। তখন “খণ্ড” আর পূর্ণ s1 ⇝ f1 পথ থাকে না, আর hypothesis খাটে না। আরও মৌলিক কথা: শর্টকাটের টুকরো Lemma ৪.১-এর (I2), (I3) ভাঙে, তাই বাইরের কোনো নিয়মেও আর এই টুকরো নিরাপদে বসানো যায় না।
পাল্টা-উদাহরণ: প্রতিটি star-এ শর্টকাট নিলে (a∗b)∗-এর NFA “a” গ্রহণ করে: sa –a→ fa –ε→ sa (ভেতরের লুপ) –ε→ শেষ (বাইরের বাইপাস, কারণ sa-ই পুরো টুকরোর শুরু)। অথচ (a∗b)∗-এর প্রতিটি অশূন্য string b দিয়ে শেষ হয়। অংশ ৬-এর ব্লক দৈর্ঘ্য ≤ 4-এ “a”, “aa”, “ba”, “aaa” পাল্টা-উদাহরণ দিয়েছে। সংশোধন: Thompson-এর মতো দুটি নতুন state s, f নেওয়া।
-
আউটপুট অনুমান: thompson.py ব্লকে
thompson("(0|1)*1")চালালে লগের শেষ লাইনে শুরু, শেষ, state আর তীর কত হবে? শুরু state-এর ε-closure কী? আর "10" ও "01" গৃহীত কি না?গাছ ((0 ∪ 1)∗ · 1). Postorder: 0 → q0, q1; 1 → q2, q3; union → q4, q5; star → q6, q7; শেষ 1 → q8, q9; concatenation-এ q7 → q8. শেষ লাইন:
. start q6 accept q9 states 10 edges 12. হিসাব: পাতা ৩, union ১, star ১, তাই 2 · 5 = 10টি state; তীর ৩ + ৪ + ৪ + ১ = 12. (DM কোর্সের পর্ব ৭৪-এও একই regex-এ ১০টি state গোনা হয়েছিল।)E({q6}) = {q0, q2, q4, q6, q7, q8}: q6 থেকে q4 আর q7, q4 থেকে q0, q2, আর q7 থেকে q8. "10": 1 পড়ে q2 → q3 আর q8 → q9, closure-এর পর q9 আছে; তারপর 0 পড়ে শুধু q0 → q1, closure {q0, q1, q2, q4, q5, q7, q8}, q9 নেই: বাতিল। "01": 0-এর পর একই সেট, 1-এর পর q9 আছে: গৃহীত। Language “1 দিয়ে শেষ হওয়া string”, তাই উত্তর দুটি সংজ্ঞার সঙ্গেও মেলে। Scratch-এ চালিয়ে এই লাইন আর সেটগুলো মেলানো হয়েছে।
-
নকশা ও প্রমাণ: R+ (এক বা বেশি বার) আর R? (শূন্য বা একবার) সরাসরি Thompson-ধরনের নিয়মে বানান, R+ = RR∗ বা R? = R ∪ ε-তে না ভেঙে। প্রতিটিতে কতটি নতুন state লাগে? Lemma ৪.১-এর চার ধর্ম টিকে থাকে কেন, আর language ঠিক কেন? RR∗ লিখে বানালে আকারে কী সমস্যা?
- R+: নতুন s, f; ε-তীর s → s1, f1 → s1, f1 → f. Star থেকে শুধু বাইপাস s → f বাদ। — “শূন্য বার” পথ সরানো
- R?: নতুন s, f; ε-তীর s → s1, s → f, f1 → f. Star থেকে লুপ f1 → s1 বাদ। — “আবার একবার” পথ সরানো
- ধর্ম: দুটিতেই s আর f নতুন, নতুন তীর s থেকে বের হয় বা f-এ ঢোকে, বা f1 থেকে বের হয় (যেখান থেকে আগে কিছু বের হতো না, I3), তাই (I1)–(I4) টিকে থাকে, ঠিক star-এর প্রমাণের মতো। — Lemma ৪.১-এর যুক্তি
- Language: উপপাদ্য ৪.২-এর star-এর প্রমাণে পথ f1-এ কাটা হয়েছিল। R+-এ বাইপাস না থাকায় খণ্ড k ≥ 1, তাই L(R1)+; R?-এ লুপ না থাকায় খণ্ড k ∈ {0, 1}, তাই {ε} ∪ L(R1). ∎ — পথ কাটা, hypothesis
দুটিতেই ২টি নতুন state. RR∗ লিখে বানালে R-এর টুকরো দুবার তৈরি হয়, তাই আকার প্রায় দ্বিগুণ; (((R+)+)+)-এর মতো নেস্টিংয়ে এই দ্বিগুণ হওয়া বারবার ঘটে আর আকার ঘাতের হারে বাড়ে। সরাসরি নিয়মে আকার রৈখিক থাকে। Scratch-এ দুটি নিয়ম a∗b, ab, (a ∪ b)a, ε আর ∅-এর ওপর দৈর্ঘ্য ≤ 7-এর সব string-এ Python-এর
re-এর সঙ্গে মেলানো হয়েছে: অমিল 0.
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি regex থেকে Thompson construction হয়ে DFA পর্যন্ত যাওয়ার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- Precedence মেনে regex-কে syntax tree-তে ভাঙা
- প্রতিটি পাতার (চিহ্ন, ε বা ∅) জন্য দুই state-এর ভিত্তি-টুকরো বানানো
- নিচ থেকে ওপরে union, concatenation আর star-এর নিয়মে টুকরো জোড়া
- মূল node-এর টুকরোটিকে এক শুরু ও এক accepting state-এর ε-NFA হিসেবে নেওয়া
- শুরুর ε-closure থেকে subset construction চালিয়ে DFA বানানো
Thompson construction-এ (concatenation-এ ε-তীর, state না মিশিয়ে) Σ = {a, b}-এর ওপর regex (a ∪ b)∗-এর ε-NFA-তে কতটি state?
- 4
- 6
- 8
- 10
Thompson construction-এ N(R1) (শুরু s1, শেষ f1) আর N(R2) (শুরু s2, শেষ f2) থেকে N(R1R2) বানাতে কী যোগ করা হয়?
- একটি নতুন শুরু state, সেখান থেকে s1 আর s2-এ ε-তীর
- একটি ε-তীর f1 → s2
- একটি ε-তীর f2 → s1
- একটি ε-তীর s1 → s2
কেউ Kleene star-এর নিয়মে নতুন state না নিয়ে শুধু s1 → f1 আর f1 → s1 দুটি ε-তীর যোগ করেন, প্রতিটি star-এ। তাঁর (a∗b)∗-এর NFA নিচের কোন string ভুলভাবে গ্রহণ করে?
- ε
- ab
- bb
- a
Thompson construction সরাসরি Kleene-এর উপপাদ্যের কোন অংশ প্রমাণ করে?
- প্রতিটি regex-এর language কোনো ε-NFA চেনে
- প্রতিটি DFA-র language কোনো regex দিয়ে লেখা যায়
- প্রতিটি NFA-র সমতুল্য একটি DFA আছে
- প্রতিটি regular language-এর একটি অনন্য সবচেয়ে ছোট DFA আছে
|R| আকারের একটি regex-এর Thompson ε-NFA ব্যবহার করে, state-এর সেট ধরে simulation-এ, দৈর্ঘ্য m-এর একটি string গৃহীত কি না ঠিক করতে কত সময় লাগে?
- m-এর অনুপাতে, |R|-এর ওপর নির্ভর না করে
- |R| · m-এর অনুপাতে
- 2|R| · m-এর অনুপাতে
- 2m-এর অনুপাতে
Thompson construction-এর প্রতিটি টুকরোর কোন ধর্মটি তার সঠিকতার প্রমাণে (union, concatenation আর star-এর পথ ভাগ করার যুক্তিতে) সবচেয়ে জরুরি?
- টুকরোতে ε-তীরের সংখ্যা বড়জোর চিহ্নের সংখ্যার সমান
- টুকরোটি deterministic
- শুরুতে কোনো তীর ঢোকে না, আর একমাত্র accepting state থেকে কোনো তীর বের হয় না
- টুকরোর প্রতিটি state accepting
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Thompson construction: regex-এর syntax tree ধরে নিচ থেকে ওপরে; ভিত্তি ∅, ε, a (দুই state), আর union, concatenation, star ε-তীর দিয়ে জোড়া।
- প্রতিটি টুকরোর এক শুরু, এক accepting state; শুরুতে তীর ঢোকে না, শেষ থেকে বের হয় না। এই invariant-ই প্রমাণের চাবিকাঠি।
- Structural induction-এ L(N(R)) = L(R): Kleene-এর উপপাদ্যের “regex ⇒ automaton” দিক।
- State ঠিক 2(পাতা + union + star) ≤ 2|R|, তীর ≤ 4|R|; simulation |R| · m সময়ে, কোনো বিস্ফোরণ ছাড়া।
- Star-এ নতুন state বাদ দেওয়ার শর্টকাট ভুল ((a∗b)∗-এ “a”); DFA পেতে ε-closure-সহ subset construction.
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ১০ · NFA থেকে DFA — subset construction আর state বিস্ফোরণফিরে দেখুনThompson NFA-কে DFA বানানোর পদ্ধতি আর 2n state-এর নিম্নসীমা।
- পর্ব ১৫ · Automaton থেকে regex — state elimination আর Arden-এর সূত্রপরের পর্বউল্টো দিকের রূপান্তর, যা Kleene-এর উপপাদ্য সম্পূর্ণ করে।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ১৫ automaton থেকে regex.
- পর্ব ০৪ · Theory of Computation-এর প্রমাণ — string-এর ওপর induction, construction আর diagonalizationভিত্তিএই পর্বের structural induction আর construction proof-এর পদ্ধতি।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৪ — Finite automaton আর regular expression-এর পরিচয়পটভূমিThompson-এর নিয়ম আর Kleene-এর উপপাদ্যের একটি ছোট প্রথম পরিচয়।
- Python প্রোগ্রামিং · পর্ব ৩০ — regular expressionপাশের ট্র্যাকবাস্তব regex-এর syntax আর re module হাতে-কলমে।
- DSA · পর্ব ৫৮ — String matchingগভীরে যানএকটি নির্দিষ্ট pattern খোঁজার দ্রুত algorithm, যার পেছনেও automaton-এর ধারণা।