সরাসরি পর্বে যান
পর্ব ১৩ · ৮৫-এর মধ্যে · মডিউল ৩

Regular expression — formal definition আর বীজগণিত

Regular Expressions — Inductive Syntax and Semantics, Precedence, Design, Identities with Proofs, and Formal vs Practical Regex

Taught in Bangla, this lesson defines regular expressions formally, with recursive syntax over ∅, ε, symbols, union, concatenation and star and a semantics L(R), and proves facts by structural induction. It fixes operator precedence, designs regexes from descriptions, and separates true identities such as (R*)* ≡ R* from false ones such as (RS)* ≡ R*S*. In-page Python (Pyodide) computes L(R) and hunts counterexamples, and a browser check shows why validation needs fullmatch rather than ^…$.

এই পর্বে যা শিখবেন

  • Regular expression-এর recursive syntax আর L(R)-এর সংজ্ঞা লেখা, আর ছোট regex-এর language হাতে বের করা
  • অগ্রাধিকার আর বন্ধনী ঠিকভাবে পড়া, আর একটি regex-এর syntax tree আঁকা
  • “জোড়সংখ্যক 0” বা “পরপর দুটি 1 নেই”-এর মতো বর্ণনা থেকে regex নকশা করা
  • Regex-এর অভেদ প্রমাণ করা আর ভুল অভেদের সবচেয়ে ছোট পাল্টা-উদাহরণ খুঁজে বের করা
  • গণিতের regex আর Python/JavaScript-এর regex-এর পার্থক্য বোঝা, আর validator লেখার ফাঁদ চেনা

১ · কেন regular expression — language-এর ছোট সূত্র

মডিউল ২-এ আপনি language চিনেছেন যন্ত্র দিয়ে: একটি DFA বা NFA একটি একটি চিহ্ন পড়ে আর শেষে “গ্রহণ” বা “বাতিল” বলে। যন্ত্র দারুণ, কিন্তু একটি সমস্যা আছে। “বাজারঘরের অর্ডার কোড BG- দিয়ে শুরু, তারপর চারটি অঙ্ক” কথাটি বোঝাতে আট-নয়টি state-এর ছবি আঁকতে হয়। মানুষ সাধারণত এভাবে ভাবে না। আমরা ভাবি গঠন দিয়ে: “এটা, তারপর ওটা, তারপর এর যেকোনো একটি, যতবার খুশি।”

বাজারের ফর্দের কথা ভাবুন। মা লিখে দিলেন: “চাল, তারপর ডাল অথবা ছোলা, তারপর যত খুশি ডিম।” এই এক লাইনে তিনটি কাজ আছে: পরপর বসানো (চাল তারপর ডাল), বিকল্প বেছে নেওয়া (ডাল অথবা ছোলা), আর পুনরাবৃত্তি (যত খুশি ডিম, শূন্যটিও চলে)। Regular expression ঠিক এই তিনটি কাজের গাণিতিক রূপ: concatenation, union আর star. ফর্দটি দোকানদার যেভাবে খুশি মেলাতে পারেন; regex-ও শুধু বলে কী মিলবে, কীভাবে মেলাতে হবে তা নয়।

এই পর্বের প্রশ্নগুলো গাণিতিক। একটি regex ঠিক কী? সে কোন language বোঝায়? দুটি regex কখন একই language বোঝায়, আর তা প্রমাণ বা খণ্ডন করব কীভাবে? এর পরের দুই পর্বে একটি বড় উপপাদ্য আসবে: regex দিয়ে ঠিক সেই language-গুলোই লেখা যায়, যেগুলো finite automaton চেনে। পর্ব ১৪ দেখাবে regex থেকে NFA বানানোর পদ্ধতি, আর পর্ব ১৫ উল্টো দিক। এই পর্বে ভিত্তি গড়া হবে: সংজ্ঞা, পড়ার নিয়ম, নকশা আর বীজগণিত।

এই পর্বের notation: Σ একটি alphabet, ε ফাঁকা string (কিছু বইয়ে λ), ∅ ফাঁকা language. Language-এর union, concatenation LM আর Kleene star L∗-এর সংজ্ঞা ও মৌলিক ধর্ম পর্ব ০৩-এ আছে; এখানে সেগুলো ধরে নেওয়া হলো। Regex-এ union লেখা হবে “∪” দিয়ে। অনেক বইয়ে একই জিনিস “+” দিয়ে লেখা হয়, আর বাস্তবের টুলে “|” দিয়ে। DFA আর NFA-এর notation আগের পর্বগুলোর মতোই। Discrete Math কোর্সের পর্ব ৭৪-এ regex-এর একটি ছোট প্রথম পরিচয় আছে; এখানে অনেক গভীরে যাওয়া হবে।

২ · Formal সংজ্ঞা — syntax আর semantics

সংজ্ঞাটি দুই স্তরে। প্রথম স্তর syntax: কোন লেখাগুলো বৈধ regular expression. এখানে ∅, ε, ∪, ∗ আর বন্ধনী শুধু চিহ্ন, তাদের কোনো অর্থ নেই; ধরে নেওয়া হয় এরা Σ-এর বাইরের চিহ্ন। দ্বিতীয় স্তর semantics: প্রতিটি বৈধ লেখা কোন language বোঝায়। এই পার্থক্য প্রোগ্রামিংয়ের মতোই: x + 1 একটি লেখা, আর তার মান অন্য জিনিস।

সংজ্ঞা ২.১ (regular expression-এর syntax)

Σ-এর ওপর regular expression-এর সেট নিচের নিয়মে গড়া:
ভিত্তি: (১) ∅ একটি regex. (২) ε একটি regex. (৩) প্রতিটি a ∈ Σ একটি regex.
গঠনের নিয়ম: R1 আর R2 regex হলে (৪) (R1 ∪ R2), (৫) (R1R2) আর (৬) (R1)∗ regex.
সীমা: এই ছয় নিয়ম সসীম বার প্রয়োগ করে যা পাওয়া যায়, শুধু সেগুলোই regex.

এটি একটি recursively defined set, পর্ব ০৪-এর সুষম বন্ধনীর সেটের মতো। তাই এর প্রতিটি সদস্য সম্পর্কে কোনো দাবি প্রমাণ করা যায় structural induction দিয়ে: তিনটি ভিত্তি-ক্ষেত্রে দাবিটি দেখানো, আর তিনটি নিয়মের প্রতিটিতে দেখানো যে অংশে সত্য হলে পুরোটিতেও সত্য।

সংজ্ঞা ২.২ (regex-এর language, L(R))

L(∅) = ∅,  L(ε) = {ε},  L(a) = {a} প্রতিটি a ∈ Σ-এর জন্য;
L(R1 ∪ R2) = L(R1) ∪ L(R2),  L(R1R2) = L(R1)L(R2),  L(R1∗) = L(R1)∗.

কথায়: ∅ কিছুই মেলায় না; ε শুধু ফাঁকা string মেলায়; a শুধু এক-চিহ্নের string “a” মেলায়। Union মানে “এটি অথবা ওটি”, concatenation মানে “এটির পরে ওটি”, আর star মানে “শূন্য বা তার বেশি বার”। লক্ষ করুন, বাঁ দিকের ∪ আর ∗ regex-এর চিহ্ন, ডান দিকের ∪ আর ∗ language-এর operation. একই চিহ্ন দুই কাজে লাগানো সুবিধাজনক, কিন্তু প্রথমবার পড়ার সময় এই পার্থক্য মনে রাখুন।

কয়েকটি সংক্ষেপ সবাই ব্যবহার করে। R+ মানে RR∗ (অন্তত একবার); Rk মানে R পরপর k বার; Σ নিজেও একটি regex-এর সংক্ষেপ, Σ = {a1, …, ak} হলে (a1 ∪ ⋯ ∪ ak). তাই Σ∗ সব string-এর regex. এগুলো নতুন শক্তি আনে না, শুধু লেখা ছোট করে। যে language কোনো regex-এর L(R), তাকে regex-বর্ণনাযোগ্য বলা যায়; পর্ব ১৪–১৫-এ প্রমাণ হবে যে এরাই ঠিক regular language.

প্রথম structural induction — regex কখন ε মেলায়?

অনেক কাজে জানা দরকার, ε ∈ L(R) কি না। যেমন R+ আর R∗ কখন সমান, বা পর্ব ১৫-এর Arden-এর সূত্রের শর্ত। এর জন্য একটি সরল recursive পরীক্ষা ν (“nu”) আছে, যাকে বলে nullable পরীক্ষা:

ν(∅) = না, ν(ε) = হ্যাঁ, ν(a) = না;  ν(R ∪ S) = ν(R) অথবা ν(S);  ν(RS) = ν(R) এবং ν(S);  ν(R∗) = হ্যাঁ
Lemma ২.৩

প্রতিটি regex R-এর জন্য ε ∈ L(R) ⇔ ν(R) = হ্যাঁ।

প্রমাণ (R-এর গঠনের ওপর structural induction):

  1. ভিত্তি: L(∅) = ∅-এ ε নেই, ν(∅) = না। L(ε) = {ε}-এ ε আছে, ν(ε) = হ্যাঁ। L(a) = {a}-এ ε নেই, কারণ |a| = 1; ν(a) = না। — সংজ্ঞা ২.২-এর প্রথম তিন লাইন
  2. Hypothesis: R আর S-এর জন্য দাবিটি সত্য ধরুন। — অংশে সত্য ধরা
  3. Union: ε ∈ L(R) ∪ L(S) ⇔ ε ∈ L(R) অথবা ε ∈ L(S) ⇔ ν(R) অথবা ν(S). — union-এর সংজ্ঞা, তারপর hypothesis
  4. Concatenation: ε = uv হলে |u| + |v| = 0, তাই u = v = ε. অর্থাৎ ε ∈ L(R)L(S) ⇔ ε ∈ L(R) এবং ε ∈ L(S) ⇔ ν(R) এবং ν(S). — দৈর্ঘ্য যোগ হয়, তারপর hypothesis
  5. Star: L(R)∗-এ শূন্যটি টুকরো জুড়লে ε আসে, তাই ε সবসময় আছে; ν(R∗) = হ্যাঁ। — Kleene star-এর সংজ্ঞা, পর্ব ০৩
  6. ছয়টি নিয়মেই দাবি টিকে থাকে, তাই প্রতিটি regex-এ সত্য। ∎

উদাহরণ: ν((ab)∗ ∪ a) = হ্যাঁ, কারণ star-এর অংশটি ε মেলায়; ν(a∗b) = না, কারণ b-অংশ ε মেলায় না। প্রমাণটি ছোট, কিন্তু কৌশলটি এই মডিউলের প্রায় প্রতিটি প্রমাণে ফিরবে, বিশেষ করে পর্ব ১৪-এ Thompson construction-এর সঠিকতায়।

Regular expression-এর ধারণা গণিতবিদ Stephen Kleene-এর। তিনি ১৯৫১ সালে RAND Corporation-এর একটি গবেষণা-প্রতিবেদনে, পরে ১৯৫৬ সালে “Automata Studies” সংকলনে প্রকাশিত “Representation of Events in Nerve Nets and Finite Automata” প্রবন্ধে, McCulloch আর Pitts-এর (১৯৪৩) স্নায়ু-জালের মডেল কোন “ঘটনা” চিনতে পারে, সেই প্রশ্নের উত্তর দেন। তিনি এগুলোকে বলেছিলেন “regular events”; সেখান থেকেই “regular” শব্দটি এসেছে বলে সাধারণত বলা হয়। Kleene-এর মূল চিহ্নগুলো আজকের মতো ছিল না; আজকের রূপ পরের বইগুলোতে ধীরে ধীরে দাঁড়িয়েছে।

৩ · অগ্রাধিকার, বন্ধনী আর syntax tree

সংজ্ঞা ২.১ মানলে প্রতিটি regex বন্ধনীতে মোড়া থাকে: ((a ∪ (b(c)∗))). এভাবে লেখা কষ্টকর, তাই পাটিগণিতের মতো একটি operator precedence বা অগ্রাধিকারের নিয়ম মানা হয়:

star (∗) > concatenation > union (∪)

পাটিগণিতে যেমন 2 + 3 × 42-এ আগে ঘাত, তারপর গুণ, শেষে যোগ, এখানেও তেমন। star সবচেয়ে কাছের অংশটিকে আঁকড়ে ধরে: ab∗-এ star শুধু b-এর ওপর। concatenation union-এর চেয়ে শক্ত: a ∪ bc মানে a ∪ (bc), (a ∪ b)c নয়। concatenation আর union দুটিই associative, তাই abc বা a ∪ b ∪ c-তে বন্ধনীর দরকার নেই। প্রতিটি regex-কে একটি syntax tree হিসেবে আঁকা যায়, যার পাতায় ∅, ε বা চিহ্ন, আর ভেতরের node-এ operation.

একই চিহ্ন, আলাদা বন্ধনী, আলাদা গাছ

হলুদ node হলো operation (· মানে concatenation), নীল node পাতা। language নিচ থেকে ওপরে হিসাব হয়।

Syntax trees of a ∪ bc* and (a ∪ b)c* a ∪ bc∗ (a ∪ b)c∗ ∪·∗ abc ·∪∗ abc
ছবি ১৩.১ — বাঁয়ের গাছে L = {a, b, bc, bcc, …}: a, অথবা b-এর পরে যত খুশি c. ডানের গাছে L = {a, b, ac, bc, acc, bcc, …}: a বা b, তারপর যত খুশি c. দৈর্ঘ্য ৩ পর্যন্ত প্রথমটিতে ৪টি, দ্বিতীয়টিতে ৬টি string.

এবার একটি ছোট regex-এর language নিচ থেকে ওপরে, গাছ ধরে, ধাপে ধাপে বের করা যাক। R = (a ∪ b)a∗, Σ = {a, b}. L(R) অসীম, তাই দৈর্ঘ্য ≤ 3 পর্যন্ত কাটা হবে। শেষ ধাপে দেখবেন বন্ধনী সরালে কী হয়।

1পাতা: a, b2union: a ∪ b3star: a∗4জোড়া: (a ∪ b)a∗5ফল, shortlex ক্রমে6বন্ধনী ছাড়া: a ∪ ba∗
এই ধাপের হিসাব
উপ-regex
language (≤ 3)
string-সংখ্যা
  1. পাতা। গাছের নিচে দুটি পাতা, a আর b. সংজ্ঞা অনুযায়ী L(a) = {a}, L(b) = {b}, প্রতিটিতে একটি করে string.
  2. Union. L(a ∪ b) = {a} ∪ {b} = {a, b}. Union-এ কিছু জোড়া লাগে না, শুধু দুই সেট মেলানো হয়।
  3. Star. L(a∗) = {ε, a, aa, aaa, …}; দৈর্ঘ্য ≤ 3 পর্যন্ত চারটি। শূন্যবার a মানে ε, তাই ε থাকবেই।
  4. Concatenation. বাঁয়ের ২টি থেকে একটি, ডানের ৪টি থেকে একটি: ৮টি জোড়া। aaaa আর baaa-এর দৈর্ঘ্য 4, তাই বাদ; ৬টি টেকে।
  5. ফল। shortlex ক্রমে a, b, aa, ba, aaa, baa. বর্ণনা: “প্রথম চিহ্ন a বা b, তারপর শুধু a” ধরনের string. প্রতিটি দৈর্ঘ্য k ≥ 1-এ ঠিক ২টি string, আর ε নেই।
  6. বন্ধনী সরালে। a ∪ ba∗ মানে a ∪ (b(a∗)), কারণ concatenation union-এর চেয়ে শক্ত। এর language {a, b, ba, baa, …}: aa আর aaa নেই। একটি বন্ধনী language বদলে দিয়েছে।

এই হিসাব হাতে করা যায়, কিন্তু ভুলও সহজে হয়। নিচের ব্লকে একটি ছোট Python regex-semantics evaluator আছে: একটি parser, যা regex-কে syntax tree বানায় (অগ্রাধিকার মেনে), আর একটি function lang, যা সংজ্ঞা ২.২ হুবহু নকল করে L(R)-এর দৈর্ঘ্য ≤ n অংশ ফেরত দেয়। এটি Python-এর re module ব্যবহার করে না; ∪, ∗, ε আর ∅ এখানে গণিতের অর্থে। পরের একটি ব্লক এই function-গুলোই আবার ব্যবহার করবে (data-shared), তাই আগে এটি চালান।

def parse(R):                 # formal regex: ∅ ε symbols ∪ (or +) ∗ (or *) ( )
    t = list(R.replace(" ", ""))
    look = lambda: t[0] if t else None
    def union():
        node = concat()
        while look() in ("∪", "+"):
            t.pop(0); node = ("∪", node, concat())
        return node
    def concat():
        node = ("ε",)
        while look() not in (None, ")", "∪", "+"):
            node = ("·", node, star())
        return node
    def star():
        c = t.pop(0)
        node = union() if c == "(" else ("∅",) if c == "∅" else ("ε",) if c == "ε" else ("sym", c)
        if c == "(": t.pop(0)             # the closing ")"
        while look() in ("∗", "*"):
            t.pop(0); node = ("∗", node)
        return node
    return union()
def lang(e, n):               # L(e), cut at length n
    op = e[0]
    if op in ("∅", "ε", "sym"): return {"∅": set(), "ε": {""}, "sym": {e[-1]}}[op]
    if op == "∪": return lang(e[1], n) | lang(e[2], n)
    A = lang(e[1], n)
    if op == "·": return {x + y for x in A for y in lang(e[2], n) if len(x + y) <= n}
    S = {""}                          # star: keep gluing until nothing new
    while (T := S | {x + y for x in S for y in A if len(x + y) <= n}) != S: S = T
    return S
L = lambda R, n: sorted(lang(parse(R), n), key=lambda w: (len(w), w))
show = lambda ws: "{" + ", ".join(w or "ε" for w in ws) + "}"
for R, n in [("(a∪b)a∗", 3), ("a∪ba∗", 3), ("ab∗", 3), ("(ab)∗", 4),
             ("a∪bc∗", 3), ("∅∗", 3), ("a∅", 3), ("1∗(01∗01∗)∗", 4)]:
    print(f"L({R}) up to {n}: {show(L(R, n))}")

আসল আউটপুট (ব্রাউজারের Python):

L((a∪b)a∗) up to 3: {a, b, aa, ba, aaa, baa}
L(a∪ba∗) up to 3: {a, b, ba, baa}
L(ab∗) up to 3: {a, ab, abb}
L((ab)∗) up to 4: {ε, ab, abab}
L(a∪bc∗) up to 3: {a, b, bc, bcc}
L(∅∗) up to 3: {ε}
L(a∅) up to 3: {}
L(1∗(01∗01∗)∗) up to 4: {ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111}

প্রথম দুই লাইন stepper-এর শেষ দুই ধাপ হুবহু মেলায়: বন্ধনী সরাতেই aa আর aaa হারিয়ে গেছে। ab∗ আর (ab)∗-এর পার্থক্য স্পষ্ট: প্রথমটিতে একটি a আর যত খুশি b, দ্বিতীয়টিতে ab টুকরোটি যতবার খুশি। ∅∗-এর ফল {ε}: ∅ থেকে কোনো টুকরো নেওয়া যায় না, কিন্তু শূন্যটি টুকরো জোড়া সবসময় চলে। আর a∅ ফাঁকা: concatenation-এ এক দিক ফাঁকা হলে জোড়ার কোনো সঙ্গী নেই। শেষ লাইনের regex-টি অংশ ৪-এ নকশা করা হবে; দৈর্ঘ্য ≤ 4-এ ১৬টি string, প্রতিটিতে জোড়সংখ্যক 0. কোডের parser-এ concat ফাঁকা হলে ε ফেরত দেয়, তাই "(ε∪1)" বা "()" দুটিই চলে। star-এর loop থামে কারণ দৈর্ঘ্য ≤ n-এর string সসীম।

৪ · বর্ণনা থেকে regex — নকশার কৌশল

পরীক্ষায় আর কাজে সবচেয়ে বেশি আসে উল্টো প্রশ্ন: একটি বর্ণনা দেওয়া আছে, regex লিখুন। কোনো যান্ত্রিক রেসিপি নেই, কিন্তু কয়েকটি নকশা বারবার কাজে লাগে। নিচের টেবিলের প্রতিটি regex scratch-এ দৈর্ঘ্য ≤ 10-এর সব string-এ একটি Python সংজ্ঞার সঙ্গে মেলানো হয়েছে।

বর্ণনাRegexভাবনা
aba substring হিসেবে আছে(a ∪ b)∗aba(a ∪ b)∗আগে যা খুশি, মাঝে নমুনা, পরে যা খুশি
a দিয়ে শুরু, b দিয়ে শেষa(a ∪ b)∗bদুই প্রান্ত স্থির, মাঝখান মুক্ত
দৈর্ঘ্য বড়জোর ২(ε ∪ a ∪ b)(ε ∪ a ∪ b)প্রতিটি ঘর ফাঁকাও থাকতে পারে
দৈর্ঘ্য জোড়((a ∪ b)(a ∪ b))∗দুই চিহ্নের ব্লক, যতবার খুশি
b বড়জোর একটিa∗(ε ∪ b)a∗ঐচ্ছিক অংশ মানে (ε ∪ R)
পরপর দুটি 1 নেই(0 ∪ 10)∗(ε ∪ 1)প্রতিটি 1-এর পরে 0, শুধু শেষেরটি ছাড়া
ঠিক দুটি 10∗10∗10∗নির্দিষ্ট চিহ্ন বসিয়ে ফাঁকে বাকিগুলো

সাধারণ কৌশলটি তিন ধাপের। প্রথমে কয়েকটি ছোট সদস্য আর অসদস্য লিখে ফেলুন, ε-সহ। তারপর string-কে স্বাভাবিক টুকরোয় ভাগ করুন: কোন অংশ স্থির, কোন অংশ পুনরাবৃত্ত, কোথায় বিকল্প। শেষে প্রতিটি টুকরোর regex লিখে জোড়া লাগান, আর তালিকার প্রতিটি উদাহরণ মিলিয়ে দেখুন। নিচে একটি পূর্ণ উদাহরণ: Σ = {0, 1}-এর ওপর “0-এর সংখ্যা জোড়”, বাজারঘরের ভাষায় একটি parity-check লাইন, যেখানে 0 মানে “সংকেত বন্ধ হলো”।

1সদস্য আর অসদস্য লেখা2প্রথম 0-এর আগের অংশ3দুটি 0-এর একটি ব্লক4জোড়া লাগানো5একটি সদস্য ভেঙে দেখা6সব string-এ যাচাই
এই ধাপের অবস্থা
regex-এর টুকরো
উদাহরণ
শর্ত
  1. উদাহরণ। ε (শূন্যটি 0, শূন্য জোড়), 1, 00, 101 সদস্য; 0, 10, 000 সদস্য নয়। ε-কে ভুলে যাওয়া এই ধরনের নকশার সবচেয়ে সাধারণ ভুল।
  2. শুরুর অংশ। প্রথম 0-এর আগে যত খুশি 1 থাকতে পারে, একটিও না থাকতে পারে: 1∗. কোনো 0 না থাকলে পুরো string এখানেই শেষ।
  3. ব্লক। এরপর 0-গুলোকে জোড়ায় জোড়ায় ভাগ করুন। একটি জোড়া মানে 0, তারপর কিছু 1, তারপর আরেকটি 0, তারপর কিছু 1: 01∗01∗. প্রতিটি ব্লকে ঠিক দুটি 0.
  4. জোড়া লাগানো। ব্লক শূন্য বা বেশি বার: 1∗(01∗01∗)∗. k-টি ব্লক মানে 2k-টি 0, তাই 0-এর সংখ্যা সবসময় জোড়; উল্টো দিকে, জোড়সংখ্যক 0-এর যেকোনো string ঠিক এভাবে ভাগ হয়।
  5. পরীক্ষা: 10110. শুরুর 1∗ = “1”, তারপর একটি ব্লক: 0, 1∗ = “11”, 0, 1∗ = ε. ভাগটি বৈধ, তাই 10110 ∈ L. দুটি 0, জোড়।
  6. যাচাই। দৈর্ঘ্য 0 থেকে 10-এর ২০৪৭টি string-এর মধ্যে ঠিক ১০২৪টিতে জোড়সংখ্যক 0, আর regex ঠিক সেগুলোই মেলায় (অংশ ৬-এর ব্লকের আউটপুট)। (1 ∪ 01∗0)∗ আরেকটি সঠিক উত্তর।

ধাপ ৪-এ “উল্টো দিক” শব্দটি গুরুত্বপূর্ণ। একটি নকশার সঠিকতা প্রমাণে দুটি দিক লাগে: regex যা মেলায় তা সবই language-এ (sound), আর language-এর সবকিছুই regex মেলায় (complete). প্রথমটি সাধারণত সহজ, দ্বিতীয়টিতেই ভুল লুকিয়ে থাকে। যেমন (1∗01∗0)∗ লিখলে সব সদস্যেই জোড়সংখ্যক 0, কিন্তু “1” বাদ পড়ে, কারণ প্রতিটি অশূন্য সদস্য 0 দিয়ে শেষ হয়।

DFA দেখে regex — অনানুষ্ঠানিকভাবে

একটি ছোট DFA থাকলে regex প্রায়ই তার loop পড়ে লেখা যায়। “জোড়সংখ্যক 0”-এর DFA-তে দুটি state: q0 (এ পর্যন্ত জোড়, শুরু ও accepting) আর q1 (বিজোড়)। 1 পড়লে state বদলায় না, 0 পড়লে বদলায়।

“জোড়সংখ্যক 0”-এর ২-state DFA

q0 থেকে বেরিয়ে আবার q0-তে ফেরার দুই রকম পথ: 1, অথবা 0 1∗ 0.

Two-state DFA for an even number of 0s q0q1 11 00
ছবি ১৩.২ — q0-তে শুরু আর শেষ এমন প্রতিটি পথ কয়েকটি “ফেরার ঘুর” জুড়ে বানানো: প্রতিটি ঘুর হয় 1, নয়তো 0 1∗ 0. তাই L = (1 ∪ 01∗0)∗.

কৌশলটি: শুরু থেকে accepting state-এ যাওয়ার প্রতিটি পথকে “ফেরার ঘুর”-এ ভাগ করা। q0 থেকে q0-তে ফেরার সরলতম ঘুর দুই রকম: সরাসরি 1, অথবা 0 পড়ে q1-এ গিয়ে সেখানে যত খুশি 1 পড়ে আবার 0-তে ফেরা। ফলে (1 ∪ 01∗0)∗. বড় DFA-তে এই চোখে-দেখা পদ্ধতি দ্রুত জটিল হয়ে যায়; পর্ব ১৫-এর state elimination এটিকেই একটি নিশ্চিত algorithm বানায়।

৫ · বাজারঘরের format আর ব্রাউজারে যাচাই

বাজারঘরের তিনটি format গণিতের regex-এ লেখা যাক। D দিয়ে বোঝানো হলো যেকোনো একটি অঙ্ক, অর্থাৎ D = (0 ∪ 1 ∪ ⋯ ∪ 9), আর Γ দিয়ে কুপনের যেকোনো একটি চিহ্ন, Γ = (A ∪ ⋯ ∪ Z ∪ 0 ∪ ⋯ ∪ 9).

  • অর্ডার কোড: BG-DDDD. এখানে B, G আর “-” সাধারণ চিহ্ন, পরপর বসানো। L-এ ঠিক 104 = ১০,০০০টি string; একটি সসীম language, আর প্রতিটি সসীম language regular (সব সদস্যের union লিখলেই হয়)।
  • কুপন: ছয় চিহ্নের কোড, যার ভেতরে SALE আছে: ΓΓSALE ∪ ΓSALEΓ ∪ SALEΓΓ. SALE নিজের সঙ্গে উপরিপাতে মেলে না (তার শুরুর কোনো অংশ শেষের অংশের সমান নয়), আর ছয় ঘরে দুটি SALE ধরে না, তাই তিন অংশ আলাদা; মোট 3 × 362 = ৩,৮৮৮টি কুপন।
  • ফোন নম্বরের মতো একটি কাল্পনিক format: 01, তারপর 3 থেকে 9-এর একটি অঙ্ক, তারপর আরও আটটি অঙ্ক: 01(3 ∪ 4 ∪ ⋯ ∪ 9)D8. বাস্তবের টুলে এটিই 01[3-9][0-9]{8}.

শেষ লাইনে বাস্তবের সংক্ষেপগুলো দেখা যাচ্ছে: [3-9] একটি character class, যা শুধু একটি লম্বা union-এর সংক্ষেপ, আর {8} মানে আটবার পরপর বসানো। এগুলো গণিতের শক্তি বাড়ায় না। গণিতের regex আর বাস্তবের regex যে একই কথা বলছে, তা পরীক্ষা করা যায় ব্রাউজারেই: JavaScript-এর RegExp একটি সত্যিকারের regex engine. নিচের ব্লক কয়েকটি formal regex-কে JavaScript syntax-এ অনুবাদ করে (∪ হলো |, ε হলো ফাঁকা বিকল্প), আর প্রতিটিকে একটি সরল সংজ্ঞার সঙ্গে মেলায়: দৈর্ঘ্য ≤ 12-এর সব binary string, আর স্থির seed-এর ৩,০০০টি লম্বা দৈব string. তৃতীয় সারিতে একটি “AI-এর দেওয়া” উত্তর আছে।

// Formal regex -> JS syntax: ∪ becomes |, ε becomes an empty alternative,
// and ^(?: … )$ forces a match of the WHOLE string (formal semantics).
const cases = [
  ["even 0s",     "1∗(01∗01∗)∗",   /^(?:1*(01*01*)*)$/, w => w.split("0").length % 2 === 1],
  ["no 11",       "(0∪10)∗(ε∪1)",  /^(?:(0|10)*(|1))$/, w => !w.includes("11")],
  ["no 11 (AI)",  "(0∪10)∗",       /^(?:(0|10)*)$/,     w => !w.includes("11")],
  ["len % 3 = 0", "((0∪1)(0∪1)(0∪1))∗", /^(?:([01][01][01])*)$/, w => w.length % 3 === 0],
];
const all = [""];                       // every binary string up to length 12, shortlex
for (let k = 1; k <= 12; k++)
  for (let i = 0; i < 2 ** k; i++) all.push(i.toString(2).padStart(k, "0"));
let x = 2026;                           // fixed-seed generator: same strings every run
const rnd = () => (x = (x * 48271) % 2147483647);
const randoms = [];
for (let i = 0; i < 3000; i++) {
  let w = "", len = 13 + rnd() % 28;
  while (w.length < len) w += rnd() % 2;
  randoms.push(w);
}
for (const [name, formal, re, pred] of cases) {
  const bad = all.concat(randoms).filter(w => re.test(w) !== pred(w));
  const first = bad.length ? JSON.stringify(bad[0]) + (pred(bad[0]) ? " wrongly rejected" : " wrongly accepted") : "none";
  console.log(name.padEnd(12), formal.padEnd(20), "mismatches:", bad.length, " first:", first);
}
console.log("strings tested per case:", all.length + randoms.length);

আসল আউটপুট (ব্রাউজারের JavaScript):

even 0s      1∗(01∗01∗)∗          mismatches: 0  first: none
no 11        (0∪10)∗(ε∪1)         mismatches: 0  first: none
no 11 (AI)   (0∪10)∗              mismatches: 390  first: "1" wrongly rejected
len % 3 = 0  ((0∪1)(0∪1)(0∪1))∗   mismatches: 0  first: none
strings tested per case: 11191

তিনটি নকশা ১১,১৯১টি string-এর একটিতেও ভুল করেনি। তৃতীয় সারির (0 ∪ 10)∗ দেখতে প্রায় ঠিক, কিন্তু ৩৯০টি string ভুলভাবে বাতিল করেছে, আর shortlex ক্রমে প্রথমটি “1”: এক-চিহ্নের string, যাতে পরপর দুটি 1 নেই, অথচ regex-এর প্রতিটি অশূন্য সদস্য 0 দিয়ে শেষ হয়। যে string-গুলো 1 দিয়ে শেষ, সেগুলোই বাদ পড়েছে; (ε ∪ 1) অংশটি ঠিক এই ফাঁক বন্ধ করে। লক্ষ করুন, সংজ্ঞার দিকটি (pred) সরল Python-ধাঁচের শর্ত, regex নয়; দুটি স্বাধীন বর্ণনা মেলানোই এই পরীক্ষার শক্তি। দুটি সতর্কতা: প্রথমত, ^(?:…)$ ছাড়া test string-এর যেকোনো অংশে মিল খোঁজে, তখন গণিতের অর্থ হারায় (অংশ ৭)। দ্বিতীয়ত, এটি প্রমাণ নয়: সব দৈর্ঘ্যে মিলবে কি না, তা প্রমাণ বা পর্ব ২০-এর equivalence algorithm বলবে।

৬ · Regex-এর বীজগণিত — অভেদ, প্রমাণ আর ভুল অভেদ

দুটি regex R আর S equivalent, লেখা হয় R ≡ S, যদি L(R) = L(S). যেমন (a ∪ b)∗ ≡ (b ∪ a)∗, যদিও লেখা দুটি আলাদা। “অভেদ” মানে এমন একটি সমীকরণ, যা R, S, T-এর যেকোনো মানে সত্য। Regex-এর language-গুলো আসলে language-ই, তাই পর্ব ০৩-এর language-অভেদগুলো (∅L = ∅, {ε}L = L, (L∗)∗ = L∗ …) সরাসরি regex-অভেদ হয়ে যায়। এখানে মূল তালিকা, আর দুটির পূর্ণ প্রমাণ।

অভেদসত্য?কারণ বা পাল্টা-উদাহরণ (R = a, S = b)
R ∪ ∅ ≡ R,  R∅ ≡ ∅R ≡ ∅সবসময়∅ হলো union-এর “শূন্য” আর concatenation-এর “শোষক”
Rε ≡ εR ≡ Rসবসময়ε হলো concatenation-এর “এক”
R ∪ R ≡ R,  R ∪ S ≡ S ∪ Rসবসময়সেটের union-এর ধর্ম
R(S ∪ T) ≡ RS ∪ RT,  (S ∪ T)R ≡ SR ∪ TRসবসময়বণ্টন, দুই দিকেই
∅∗ ≡ ε,  ε∗ ≡ εসবসময়শুধু শূন্যটি টুকরোর জোড়া টেকে
(R∗)∗ ≡ R∗,  R∗R∗ ≡ R∗সবসময়উপপাদ্য ৬.১
ε ∪ RR∗ ≡ R∗,  (ε ∪ R)∗ ≡ R∗সবসময়শূন্যবার, অথবা অন্তত একবার
R(SR)∗ ≡ (RS)∗Rসবসময়“সরানোর নিয়ম”, অনুশীলন ২
(R ∪ S)∗ ≡ (R∗S∗)∗সবসময়উপপাদ্য ৬.২
(RS)∗ ≡ R∗S∗নাa শুধু ডানে; abab শুধু বাঁয়ে
(R ∪ S)∗ ≡ R∗ ∪ S∗নাab শুধু বাঁয়ে
R∗S∗ ≡ S∗R∗,  RS ≡ SRনাab শুধু বাঁয়ে; concatenation commutative নয়
উপপাদ্য ৬.১

প্রতিটি regex R-এর জন্য (R∗)∗ ≡ R∗.

প্রমাণ (A = L(R) লিখুন; দেখাতে হবে (A∗)∗ = A∗, দুই দিকের ⊆ দিয়ে):

  1. ⊇: যেকোনো language X-এর জন্য X ⊆ X∗ (একটি টুকরো নিলেই)। X = A∗ বসালে A∗ ⊆ (A∗)∗. — star-এর সংজ্ঞা, X1 = X
  2. ⊆: w ∈ (A∗)∗ নিন। তাহলে কোনো k ≥ 0-এর জন্য w = u1u2⋯uk, প্রতিটি ui ∈ A∗. — বাইরের star-এর সংজ্ঞা
  3. প্রতিটি ui নিজেও A-এর কয়েকটি string-এর জোড়া: ui = vi1⋯vimi, প্রতিটি v ∈ A. — ভেতরের star-এর সংজ্ঞা
  4. তাই w = v11⋯v1m1⋯vk1⋯vkmk, অর্থাৎ A-এর সসীম সংখ্যক string পরপর জোড়া, তাই w ∈ A∗. — concatenation associative, বন্ধনী সরানো যায়
  5. দুই দিকের ⊆ মিলে (A∗)∗ = A∗. ∎
উপপাদ্য ৬.২

প্রতিটি regex R আর S-এর জন্য (R ∪ S)∗ ≡ (R∗S∗)∗.

প্রমাণ (A = L(R), B = L(S)):

  1. ⊆: w ∈ (A ∪ B)∗ হলে w = w1⋯wk, প্রতিটি wi ∈ A ∪ B. — star-এর সংজ্ঞা
  2. wi ∈ A হলে wi = wi·ε, যেখানে wi ∈ A ⊆ A∗ আর ε ∈ B∗; wi ∈ B হলে wi = ε·wi. দুই ক্ষেত্রেই wi ∈ A∗B∗. — ε সব star-এ আছে
  3. তাই w হলো A∗B∗-এর k-টি string-এর জোড়া, w ∈ (A∗B∗)∗. — star-এর সংজ্ঞা
  4. ⊇: A ⊆ A ∪ B, তাই A∗ ⊆ (A ∪ B)∗; একইভাবে B∗ ⊆ (A ∪ B)∗. — star monotone: X ⊆ Y হলে X∗ ⊆ Y∗
  5. ফলে A∗B∗ ⊆ (A ∪ B)∗(A ∪ B)∗ = (A ∪ B)∗. — concatenation monotone, আর উপপাদ্য ৬.১-এর পাশের অভেদ X∗X∗ = X∗
  6. আবার star নিয়ে: (A∗B∗)∗ ⊆ ((A ∪ B)∗)∗ = (A ∪ B)∗. ∎ — star monotone, তারপর উপপাদ্য ৬.১

এবার উল্টো কাজ: একটি “অভেদ” মিথ্যা, তা দেখানো। এর জন্য প্রমাণ লাগে না, একটি counterexample যথেষ্ট: R আর S-এর একটি নির্দিষ্ট মান আর একটি string, যা এক দিকে আছে, অন্য দিকে নেই। সবচেয়ে সহজ খোঁজ: R = a, S = b বসিয়ে দুই দিকের ছোট string-গুলো তালিকা করা। নিচের stepper একটি সত্য আর একটি মিথ্যা দাবি এভাবে পরীক্ষা করে।

1দাবি ক: (a ∪ b)∗ ≡ (a∗b∗)∗2দৈর্ঘ্য 0 আর 13দৈর্ঘ্য 24সব দৈর্ঘ্যে কেন?5দাবি খ: (a ∪ b)∗ ≡ a∗ ∪ b∗6শিক্ষা
দুই দিকের string
বাঁ দিক
ডান দিক
ফল
  1. দাবি ক। R = a, S = b বসিয়ে উপপাদ্য ৬.২-এর একটি রূপ: (a ∪ b)∗ ≡ (a∗b∗)∗. দুই দিকের string দৈর্ঘ্য ধরে তালিকা করা হবে।
  2. দৈর্ঘ্য 0 আর 1. দুই দিকেই ε আছে, কারণ star শূন্যবারও চলে। a = a·ε আর b = ε·b দুটিই a∗b∗-এর সদস্য, তাই ডান দিকেও আছে। মোট ৩টি করে।
  3. দৈর্ঘ্য 2. aa, ab, bb একটি a∗b∗ ব্লকেই হয়। ba একটি ব্লকে হয় না (a∗b∗-এ সব a আগে), কিন্তু দুটি ব্লকে হয়: প্রথম ব্লক “b”, দ্বিতীয় “a” নিলে। ৪টি করে।
  4. সব দৈর্ঘ্যে। যেকোনো string-এর প্রতিটি চিহ্নকে আলাদা ব্লক ধরলেই ডান দিকে পড়ে। গোনা শুধু ছোট দৈর্ঘ্য দেখায়; সব দৈর্ঘ্যের নিশ্চয়তা দেয় উপপাদ্য ৬.২-এর প্রমাণ।
  5. দাবি খ। a∗ ∪ b∗-এ শুধু “সব a” বা “সব b” string. দৈর্ঘ্য 2-এ ডানে শুধু aa আর bb; বাঁয়ে ab আর ba-ও আছে। ab একটি witness: দাবিটি মিথ্যা।
  6. শিক্ষা। মিথ্যা অভেদ খণ্ডনে একটি নির্দিষ্ট R, S আর একটি string যথেষ্ট। সত্য অভেদে যত দৈর্ঘ্যই মেলানো হোক, প্রমাণ লাগে, কারণ language অসীম।

নিচের ব্লক অংশ ৩-এর evaluator ব্যবহার করে (আগে সেটি চালানো না থাকলে নিজেই আগে চালায়)। check দুই দিকের দৈর্ঘ্য ≤ 8 অংশ মেলায় আর অমিল থাকলে shortlex ক্রমে সবচেয়ে ছোট witness দেখায়। against একটি regex-কে সরল Python সংজ্ঞার সঙ্গে দৈর্ঘ্য ≤ 10-এর সব binary string-এ মেলায়। শেষ সারিটি একটি চমক: “01 আর 10 substring হিসেবে সমান সংখ্যক বার আছে”, শুনতে গোনার কাজ, অথচ regular.

from itertools import product

def check(R, S, n=8):         # compare L(R) and L(S) on every string up to length n
    A, B = set(L(R, n)), set(L(S, n))
    d = sorted(A ^ B, key=lambda w: (len(w), w))
    if not d: return f"same up to length {n} ({len(A)} strings)"
    w = d[0]
    return f"DIFFER: shortest witness {w or 'ε'} (only in {'left' if w in A else 'right'})"

for R, S in [("(a∗)∗", "a∗"), ("a∅", "∅"), ("aε", "a"), ("∅∗", "ε"),
             ("(a∪b)∗", "(a∗b∗)∗"), ("a(ba)∗", "(ab)∗a"), ("(a∗b)∗a∗", "(a∪b)∗"),
             ("(ab)∗", "a∗b∗"), ("(a∪b)∗", "a∗∪b∗"), ("a∗b∗", "b∗a∗")]:
    print(f"{R:>9} vs {S:<9} {check(R, S)}")

def against(R, pred, n=10):   # regex vs a plain-Python definition
    words = {"".join(t) for k in range(n + 1) for t in product("01", repeat=k)}
    bad = sorted(set(L(R, n)) ^ {w for w in words if pred(w)}, key=lambda w: (len(w), w))
    return "agree on all %d strings" % len(words) if not bad else "first mismatch: " + (bad[0] or "ε")

print("even 0s :", against("1∗(01∗01∗)∗", lambda w: w.count("0") % 2 == 0))
print("even 0s':", against("(1∪01∗0)∗", lambda w: w.count("0") % 2 == 0))
print("01 = 10 :", against("ε∪0∪1∪0(0∪1)∗0∪1(0∪1)∗1",
                           lambda w: w.count("01") == w.count("10")))

আসল আউটপুট (ব্রাউজারের Python):

    (a∗)∗ vs a∗        same up to length 8 (9 strings)
       a∅ vs ∅         same up to length 8 (0 strings)
       aε vs a         same up to length 8 (1 strings)
       ∅∗ vs ε         same up to length 8 (1 strings)
   (a∪b)∗ vs (a∗b∗)∗   same up to length 8 (511 strings)
   a(ba)∗ vs (ab)∗a    same up to length 8 (4 strings)
 (a∗b)∗a∗ vs (a∪b)∗    same up to length 8 (511 strings)
    (ab)∗ vs a∗b∗      DIFFER: shortest witness a (only in right)
   (a∪b)∗ vs a∗∪b∗     DIFFER: shortest witness ab (only in left)
     a∗b∗ vs b∗a∗      DIFFER: shortest witness ab (only in left)
even 0s : agree on all 2047 strings
even 0s': agree on all 2047 strings
01 = 10 : agree on all 2047 strings

প্রথম সাতটি অভেদ দৈর্ঘ্য ≤ 8-এ টিকেছে; 511 = 29 − 1, অর্থাৎ দৈর্ঘ্য 0 থেকে 8-এর সব string. শেষ তিনটি ভেঙেছে, টেবিলের পাল্টা-উদাহরণগুলোই: (ab)∗ বনাম a∗b∗-এ সবচেয়ে ছোট witness “a”, যা শুধু ডান দিকে (অন্য witness abab শুধু বাঁ দিকে, তাই কোনো দিকেই ⊆ নেই)। অংশ ৪-এর দুটি নকশা ২০৪৭টি string-এ সংজ্ঞার সঙ্গে মিলেছে। শেষ লাইনের ব্যাখ্যা সুন্দর: একটি binary string-এ “01” আর “10” পালা করে আসে (0-এর ব্লক থেকে 1-এর ব্লকে যাওয়া, আবার ফেরা), তাই দুটির সংখ্যা সমান ঠিক তখনই, যখন প্রথম আর শেষ চিহ্ন একই, বা string-টি ফাঁকা। গোনার মতো শোনালেও এখানে আসলে কিছু গুনতে হয় না।

অভেদ দিয়ে regex সরল করাও যায়। উদাহরণ: (a ∪ b)∗a(a ∪ b)∗ ∪ b∗. প্রথম অংশ “অন্তত একটি a আছে” এমন সব string, দ্বিতীয় অংশ “কোনো a নেই” এমন সব string. দুটি মিলে প্রতিটি string, তাই পুরোটি ≡ (a ∪ b)∗. এই যুক্তি অভেদ-টেবিলের সারি ব্যবহার করে না, সরাসরি language নিয়ে ভাবে; অনেক সময় এটিই দ্রুততম পথ। আর মনে রাখবেন, যেকোনো দুটি regex-এর equivalence যান্ত্রিকভাবে নির্ণয় করা যায় (দুটিকে DFA বানিয়ে তুলনা, পর্ব ২০), যদিও সবচেয়ে খারাপ ক্ষেত্রে তা ব্যয়বহুল।

৭ · গণিতের regex বনাম বাস্তবের regex

Python, JavaScript বা grep-এর regex গণিতের regex থেকে এসেছে, কিন্তু এক নয়। প্রথম পার্থক্য প্রশ্নে: গণিতে প্রশ্ন “w ∈ L(R)?”, অর্থাৎ পুরো string মেলে কি না; বাস্তবের টুলে প্রায়ই প্রশ্ন “w-এর কোনো অংশে মিল আছে কি না, আর থাকলে কোথায়”। দ্বিতীয় পার্থক্য শক্তিতে: অনেক বাস্তব সুবিধা শুধু সংক্ষেপ, কিন্তু কয়েকটি গণিতের regular language-এর সীমা ছাড়িয়ে যায়। Python-এর re হাতে-কলমে শিখতে Python কোর্সের পর্ব ৩০, আর JavaScript-এরটি JavaScript কোর্সের পর্ব ৩০ দেখুন। engine কীভাবে মেলায়, backtracking বনাম automaton, আর ReDoS নামের নিরাপত্তা সমস্যা, এসবের বিস্তারিত পর্ব ২১-এ।

বাস্তবের সুবিধাউদাহরণগণিতের দৃষ্টিতে
Character class[0-9], \d, .লম্বা union-এর সংক্ষেপ; regular
Quantifier+, ?, {4}, {2,5}RR∗, (ε ∪ R), পুনরাবৃত্তি; regular
Anchor^, $, \bকোনো চিহ্ন মেলায় না, অবস্থান যাচাই করে; পুরো-string অর্থ পেতে দরকার
Lazy quantifier*?কোন অংশ মিলবে তা বদলায়, “মিলবে কি না” নয়
Lookahead(?=…)backreference ছাড়া থাকলে language regular থাকে বলে জানা আছে
Backreference(a*)b\1anban-এর মতো non-regular language; পর্ব ১৭-এর pumping lemma প্রমাণ করবে

বাজারঘরের অর্ডার কোডের validator দিয়ে প্রথম পার্থক্যটি হাতে দেখা যাক। গণিতের regex BG-DDDD সরল, কিন্তু Python-এ লিখতে গেলে তিনটি ফাঁদ আছে: re.search string-এর যেকোনো অংশে খোঁজে, $ শেষের একটি newline-এর আগেও মেলে, আর Python 3-এর str pattern-এ \d শুধু 0–9 নয়, Unicode-এর যেকোনো দশমিক অঙ্ক মেলায়, বাংলা অঙ্কও।

import re, itertools
# bazarghar order code: formal regex  BG-DDDD,  D = (0 ∪ 1 ∪ ⋯ ∪ 9)
loose  = r"BG-\d{4}"                 # what people often write first
strict = r"BG-[0-9]{4}"
tests = ["BG-0042", "BG-00421", "xBG-0042", "BG-০০৪২", "BG-0042\n"]
print("input        search  fullmatch  fullmatch-strict")
for s in tests:
    print(f"{s!r:<12} {bool(re.search(loose, s))!s:<7} "
          f"{bool(re.fullmatch(loose, s))!s:<10} {bool(re.fullmatch(strict, s))}")
print("^…$ with match on 'BG-0042\\n':", bool(re.match(r"^BG-[0-9]{4}$", "BG-0042\n")))

# the formal language L(BG-DDDD) is finite: list it and count
codes = {f"BG-{i:04d}" for i in range(10000)}
print("codes:", len(codes), " all strict:", all(re.fullmatch(strict, c) for c in codes))

# coupon: 6 symbols from A-Z 0-9 containing SALE  =  ΓΓSALE ∪ ΓSALEΓ ∪ SALEΓΓ
G = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
part = lambda k: map("".join, itertools.product(G, repeat=k))
coupons = {p + "SALE" + q for k in range(3) for p in part(k) for q in part(2 - k)}
print("coupons:", len(coupons), " = 3 x 36^2:", len(coupons) == 3 * 36 ** 2)

আসল আউটপুট (ব্রাউজারের Python):

input        search  fullmatch  fullmatch-strict
'BG-0042'    True    True       True
'BG-00421'   True    False      False
'xBG-0042'   True    False      False
'BG-০০৪২'    True    True       False
'BG-0042\n'  True    False      False
^…$ with match on 'BG-0042\n': True
codes: 10000  all strict: True
coupons: 3888  = 3 x 36^2: True

search কলামে সব True: পাঁচ অঙ্কের কোড, সামনে বাড়তি অক্ষর, এমনকি শেষে newline, সবকিছুর ভেতরে কোথাও “BG-” আর চারটি অঙ্ক পাওয়া গেছে। তাই validator-এ search ব্যবহার করা ভুল। fullmatch পুরো string চায়, ঠিক গণিতের L(R)-এর মতো। কিন্তু চতুর্থ সারিতে \d বাংলা অঙ্ক ০০৪২-কেও মেনে নিয়েছে; গণিতের D-তে শুধু 0–9, তাই সঠিক অনুবাদ [0-9] (অথবা re.ASCII flag দেওয়া)। আর ^…$ দিয়ে match করলে শেষের newline পেরিয়ে যায়; fullmatch বা \Z নিরাপদ। শেষ দুই লাইন অংশ ৫-এর গোনা মেলায়: ১০,০০০টি অর্ডার কোড, আর তিন অংশের union-এ ঠিক ৩,৮৮৮টি আলাদা কুপন, কোনো string দুবার আসেনি।

আরও গভীরে: একটি regex-এ star কত গভীরে নেস্ট করা, তাকে বলে star height; যেমন (a∗b)∗-এর star height 2, যদিও সমতুল্য (a ∪ b)∗-এ 1. Eggan ১৯৬৩ সালে দেখান যে প্রতিটি n-এর জন্য এমন regular language আছে যার যেকোনো regex-এ star height অন্তত n লাগে, আর একটি language-এর ন্যূনতম star height বের করা যায় কি না, সেই প্রশ্ন Hashiguchi ১৯৮৮ সালে “হ্যাঁ” বলে সমাধান করেন বলে উল্লেখ করা হয়। কিন্তু regex-এ complement-ও দিলে যে “generalized star height” পাওয়া যায়, সেখানে কোনো language-এর জন্য 1-এর বেশি লাগে কি না, তা এখনো অজানা, automata তত্ত্বের পরিচিত খোলা প্রশ্নগুলোর একটি।

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:

  • Σ = {0, 1}-এ “পরপর দুটি 1 নেই”-এর regex লিখুন। (0 ∪ 10)∗(ε ∪ 1); শেষের (ε ∪ 1) ভুলে গেলে “1” বাদ পড়ে।
  • L(∅∗) কী? {ε}, ∅ নয়: শূন্যটি টুকরোর জোড়া সবসময় চলে।
  • (RS)∗ ≡ R∗S∗ কি সত্য? না; R = a, S = b নিলে “a” শুধু ডান দিকে, “abab” শুধু বাঁ দিকে।
  • ab∗ ∪ c-তে বন্ধনী বসান। (a(b∗)) ∪ c, কারণ star > concatenation > union.
  • Python-এর regex কি সবসময় regular language বোঝায়? না; backreference থাকলে anban-এর মতো non-regular language-ও চেনা যায়।

৮ · AI-এর যুগে regular expression

Regex লিখতে AI assistant খুব জনপ্রিয়, কারণ ছোট pattern তারা দ্রুত দেয়। কিন্তু অংশ ৫-এর (0 ∪ 10)∗-এর মতো “প্রায় ঠিক” উত্তর এখানে খুব সাধারণ, আর regex দেখে ভুল ধরা কঠিন। এই বিষয়ে যে ভুলগুলো বারবার দেখা যায়:

AI-এর ভুলকীভাবে ধরবেন
ε বা প্রান্তের ক্ষেত্র বাদ: “1” বা ফাঁকা string ভুলে যাওয়াদৈর্ঘ্য 0, 1, 2-এর সব string নিজে পরীক্ষা করা
গোনায় এক-কম বা এক-বেশি (“অন্তত দুটি” বনাম “ঠিক দুটি”)সংজ্ঞাটি Python শর্তে লিখে সব ছোট string-এ মেলানো
অগ্রাধিকার ভুল পড়া: a ∪ bc-কে (a ∪ b)c ধরাsyntax tree এঁকে বা evaluator-এ দুটি রূপের language তুলনা
(RS)∗ ≡ R∗S∗-এর মতো মিথ্যা “সরলীকরণ”R = a, S = b বসিয়ে সবচেয়ে ছোট witness খোঁজা
validator-এ anchor ছাড়া search, বা \d-কে 0–9 ধরাfullmatch দিয়ে, আর বাড়তি অক্ষর ও বাংলা অঙ্কসহ ইনপুটে পরীক্ষা
“এই regex সুষম বন্ধনী চেনে” ধরনের অসম্ভব দাবিমনে রাখা: সুষম বন্ধনী regular নয় (পর্ব ১৭); backreference দিয়েও সাধারণ সমাধান হয় না
বানানো ইতিহাস বা রেফারেন্সSipser বা Hopcroft–Motwani–Ullman-এ নিজে খুঁজে দেখা

AI-কে ভালোভাবে কাজে লাগানোর উপায়: regex-এর সঙ্গে একটি স্বাধীন সংজ্ঞাও চাওয়া, আর দুটিকে সব ছোট string-এ মেলানোর কোড নিজে চালানো।

আমি গণিতের অর্থে regular expression শিখছি (union ∪, concatenation, Kleene star; পুরো string মেলাতে হবে)। Σ = {a, b}-এর ওপর এই language-এর regex দাও: “প্রতিটি a-এর ঠিক পরেই একটি b আছে”। ১. regex-টি দাও, আর প্রতিটি অংশ কেন আছে তা ব্যাখ্যা করো। ২. দৈর্ঘ্য ≤ 3-এর যে string-গুলো language-এ আছে আর নেই, দুটি তালিকা দাও; ε আছে কি না আলাদা করে বলো। ৩. একটি ছোট Python কোড দাও (শুধু standard library), যা দৈর্ঘ্য ≤ 10-এর সব string-এ তোমার regex (re.fullmatch দিয়ে) আর একটি সরল শর্ত-ভিত্তিক সংজ্ঞা মিলিয়ে অমিল থাকলে প্রথমটি ছাপে। ৪. তোমার regex যে language-এর প্রতিটি string মেলায় আর বাইরের কিছু মেলায় না, তার দুই দিকের যুক্তি লেখো।

(নিজে যাচাই করুন: একটি সঠিক উত্তর (b ∪ ab)∗, বাস্তব syntax-এ (b|ab)*. ε আছে, কারণ ফাঁকা string-এ কোনো a নেই যার পরে b লাগবে। দৈর্ঘ্য ≤ 3-এ সদস্য ε, b, ab, bb, abb, bab, bbb. অনুশীলন ১-এ পূর্ণ যুক্তি আছে।)

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১স্নায়ুকোষের একটি গাণিতিক মডেল থেকে কীভাবে আজকের প্রতিটি text editor-এর “খুঁজুন” বোতাম এল?

১৯৪৩ সালে Warren McCulloch আর Walter Pitts স্নায়ুকোষকে একটি সরল যৌক্তিক একক হিসেবে মডেল করেন: কয়েকটি ইনপুট, একটি সীমা, আর “জ্বলে” বা “নেভে” আউটপুট। এমন এককের জাল কী কী “ঘটনা” চিনতে পারে, সেই প্রশ্নটি গণিতবিদ Stephen Kleene হাতে নেন। ১৯৫১ সালে RAND Corporation-এর একটি গবেষণা-প্রতিবেদনে, আর পরে ১৯৫৬ সালে Claude Shannon ও John McCarthy-র সম্পাদিত “Automata Studies” সংকলনে প্রকাশিত প্রবন্ধে তিনি দেখান: এই জালগুলো ঠিক সেই ঘটনা-সেট চেনে, যেগুলো তিনটি operation দিয়ে গড়া যায়। তিনি এদের বলেন “regular events”, আর ফলটি আজ Kleene-এর theorem নামে পরিচিত (পর্ব ১৪–১৫-এ প্রমাণ)।

এরপর প্রায় এক যুগ ধারণাটি মূলত তত্ত্বের জগতে ছিল। বড় পরিবর্তন আসে ১৯৬৮ সালে, যখন Ken Thompson Communications of the ACM-এ “Regular Expression Search Algorithm” প্রবন্ধে regex থেকে যন্ত্র বানিয়ে লেখার ভেতরে খোঁজার পদ্ধতি দেন। তিনি এটি QED নামের একটি text editor-এ ব্যবহার করেছিলেন বলে জানা যায়, পরে Unix-এর ed editor-এ। ed-এর একটি কমান্ড ছিল “g/re/p” (globally, regular expression, print), আর সেখান থেকে ১৯৭০-এর দশকের শুরুতে grep নামের আলাদা টুল আসে বলে প্রচলিত বিবরণে বলা হয়।

এই ইতিহাস থেকে একটি শিক্ষা আছে। Kleene কোনো সফটওয়্যার বানাতে চাননি; তিনি একটি গাণিতিক প্রশ্নের নিখুঁত উত্তর খুঁজছিলেন। কিন্তু উত্তরটি এত পরিষ্কার ছিল, তিনটি operation আর একটি সরল recursive সংজ্ঞা, যে প্রকৌশলীরা সেটিকে প্রায় সরাসরি একটি ব্যবহারের ভাষা বানাতে পেরেছিলেন। পরে Perl-এর মতো ভাষা অনেক বাড়তি সুবিধা যোগ করে, যার কিছু গণিতের সীমা ছাড়িয়ে যায় (অংশ ৭)। আজকের “regex” শব্দটি তাই দুটি জিনিস বোঝায়: Kleene-এর নিখুঁত গাণিতিক বস্তু, আর তার বহু-বর্ধিত প্রকৌশলী বংশধর।

মূল উপলব্ধি: Regular expression একটি বিশুদ্ধ গাণিতিক প্রশ্নের উত্তর হিসেবে জন্মেছিল, আর তার সরল, recursive গঠনই তাকে প্রকৌশলে এত সফল করেছে। গণিতের সংজ্ঞা আর টুলের সুবিধা আলাদা রাখতে শেখাই এই কোর্সের প্রথম শৃঙ্খলা।

প্র ০২সংখ্যার বীজগণিতে কয়েকটি সূত্র থেকেই বাকি সব অভেদ পাওয়া যায়। Regex-এর বীজগণিতে কি তেমন একটি সসীম সূত্র-তালিকা আছে?

অংশ ৬-এর টেবিলে যে অভেদগুলো দেখেছেন, সেগুলো দেখে মনে হতে পারে, কয়েকটি মৌলিক সূত্র বেছে নিলে বাকি সব অভেদ শুধু বসানো আর সরলীকরণে পাওয়া যাবে, যেমন commutative ring-এর কয়েকটি নিয়ম থেকে স্কুলের সব বীজগণিত। প্রশ্নটি ১৯৬০-এর দশকে গুরুত্ব দিয়ে তোলা হয়, আর উত্তরটি অবাক করার মতো: শুধু সমীকরণ দিয়ে তা সম্ভব নয়। V. N. Redko ১৯৬৪ সালে দেখান যে regex-এর সব সত্য অভেদকে কোনো সসীম সমীকরণ-তালিকা থেকে বের করা যায় না।

তাহলে উপায় কী? Arto Salomaa ১৯৬৬ সালে একটি সসীম তালিকা দেন, তবে সঙ্গে একটি বিশেষ অনুমান-নিয়ম, যা মোটামুটি বলে: X = AX ∪ B আর ε ∉ L(A) হলে X = A∗B. এটি পর্ব ১৫-এর Arden-এর সূত্রের কাছের রূপ। লক্ষ করুন, এখানে শর্ত “ε ∉ L(A)” পরীক্ষা করতে অংশ ২-এর ν function-টিই লাগে। পরে Dexter Kozen ১৯৯৪ সালে দেখান, Kleene algebra নামের একটি সরল অসমতা-ভিত্তিক axiom-তালিকা থেকে regex-এর প্রতিটি সত্য অভেদ প্রমাণ করা যায়; এটি এখন program verification-এর কিছু পদ্ধতির ভিত্তি।

অন্যদিকে, দুটি নির্দিষ্ট regex সমতুল্য কি না, তা algorithm দিয়ে সবসময় নির্ণয় করা যায়: দুটিকে automaton বানিয়ে তুলনা করলেই হয় (পর্ব ২০)। কিন্তু সময় লাগতে পারে প্রচুর। Larry Stockmeyer আর Albert Meyer ১৯৭০-এর দশকের শুরুতে দেখান যে regex-এর equivalence সমস্যা PSPACE-complete; অর্থাৎ এর জন্য দ্রুত (polynomial-time) algorithm থাকলে P = PSPACE হতো, যা বেশিরভাগ বিশেষজ্ঞ অসম্ভব মনে করেন, যদিও এটি প্রমাণিত নয়। তাই অংশ ৬-এর মতো brute-force witness খোঁজা বাস্তবে কাজের: ভুল অভেদ সাধারণত ছোট string-এই ধরা পড়ে।

মূল উপলব্ধি: Regex-এর অভেদ নির্ণয়যোগ্য, কিন্তু শুধু সমীকরণের সসীম তালিকা দিয়ে সব অভেদ পাওয়া যায় না; একটি বাড়তি নিয়ম বা অসমতা লাগে। “সত্য কি না জানা যায়” আর “সংক্ষিপ্ত নিয়মে প্রমাণ করা যায়” দুটি আলাদা প্রশ্ন।

প্র ০৩কেউ বাস্তবে ∅ লেখে না, আর ε তো ∅∗ দিয়েই পাওয়া যায়। তাহলে সংজ্ঞার ভিত্তিতে এই দুটি রাখা হলো কেন?

প্রথমে ε-এর কথা। অংশ ৬-এর টেবিলে দেখেছেন, L(∅∗) = {ε}. তাই ε সংজ্ঞা থেকে বাদ দিলেও কোনো language হারায় না: যেখানেই ε দরকার, ∅∗ লেখা যায়। ε রাখা হয় শুধু সুবিধার জন্য, ঠিক যেমন পাটিগণিতে 1 রাখা হয় যদিও সেটি 0-এর successor হিসেবে লেখা যেত। কিছু বই সত্যিই ছোট ভিত্তি নেয়; ফল একই।

∅-কে বাদ দেওয়া যায় না। দাবি: ∅ ব্যবহার না করা প্রতিটি regex-এর language অশূন্য। প্রমাণ structural induction-এ: ε আর a-এর language অশূন্য; দুটি অশূন্য language-এর union আর concatenation অশূন্য (প্রতিটি থেকে একটি string নিয়ে জোড়া যায়); আর যেকোনো language-এর star-এ ε আছে। তাই ∅ ছাড়া ফাঁকা language লেখার কোনো উপায়ই নেই। কিন্তু ফাঁকা language কি দরকার? হ্যাঁ, কারণ “regex-বর্ণনাযোগ্য language” শ্রেণিটি সব regular language হতে হলে ∅-কেও ধরতে হবে; যে DFA-র কোনো accepting state নেই, তার language ∅.

আরও একটি ব্যবহারিক কারণ আছে। পর্ব ১৫-এর state elimination-এ একটি automaton-এর দুই state-এর মাঝে তীর না থাকলে সেই “তীরের regex” হয় ∅. এতে প্রতিটি জোড়া state-এর জন্য একটি regex থাকে, আর সূত্র R1R2∗R3 ∪ R4 সব ক্ষেত্রে একইভাবে লেখা যায়; ∅-এর অভেদ (R∅ ≡ ∅, R ∪ ∅ ≡ R) নিজে থেকেই অনুপস্থিত পথগুলো মুছে দেয়। বীজগণিতে শূন্য সংখ্যাটির মতো, ∅ নিজে কোনো কাজ করে না, কিন্তু তাকে ছাড়া হিসাবের নিয়মগুলো ভাঙা ভাঙা হয়ে যায়।

শেষে একটি গোনার কথা। Regex সসীম চিহ্নের string, তাই সব regex-এর সেট countable; অথচ Σ∗-এর সব language-এর সেট uncountable (পর্ব ০২)। তাই বেশিরভাগ language-এর কোনো regex নেই। ভিত্তিতে কী রাখা হলো, তাতে এই চিত্র বদলায় না।

মূল উপলব্ধি: ε সুবিধার জন্য, ∅ প্রয়োজনের জন্য। একটি recursive সংজ্ঞার ভিত্তি বাছা হয় এমনভাবে, যাতে লক্ষ্যের পুরো শ্রেণি ধরা পড়ে আর নিয়মগুলো সবক্ষেত্রে একইভাবে খাটে।

প্র ০৪একই language-এর জন্য regex ছোট আর DFA বিশাল হতে পারে। উল্টোটিও কি ঘটে? বর্ণনার আকার নিয়ে তত্ত্ব কী বলে?

পর্ব ১০-এ দেখেছেন, “শেষ থেকে n-তম চিহ্ন 1” language-এর যেকোনো DFA-তে অন্তত 2nটি state লাগে। অথচ তার regex ছোট: (0 ∪ 1)∗1(0 ∪ 1)n−1, যার দৈর্ঘ্য n-এর অনুপাতে। তাই regex DFA-র চেয়ে ঘাতের হারে সংক্ষিপ্ত হতে পারে; এটি NFA-র সঙ্গে মিলে যায়, কারণ পর্ব ১৪-এ দেখবেন regex থেকে প্রায় সমান আকারের NFA বানানো যায়।

উল্টো দিকটিও সত্য, আর সেটি অনেকের কাছে অবাক করার মতো। এমন DFA-র পরিবার আছে, যাদের n-টি state, কিন্তু যেকোনো সমতুল্য regex-এর দৈর্ঘ্য n-এর ঘাতের হারে বাড়ে। এই ধরনের প্রথম ফল সাধারণত Ehrenfeucht আর Zeiger-এর ১৯৭০-এর দশকের কাজের সঙ্গে যুক্ত করা হয়, আর পরে Gruber ও Holzer-এর মতো গবেষকেরা সীমাগুলো আরও নিখুঁত করেন। স্বজ্ঞাটি হলো: DFA-তে state-গুলো ইচ্ছামতো জালের মতো জুড়ে থাকতে পারে, কিন্তু regex একটি গাছ, তাই একই ঘুর বারবার লিখতে হয়। পর্ব ১৫-এর state elimination-এ এই বিস্ফোরণ হাতে-কলমে দেখবেন, আর দেখবেন state সরানোর ক্রম বদলালে regex-এর আকার কতটা বদলায়।

আরেকটি জায়গায় আকার বিস্ফোরিত হয়: intersection আর complement. গণিতের regex-এ এই দুটি operation নেই, যদিও regular language এদের অধীনে বন্ধ (পর্ব ১৬)। দুটি regex-এর intersection-এর regex লিখতে গেলে সাধারণত automaton-এ গিয়ে product construction করে ফিরে আসতে হয়, আর ফলের regex মূলগুলোর চেয়ে অনেক বড় হতে পারে; Gelade আর Neven-এর ২০০৮ সালের কাজে এর ঘাতের হারের সীমা দেখানো হয়েছে বলে উল্লেখ আছে। এ কারণেই বাস্তবের কিছু টুল “এবং” বা “নয়” সরাসরি সমর্থন করে, আর কিছু করে না।

বাজারঘরের দলের জন্য শিক্ষাটি ব্যবহারিক। একটি format-এর জন্য কোন বর্ণনা রাখবেন, regex না DFA না কোড, তা নির্ভর করে কে পড়বে আর কী কাজে লাগবে। মানুষের পড়ার জন্য ছোট regex ভালো; দ্রুত যাচাইয়ের জন্য ছোট DFA; আর যেখানে কোনোটিই ছোট নয়, সেখানে সরল কোড আর পরীক্ষা।

মূল উপলব্ধি: Regex, NFA আর DFA একই শ্রেণির language বর্ণনা করে, কিন্তু আকারের দিক থেকে কোনোটিই সবসময় সেরা নয়। কোনো রূপান্তর ঘাতের হারে বড় ফল দিতে পারে, আর এই সীমাগুলোর অনেকগুলো প্রমাণিত।

প্র ০৫বাজারঘর সব ইনপুট যাচাই regex দিয়ে করতে চায়: অর্ডার কোড, কুপন, অর্ডার-কোয়েরির বন্ধনী। কোথায় regex ঠিক হাতিয়ার, আর কোথায় নয়?

অর্ডার কোড আর কুপনের format সসীম বা সরল কাঠামোর, তাই regex এখানে আদর্শ: ছোট, পড়া যায়, আর একটি DFA-তে রূপান্তর করলে ইনপুটের দৈর্ঘ্যের অনুপাতে সময়ে যাচাই হয়। কিন্তু অংশ ৭ দেখিয়েছে, “আদর্শ” মানে “অসাবধানে লেখা যায়” নয়: search বনাম fullmatch, Unicode অঙ্ক, আর শেষের newline, তিনটিই বাস্তবে ভুল validator-এর পরিচিত উৎস। গণিতের সংজ্ঞায় এই প্রশ্ন ওঠেই না, কারণ L(R) সবসময় পুরো string নিয়ে কথা বলে আর Σ নির্দিষ্ট। তাই নিয়ম হলো: আগে গণিতের regex-টি লিখুন, তারপর সেটিকে টুলের syntax-এ সাবধানে অনুবাদ করুন।

অর্ডার-কোয়েরির বন্ধনী আলাদা গল্প। “প্রতিটি খোলা বন্ধনীর একটি মিলানো বন্ধনী আছে” language-টি regular নয়; পর্ব ১৭-এ pumping lemma দিয়ে প্রমাণ হবে। কোনো গণিতের regex-ই এটি পারে না। বাস্তবের কিছু engine-এ recursion-এর মতো বিশেষ সুবিধা আছে, যা এটি পারে, কিন্তু তখন সেটি আর regular expression নয়, একটি ছোট grammar. সঠিক হাতিয়ার এখানে একটি parser (মডিউল ৫–৭)।

Backreference আরেকটি সতর্কতা। এটি দিয়ে “একই শব্দ পরপর দুবার” ধরনের non-regular শর্ত লেখা যায়, কিন্তু দাম আছে। গবেষণায় দেখানো হয়েছে যে backreference-সহ pattern-এর সঙ্গে একটি string মেলে কি না, সেই প্রশ্ন সাধারণভাবে NP-complete (এই ফলটি সাধারণত Alfred Aho-র ১৯৯০ সালের একটি অধ্যায়ের সঙ্গে যুক্ত করা হয়)। অর্থাৎ এর জন্য দ্রুত সাধারণ algorithm থাকলে P = NP হতো, যা এখনো খোলা প্রশ্ন এবং বেশিরভাগ বিশেষজ্ঞ অসম্ভব মনে করেন। বাস্তবের backtracking engine এই সুবিধা দেয়, কিন্তু বিনিময়ে কিছু ইনপুটে সময় ঘাতের হারে বাড়তে পারে, যা পর্ব ২১-এর ReDoS-এর মূল।

তাহলে একটি সহজ নির্দেশিকা দাঁড়ায়। Format সসীম বা “এটা, তারপর ওটা, যতবার খুশি” ধরনের হলে regex; গোনা বা মেলানো লাগলে (সমান সংখ্যক, সুষম বন্ধনী) parser বা সাধারণ কোড; আর যেকোনো validator-এর পাশে সব ছোট ইনপুটের একটি brute-force পরীক্ষা।

মূল উপলব্ধি: Regex-এর শক্তি ঠিক regular language-এর শক্তি: সসীম স্মৃতি। এর মধ্যে এটি অসাধারণ, এর বাইরে গেলে হয় ভুল, নয়তো ব্যয়বহুল বাড়তি সুবিধা।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। যেকোনো regex উপরের regex_semantics.py বা identities.py ব্লকে বসিয়ে যাচাই করতে পারেন।

  1. নকশা: Σ = {a, b} বা {0, 1}-এর ওপর regex লিখুন: (ক) প্রতিটি a-এর ঠিক পরেই একটি b আছে; (খ) a-এর সংখ্যা 3 দিয়ে বিভাজ্য; (গ) Σ = {0, 1}-এ ঠিক দুটি 1. প্রতিটির ক্ষেত্রে একটি ছোট সদস্য আর একটি অসদস্য দিন।

    (ক) (b ∪ ab)∗. যুক্তি: string-কে বাঁ থেকে টুকরো করুন; যেখানে b, সেখানে টুকরো “b”; যেখানে a, তার পরের চিহ্নটি অবশ্যই b, তাই সেখানে টুকরোটি “ab” হয়। উল্টো দিকে, b আর ab-এর যেকোনো জোড়ায় প্রতিটি a-এর পরে b থাকে। সদস্য: ε, bab; অসদস্য: a, aab, ba.

    (খ) b∗(ab∗ab∗ab∗)∗, অংশ ৪-এর “জোড়সংখ্যক 0”-এর মতো, শুধু ব্লকে তিনটি a. সদস্য: ε, babaa (তিনটি a); অসদস্য: aa.

    (গ) 0∗10∗10∗. সদস্য: 11, 0101; অসদস্য: 1, 111.

    তিনটিই scratch-এ দৈর্ঘ্য ≤ 10-এর সব string-এ সরল Python সংজ্ঞার সঙ্গে মেলানো হয়েছে, কোনো অমিল নেই।

  2. প্রমাণ ও ভুল ধরা: (ক) প্রমাণ করুন: প্রতিটি regex R, S-এর জন্য R(SR)∗ ≡ (RS)∗R. (খ) একজন লিখেছেন: “(RS)∗-এর যেকোনো string r1s1r2s2⋯rksk. সব r-কে সামনে আর সব s-কে পেছনে সাজালে r1⋯rks1⋯sk ∈ R∗S∗. উল্টোটিও একইভাবে। তাই (RS)∗ ≡ R∗S∗. ∎” ভুল কোথায়?

    (ক) A = L(R), B = L(S).

    1. w ∈ A(BA)∗ ⇔ কোনো k ≥ 0-এর জন্য w = r0(s1r1)(s2r2)⋯(skrk), প্রতিটি ri ∈ A, si ∈ B. — concatenation আর star-এর সংজ্ঞা
    2. বন্ধনী নতুন করে বসালে একই string = (r0s1)(r1s2)⋯(rk−1sk)rk. — string-এর concatenation associative; চিহ্নের ক্রম বদলায়নি
    3. এখানে প্রতিটি (ri−1si) ∈ AB, তাই w ∈ (AB)∗A; একই ধাপ উল্টো দিকে পড়লে বিপরীত দিকও। ∎ — star-এর সংজ্ঞা

    (খ) “সাজালে” ধাপটি ভুল: concatenation commutative নয়, টুকরো সরালে string-ই বদলে যায়। R = a, S = b নিলে abab ∈ (RS)∗, কিন্তু সাজানো string aabb আলাদা string; abab নিজে a∗b∗-এ নেই। “উল্টোটিও” দাবিও ভুল: a ∈ R∗S∗, কিন্তু (ab)∗-এ নেই। identities.py ব্লক ঠিক এই witness “a” দেখিয়েছে।

  3. আউটপুট অনুমান: regex_semantics.py-এর evaluator দিয়ে show(L("a∗b∪ba∗", 3)) চালালে কী ছাপবে? আর identities.py-এর check("(ab)∗", "a∗b∗") কী ফেরত দেয়, কেন?

    অগ্রাধিকারে R = (a∗b) ∪ (ba∗). প্রথম অংশ: b, ab, aab; দ্বিতীয়: b, ba, baa. b দুই অংশেই, কিন্তু সেটে একবার। shortlex ক্রমে: {b, ab, ba, aab, baa}, ৫টি string; scratch-এ একই ফল।

    check ফেরত দেয় DIFFER: shortest witness a (only in right). দুই দিকের symmetric difference shortlex ক্রমে সাজালে প্রথমটি “a”: দৈর্ঘ্য 1-এ a ∈ a∗b∗, কিন্তু (ab)∗-এর প্রতিটি string-এর দৈর্ঘ্য জোড়।

  4. সরলীকরণ: (ক) দেখান (a ∪ b)∗a(a ∪ b)∗ ∪ b∗ ≡ (a ∪ b)∗. (খ) (a∗b)∗a∗ ≡ (a ∪ b)∗ কি সত্য? প্রমাণ বা পাল্টা-উদাহরণ দিন।

    (ক) ⊆ স্পষ্ট, কারণ বাঁ দিকের প্রতিটি string a আর b দিয়েই গড়া। ⊇: যেকোনো w-এ হয় অন্তত একটি a আছে, তখন প্রথম a-এর আগে আর পরে যা আছে তা (a ∪ b)∗-এ, তাই w প্রথম অংশে; নয়তো কোনো a নেই, তখন w ∈ b∗. ∎

    (খ) সত্য। ⊆ স্পষ্ট। ⊇: w-এ m-টি b থাকলে প্রতিটি b-এর ঠিক পরে কাটুন: w = (ak1b)(ak2b)⋯(akmb)aj, যেখানে ki, j ≥ 0. প্রতিটি বন্ধনী a∗b-এ, শেষ অংশ a∗-এ, তাই w ∈ (a∗b)∗a∗. ∎ identities.py-ও দৈর্ঘ্য ≤ 8-এ দুই দিক সমান পেয়েছে, মোট ৫১১টি string-এ। লক্ষ করুন, বাঁ দিকের star height 2, ডানের 1: একই language, ভিন্ন জটিলতার লেখা।

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমএকটি বর্ণনা থেকে regex নকশা আর যাচাইয়ের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. ε-সহ কয়েকটি ছোট সদস্য আর অসদস্য লেখা
  2. string-কে স্থির, ঐচ্ছিক আর পুনরাবৃত্ত টুকরোয় ভাগ করা
  3. প্রতিটি টুকরোর regex লিখে অগ্রাধিকার মেনে জোড়া লাগানো
  4. তালিকার প্রতিটি উদাহরণ regex-এ মিলিয়ে দেখা
  5. সব ছোট string-এ একটি স্বাধীন সংজ্ঞার সঙ্গে brute-force তুলনা করা

গণিতের regular expression ∅∗-এর language কী?

  • ∅
  • {ε}
  • {∅}
  • Σ∗

প্রচলিত অগ্রাধিকার (star > concatenation > union) মানলে ab∗ ∪ c কোন বন্ধনীর সমান?

  • (a(b∗)) ∪ c
  • ((ab)∗) ∪ c
  • a(b∗ ∪ c)
  • (ab)∗c

R আর S যেকোনো regular expression. নিচের কোনটি সাধারণভাবে সত্য অভেদ নয়?

  • (R∗)∗ ≡ R∗
  • (R ∪ S)∗ ≡ (R∗S∗)∗
  • (RS)∗ ≡ R∗S∗
  • R∅ ≡ ∅

Σ = {0, 1}-এর ওপর “0-এর সংখ্যা জোড়” language-এর সঠিক regex কোনটি?

  • (00)∗
  • 0∗1∗0∗
  • (1∗01∗0)∗
  • 1∗(01∗01∗)∗

Σ = {0, 1}-এর ওপর “পরপর দুটি 1 নেই” language-এর সঠিক regex কোনটি?

  • (0 ∪ 10)∗
  • (0 ∪ 10)∗(ε ∪ 1)
  • (0 ∪ 1)∗0
  • (01)∗

বাস্তবের regex-এর কোন সুবিধা একটি pattern-কে গণিতের regular language-এর বাইরে নিয়ে যেতে পারে?

  • Character class, যেমন [0-9]
  • Quantifier, যেমন {4}
  • Backreference, যেমন \1
  • Anchor, যেমন ^

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. Regex-এর ভিত্তি ∅, ε আর একক চিহ্ন; নিয়ম ∪, concatenation আর ∗. L(R) একই গঠনে recursive, তাই প্রমাণ structural induction-এ।
  2. অগ্রাধিকার: star > concatenation > union. একটি বন্ধনী language বদলে দিতে পারে: (a ∪ b)a∗ আর a ∪ ba∗ আলাদা।
  3. নকশায় আগে ε-সহ উদাহরণ, তারপর টুকরো, তারপর জোড়া; সঠিকতার দুই দিক: যা মেলে তা language-এ, আর language-এর সবকিছু মেলে।
  4. সত্য অভেদের জন্য প্রমাণ, মিথ্যার জন্য একটি witness: (R ∪ S)∗ ≡ (R∗S∗)∗ সত্য, (RS)∗ ≡ R∗S∗ মিথ্যা।
  5. বাস্তবের regex-এ fullmatch, [0-9] আর শেষের newline-এর দিকে নজর রাখুন; backreference গণিতের regular-এর সীমা ছাড়ায়।

পরের পর্বে: প্রতিটি regex-কে একটি ε-NFA-তে রূপান্তরের যান্ত্রিক পদ্ধতি, Thompson construction. দেখবেন ∪, concatenation আর ∗-এর জন্য তিনটি ছোট “জোড়ার কৌশল”, আর structural induction-এ প্রমাণ যে ফলের NFA ঠিক L(R) চেনে।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান