এই পর্বে যা শিখবেন
- Alphabet, string, ε, দৈর্ঘ্য, prefix, suffix, substring-এর নিখুঁত সংজ্ঞা আর এই কোর্সের notation
- Σk, Σ∗, Σ+ গোনা, আর shortlex ক্রমে সব string সাজানো
- Language-এর ওপর union, concatenation, power, Kleene star, reversal আর homomorphism হাতে হিসাব করা
- কোন অভেদ সত্য, কোনটি ফাঁদ, আর Python-এ brute force দিয়ে পাল্টা-উদাহরণ খোঁজা
- দৈর্ঘ্যের ওপর induction দিয়ে string-এর ধর্ম প্রমাণ করা
১ · Alphabet আর string — চিহ্নের সসীম সারি
বাজারঘর নামের একটি কাল্পনিক অনলাইন দোকানের কথা ভাবুন। প্রতিটি অর্ডারের একটি কোড আছে, যেমন BG-0042. ক্রেতা ফোনে একটি কুপন কোড লেখেন, যেমন EID26X. গুদামের একটি সেন্সর লাইনে 0 আর 1-এর সারি পাঠায়। অর্ডার খোঁজার ছোট ভাষায় বন্ধনী থাকে, যেমন [[]][]. চারটি জিনিস দেখতে আলাদা, কিন্তু গঠন একই: কিছু নির্দিষ্ট চিহ্ন, পরপর সাজানো। গণনার তত্ত্ব ঠিক এই সাধারণ গঠন থেকে শুরু করে।
মালার কথা ভাবুন। দোকানে কয়েক রঙের পুঁতি আছে: এটি alphabet. সুতোয় পরপর গাঁথা পুঁতির একটি মালা হলো string. মালায় কোন পুঁতি কোথায়, সেই ক্রমটাই আসল; একই পুঁতি দুবার আসতে পারে। আর ফাঁকা সুতোও একটি মালা, শুধু তাতে কোনো পুঁতি নেই। সেটিই empty string.
একটি alphabet Σ (উচ্চারণ “সিগমা”) হলো চিহ্নের একটি সসীম, অশূন্য সেট। Σ-এর ওপর একটি string w হলো Σ-এর চিহ্নের একটি সসীম ক্রম w = w1w2⋯wn, যেখানে প্রতিটি wi ∈ Σ. সংখ্যা n হলো w-এর দৈর্ঘ্য, লেখা হয় |w| = n. দৈর্ঘ্য 0-এর একটিমাত্র string আছে: empty string, প্রতীক ε (গ্রিক “এপসাইলন”)।
কয়েকটি উদাহরণ। Σ = {0, 1} হলে 0110 একটি string, |0110| = 4. বাজারঘরের অর্ডার কোডের alphabet হতে পারে ΣORD = {B, G, -, 0, 1, …, 9}, মোট ১৩টি চিহ্ন; তখন |BG-0042| = 7. কুপনের alphabet ΣCPN = {A, …, Z, 0, …, 9}, মোট ৩৬টি চিহ্ন। আরও দুটি notation লাগবে। |w|a মানে w-এ চিহ্ন a কতবার আছে: |0110|1 = 2. আর wi মানে i-তম চিহ্ন, গণনা শুরু 1 থেকে। খেয়াল করুন, Python-এ w[0] প্রথম অক্ষর; গণিতে সেটি w1. এই এক ঘরের পার্থক্য থেকেই বহু off-by-one ভুল আসে।
সংজ্ঞার দুটি শব্দ গুরুত্বপূর্ণ। সসীম alphabet: একটি যন্ত্র এক ধাপে একটি চিহ্ন পড়ে আর সসীম টেবিল দেখে সিদ্ধান্ত নেয় (পর্ব ০৭-এর DFA). অসীম alphabet হলে সেই টেবিলই লেখা যেত না। সসীম string: প্রতিটি string-এর একটি শেষ আছে। অসীম সারি নিয়েও তত্ত্ব আছে (model checking-এ, পর্ব ৭৭), কিন্তু সেগুলো আলাদা বস্তু, string নয়।
String আর সেটের পার্থক্যটিও শুরুতেই পরিষ্কার থাকা দরকার। সেটে ক্রম আর পুনরাবৃত্তির কোনো মূল্য নেই: {a, b} = {b, a} = {a, a, b}. String-এ দুটিই আসল: ab ≠ ba, আর aab-এর দৈর্ঘ্য 3, 2 নয়। রেলের টিকিট কাউন্টারের লাইনের মতো: কে কে দাঁড়িয়েছেন, সেটি একটি সেট; কে কার পরে, সেটি একটি string. তাই “string” মানে কখনো “অক্ষরের সংগ্রহ” নয়, সবসময় “অক্ষরের সারি”।
ε নিয়ে একটি কথা: কিছু বই (যেমন Linz-এর বই) empty string-কে λ (ল্যামডা) লেখে। এই কোর্সে সবসময় ε. মনে রাখবেন, ε কোনো চিহ্ন নয়, ε ∉ Σ. এটি “কিছুই না লেখা”-র নাম। ফাঁকা SMS-এর মতো: বার্তা আছে, কিন্তু অক্ষর নেই।
২ · String-এর operation — জোড়া, উল্টানো, power আর অংশ
দুটি string u আর v-কে পরপর লিখলে পাওয়া যায় তাদের concatenation uv. u = BG-, v = 0042 হলে uv = BG-0042. সংজ্ঞা অনুযায়ী |uv| = |u| + |v|. তিনটি ধর্ম সবসময় খাটে: (uv)w = u(vw), অর্থাৎ বন্ধনী লাগে না (associative); εw = wε = w, অর্থাৎ ε হলো এই গুণের “১”; আর সাধারণভাবে uv ≠ vu, যেমন ab ≠ ba. শেষ ধর্মটিই string-কে সংখ্যার যোগ থেকে আলাদা করে। ট্রেনের বগির মতো: কোন বগি আগে, তাতে ট্রেন বদলে যায়।
Power: w0 = ε, আর wk+1 = wkw. যেমন (ab)3 = ababab, কিন্তু ab3 = abbb (power কেবল ঠিক আগের চিহ্নে বসে)।
Reversal: εR = ε, আর যেকোনো string x ও চিহ্ন σ-এর জন্য (xσ)R = σxR. যেমন (BG-0042)R = 2400-GB. যে string-এর wR = w, সেটি palindrome, যেমন 0110 আর abba.
Prefix, suffix, substring: w = xyz হলে x হলো w-এর prefix, z হলো suffix, আর y হলো substring. x, y, z-এর যেকোনোটি ε হতে পারে, তাই ε আর w নিজেও w-এর prefix, suffix আর substring. w ছাড়া অন্য prefix-কে বলে proper prefix.
নিচের ছবিতে বাজারঘরের অর্ডার কোডটি ভেঙে দেখানো হলো। উপরের ছোট সংখ্যাগুলো অবস্থান i, ঘরের ভেতরে wi.
একটি string-এর শরীর: w = BG-0042
নীল বন্ধনী একটি prefix, সবুজ একটি suffix, কমলা একটি substring. তিনটিই w-এর মাঝ থেকে টানা অংশ, শুধু অবস্থান আলাদা।
Substring গোনা একটু সূক্ষ্ম। শুরু i আর শেষ j বেছে নিলে (1 ≤ i ≤ j ≤ n) একটি অশূন্য substring পাওয়া যায়; এমন জোড়া n(n + 1)/2টি। ε যোগ করলে মোট সর্বোচ্চ n(n + 1)/2 + 1. “সর্বোচ্চ”, কারণ দুই জায়গার substring একই হতে পারে। abc-এর ৭টি substring সব আলাদা (3 · 4/2 + 1 = 7), কিন্তু aaa-র মাত্র ৪টি: ε, a, aa, aaa. BG-0042-এ সীমা 29, আসল সংখ্যা 28, কারণ “0” দুবার আছে। আরেকটি শব্দ গুলিয়ে ফেলবেন না: subsequence মানে কিছু চিহ্ন বাদ দিয়ে বাকিগুলো ক্রম ঠিক রেখে নেওয়া, যেমন B04 হলো BG-0042-এর subsequence, কিন্তু substring নয়।
৩ · সব string-এর সেট — গোনা আর shortlex ক্রমে সাজানো
Σk = দৈর্ঘ্য ঠিক k-এর সব string-এর সেট; Σ0 = {ε}. Σ∗ = Σ0 ∪ Σ1 ∪ Σ2 ∪ ⋯, অর্থাৎ Σ-এর ওপর সব সসীম string (ε-সহ)। আর Σ+ = Σ1 ∪ Σ2 ∪ ⋯ = Σ∗ ∖ {ε}. তারকা চিহ্নটির নাম Kleene star, Stephen Kleene-এর নামে।
গোনার মূল সূত্রটি গুণের নিয়ম থেকে আসে: প্রতিটি অবস্থানে |Σ|টি পছন্দ, k-টি অবস্থান, তাই
|Σk| = |Σ|k
বাজারঘরের কুপন দৈর্ঘ্য 6, alphabet-এ ৩৬টি চিহ্ন: মোট 366 = 2,176,782,336টি সম্ভাব্য কুপন, প্রায় ২১৭ কোটি। অর্ডার কোডের প্রথম তিন চিহ্ন স্থির (BG-), শেষ চারটি অঙ্ক: 104 = 10,000টি কোড। দৈর্ঘ্য n পর্যন্ত সব binary string গুনলে 1 + 2 + ⋯ + 2n = 2n+1 − 1; n = 5-এ 63. Σ∗ নিজে অসীম, কিন্তু প্রতিটি সদস্য সসীম। এই দুটি কথা একসঙ্গে মনে রাখা জরুরি।
পরীক্ষার ধাঁচে একটি হিসাব (Σ = {a, b, c}): (ক) দৈর্ঘ্য 4-এর কতটি string-এ অন্তত একটি a আছে? সরাসরি না গুনে উল্টো দিক থেকে: মোট 34 = 81, যার মধ্যে a-হীন string হলো {b, c}4, সংখ্যা 24 = 16. উত্তর 81 − 16 = 65. (খ) দৈর্ঘ্য 4-এর palindrome কতটি? প্রথম দুই চিহ্ন বেছে নিলেই শেষ দুটি ঠিক হয়ে যায় (w4 = w1, w3 = w2), তাই 32 = 9; দৈর্ঘ্য 5-এ মাঝের চিহ্নটি স্বাধীন, তাই 33 = 27. (গ) বাজারঘরের যে কুপনের প্রথম চিহ্ন অক্ষর: 26 · 365 = 1,572,120,576. তিনটি উত্তরই scratch-এ সব string গুনে মেলানো হয়েছে।
অসীম সেটকে তালিকা করতে একটি ক্রম লাগে। অভিধানের ক্রম (lexicographic order) এখানে কাজ করে না: Σ = {a, b}-এ অভিধান ক্রমে a, aa, aaa, … অসীমভাবে চলতে থাকে, b-তে কখনো পৌঁছায় না। তাই এই কোর্স ব্যবহার করবে shortlex ক্রম: আগে দৈর্ঘ্য, সমান দৈর্ঘ্যে অভিধান ক্রম। Σ = {a, b}-এ: ε, a, b, aa, ab, ba, bb, aaa, …. এভাবে প্রতিটি string একটি নির্দিষ্ট সসীম অবস্থানে আসে, তাই Σ∗ গোনা যায় (countable). এর পূর্ণ প্রমাণ, ℕ-এর সঙ্গে স্পষ্ট bijection, আছে পর্ব ০২-এ।
Σ∗-কে দৈর্ঘ্যের তলায় ভাগ করা, Σ = {a, b}
প্রতিটি সারি একটি Σk, বাঁ থেকে ডানে shortlex ক্রম। সবুজ ঘরগুলো language L = {a, ab}∗-এর সদস্য (অংশ ৬-এ হিসাব করা হবে)। Language হলো এই বিশাল ছকের যেকোনো বাছাই।
এবার এই সংজ্ঞাগুলো হাতে-কলমে দেখুন। নিচের ব্লক অর্ডার কোডের দৈর্ঘ্য, reversal আর অংশ গোনে, |Σk| = 2k মেলায়, shortlex আর Python-এর sorted()-এর পার্থক্য দেখায়, আর দৈর্ঘ্য 4 পর্যন্ত সব জোড়ায় reversal-এর একটি সূত্র যাচাই করে (প্রমাণ অংশ ৮-এ)। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।
from itertools import product
w = "BG-0042" # a bazarghar order code
print("|w| =", len(w), " w^R =", w[::-1], " count of 0:", w.count("0"))
pre = [w[:i] for i in range(len(w) + 1)]
suf = [w[i:] for i in range(len(w) + 1)]
sub = {w[i:j] for i in range(len(w) + 1) for j in range(i, len(w) + 1)}
print("prefixes:", len(pre), pre[:4], "...")
print("suffixes:", len(suf), " distinct substrings:", len(sub))
S = "ab" # the alphabet, already sorted
for k in range(5): # |S^k| = |S|^k
Sk = ["".join(p) for p in product(S, repeat=k)]
print("k =", k, " |S^k| =", len(Sk), Sk[:4])
def shortlex(n): # all strings of length 0..n, length first
return ["".join(p) for k in range(n + 1) for p in product(S, repeat=k)]
print("shortlex:", shortlex(2))
print("sorted():", sorted(shortlex(2)), " <- not shortlex")
words = shortlex(4)
good = sum((u + v)[::-1] == v[::-1] + u[::-1] for u in words for v in words)
wrong = [(u, v) for u in words for v in words if (u + v)[::-1] != u[::-1] + v[::-1]]
print("pairs:", len(words) ** 2, " (uv)^R == v^R u^R holds:", good)
print("(uv)^R == u^R v^R fails", len(wrong), "times, first:", wrong[0])আসল আউটপুট (ব্রাউজারের Python):
|w| = 7 w^R = 2400-GB count of 0: 2
prefixes: 8 ['', 'B', 'BG', 'BG-'] ...
suffixes: 8 distinct substrings: 28
k = 0 |S^k| = 1 ['']
k = 1 |S^k| = 2 ['a', 'b']
k = 2 |S^k| = 4 ['aa', 'ab', 'ba', 'bb']
k = 3 |S^k| = 8 ['aaa', 'aab', 'aba', 'abb']
k = 4 |S^k| = 16 ['aaaa', 'aaab', 'aaba', 'aabb']
shortlex: ['', 'a', 'b', 'aa', 'ab', 'ba', 'bb']
sorted(): ['', 'a', 'aa', 'ab', 'b', 'ba', 'bb'] <- not shortlex
pairs: 961 (uv)^R == v^R u^R holds: 961
(uv)^R == u^R v^R fails 842 times, first: ('a', 'b')
Python-এ ε হলো ''. দৈর্ঘ্য 7-এর কোডের prefix আর suffix ৮টি করে (n + 1), আর আলাদা substring 28, যেমনটা আগে হিসাব হলো। k = 0-তেও একটি string আছে, ফাঁকাটি: |Σ0| = 1, শূন্য নয়। sorted() অভিধান ক্রমে সাজায়, তাই aa আর ab চলে আসে b-এর আগে; shortlex চাইলে key=lambda s: (len(s), s) দিতে হয়। শেষ দুই লাইন: দৈর্ঘ্য 0 থেকে 4-এর ৩১টি string-এর সব 961টি জোড়ায় (uv)R = vRuR খেটেছে, আর “স্বাভাবিক মনে হওয়া” (uv)R = uRvR ভেঙেছে 842 বার; প্রথম পাল্টা-উদাহরণ u = a, v = b: (ab)R = ba, কিন্তু uRvR = ab. গণনা প্রমাণ নয়, কিন্তু ভুল দাবি ধরার সবচেয়ে সস্তা উপায়।
৪ · Language — Σ∗-এর যেকোনো subset
Σ-এর ওপর একটি language হলো Σ∗-এর যেকোনো subset: L ⊆ Σ∗. সসীম হোক বা অসীম, নিয়ম দিয়ে বর্ণনা করা যাক বা না যাক, প্রতিটি subset-ই একটি language.
“Language” শুনে বাংলা বা ইংরেজির কথা মনে আসে, কিন্তু এখানে অর্থ অনেক সরল: কোন string “ভেতরে”, কোন string “বাইরে”, তার একটি তালিকা। পরীক্ষার ফলাফলের তালিকার মতো: রোল নম্বরের পুরো সেট হলো Σ∗, আর পাস করা রোলগুলো একটি language. বাজারঘরের চারটি language এই কোর্সে বারবার ফিরে আসবে:
| নাম | সংজ্ঞা | উদাহরণ (ভেতরে / বাইরে) | আকার |
|---|---|---|---|
| ORDER | “BG-” তারপর ঠিক চারটি অঙ্ক | BG-0042 / BG-42 | সসীম, 10,000টি |
| COUPON | {A–Z, 0–9}-এর ওপর দৈর্ঘ্য 6 | EID26X / EID2026 | সসীম, 366টি |
| EVEN1 | {0, 1}-এর ওপর, 1-এর সংখ্যা জোড় | 0110, ε / 111 | অসীম |
| BAL | {[, ]}-এর ওপর সুষম বন্ধনী | [[]][], ε / ][ | অসীম |
চারটির মধ্যে দুটি সসীম, দুটি অসীম। পরে দেখবেন, ORDER, COUPON আর EVEN1-কে একটি finite automaton চিনতে পারে, কিন্তু BAL-কে পারে না: অসীম গভীর বন্ধনী মনে রাখতে stack লাগে (প্রমাণ পর্ব ১৭-এ, আর stack-যুক্ত যন্ত্র পর্ব ৩২-এ)। আর একটি বড় ধারণা পর্ব ০৫-এর বিষয়: প্রতিটি হ্যাঁ/না প্রশ্ন আসলে একটি language, তার “হ্যাঁ” উত্তরের ইনপুটগুলোর সেট। “এই কোডটি কি বৈধ?” প্রশ্নের উত্তর দেওয়া মানে “w ∈ ORDER?” বলা।
সবচেয়ে বড় ফাঁদ: ∅, {ε} আর ε. ε একটি string. {ε} একটি language, যার ঠিক একটি সদস্য, ফাঁকা string. ∅ একটি language, যার কোনো সদস্যই নেই। একটি ফর্ম যদি ফাঁকা ঘর জমা নেয়, তার language-এ ε আছে; যদি কোনো ইনপুটই না নেয়, তার language ∅. দুটি একদম আলাদা আচরণ, আর অংশ ৫-৬-এ দেখবেন হিসাবেও এরা উল্টো আচরণ করে।
এখন বাজারঘরের চারটি language-কে ব্রাউজারের JavaScript-এ সদস্যতা-পরীক্ষা হিসেবে লেখা হলো। প্রতিটি ফাংশন একটি string নেয় আর বলে, সেটি language-এ আছে কি না। TESTS বদলে নিজের string দিয়ে আবার চালিয়ে দেখুন।
// bazarghar languages as membership tests. Edit TESTS and run again.
const D = "0123456789", U = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ORDER = w => w.length === 7 && w.startsWith("BG-") && [...w.slice(3)].every(c => D.includes(c));
const COUPON = w => w.length === 6 && [...w].every(c => U.includes(c) || D.includes(c));
const EVEN1 = w => /^[01]*$/.test(w) && [...w].filter(c => c === "1").length % 2 === 0;
const BAL = w => { // depth never below 0, ends at 0
let d = 0;
for (const c of w) {
if (c === "[") d++; else if (c === "]") d--; else return false;
if (d < 0) return false;
}
return d === 0;
};
const LANGS = [["ORDER", ORDER], ["COUPON", COUPON], ["EVEN1", EVEN1], ["BAL", BAL]];
const TESTS = ["BG-0042", "BG-42", "bg-0042", "EID2026", "EID26X", "", "0110", "111", "[[]][]", "[]]["];
for (const w of TESTS) {
const yes = LANGS.filter(([, f]) => f(w)).map(([n]) => n);
console.log(JSON.stringify(w).padEnd(10), yes.join(", ") || "-");
}
const out = []; // BAL members, shortlex, length <= 6
function gen(n, s) {
if (s.length === n) { if (BAL(s)) out.push(s); return; }
gen(n, s + "["); gen(n, s + "]");
}
for (let n = 0; n <= 6; n++) gen(n, "");
console.log("BAL, length <= 6:", out.length, "strings:", out.map(s => s || "ε").join(" "));আসল আউটপুট (ব্রাউজারের JavaScript):
"BG-0042" ORDER
"BG-42" -
"bg-0042" -
"EID2026" -
"EID26X" COUPON
"" EVEN1, BAL
"0110" EVEN1
"111" -
"[[]][]" BAL
"[]][" -
BAL, length <= 6: 9 strings: ε [] [[]] [][] [[[]]] [[][]] [[]][] [][[]] [][][]
তিনটি জিনিস খেয়াল করুন। প্রথমত, ফাঁকা string "" দুটি language-এর সদস্য: শূন্যটি 1 জোড় সংখ্যা, আর ফাঁকা বন্ধনী-সারি সুষম। সংজ্ঞা থেকেই এটি আসে, কিন্তু বাস্তবের validator-এ ε প্রায়ই অপ্রত্যাশিত অতিথি। দ্বিতীয়ত, bg-0042 বাতিল: alphabet-এ ছোট হাতের অক্ষর নেই, আর language-এর সংজ্ঞায় “প্রায় ঠিক” বলে কিছু নেই। তৃতীয়ত, দৈর্ঘ্য 6 পর্যন্ত BAL-এর ৯টি সদস্য shortlex ক্রমে এসেছে; দৈর্ঘ্য 0, 2, 4, 6-এ সংখ্যা 1, 1, 2, 5. এগুলো Catalan সংখ্যা, DSA-তে যে নামে পরিচিত।
৫ · Language-এর operation — set operation আর concatenation
Language যেহেতু সেট, তাই সেটের সব operation চলে (বিস্তারিত ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ১৫-এ): L ∪ M, L ∩ M, L ∖ M. Complement সবসময় Σ∗-এর সাপেক্ষে: L̄ = Σ∗ ∖ L. তাই complement নির্ভর করে alphabet-এর ওপর। {0, 1}-এর ওপর EVEN1-এর complement হলো “1-এর সংখ্যা বিজোড়”; কিন্তু alphabet {0, 1, 2} ধরলে complement-এ 2-যুক্ত সব string-ও ঢুকে যায়। Alphabet না বলে complement বলা অসম্পূর্ণ।
নতুন operation হলো concatenation, যা string-এর জোড়া থেকে language-এ উঠে আসে।
Concatenation: LM = {uv : u ∈ L, v ∈ M}, অর্থাৎ L থেকে একটি, M থেকে একটি string নিয়ে পরপর জোড়া। Power: L0 = {ε}, আর Lk+1 = LkL. তাই Lk হলো L-এর k-টি string (পুনরাবৃত্তি চলবে) পরপর জুড়ে পাওয়া সব string.
বাজারঘরের ভাষায়: ORDER = {BG-}D4, যেখানে D = {0, 1, …, 9}. COUPON = (A ∪ D)6, যেখানে A হলো বড় হাতের ২৬টি অক্ষরের language. ছোট language থেকে বড় language বানানোর এই কৌশলই পর্ব ১৩-এ regular expression হয়ে উঠবে। এখন একটি ছোট উদাহরণ হাতে হিসাব করুন: L1 = {ε, a, ab}, L2 = {b, bb}. সব 3 × 2 = 6টি জোড়া দেখতে হবে।
1ε · b2ε · bb3a · b4a · bb5ab · b6ab · bb7L₁L₂ = ?
| u ∈ L₁ | |
| v ∈ L₂ | |
| uv | |
| এ পর্যন্ত L₁L₂ |
- ε · b. L1-এ ε আছে। ε-এর পরে b জুড়লে b-ই থাকে। তাই ε ∈ L1 হলে L2-এর প্রতিটি string সরাসরি L1L2-এ চলে আসে।
- ε · bb = bb. একই কারণে bb যোগ হলো। এখন সেটে দুটি string.
- a · b = ab. প্রথম সত্যিকারের জোড়া। দৈর্ঘ্য 1 + 1 = 2.
- a · bb = abb. দৈর্ঘ্য 3. সেটে এখন চারটি string.
- ab · b = abb. এই string আগেই আছে (ধাপ ৪-এ a · bb থেকে)। দুটি ভিন্ন জোড়া একই string দিয়েছে, তাই সেট বড় হলো না। এ কারণেই |LM| ≤ |L| · |M|, সমান নাও হতে পারে।
- ab · bb = abbb. শেষ জোড়া, দৈর্ঘ্য 4.
- ফল। shortlex ক্রমে L1L2 = {b, ab, bb, abb, abbb}: ৬টি জোড়া থেকে ৫টি string. উল্টো ক্রমে L2L1 = {b, ba, bb, bab, bba, bbab}, যা আলাদা সেট; concatenation commutative নয়।
দুটি চরম ক্ষেত্র আলাদা করে মনে রাখুন, কারণ এগুলোই পরীক্ষায় সবচেয়ে বেশি আসে। ∅L = L∅ = ∅: জোড়ার প্রথম অংশ বেছে নেওয়ার মতো কোনো string-ই নেই, তাই একটি জোড়াও তৈরি হয় না। {ε}L = L{ε} = L: একমাত্র পছন্দ ε, যা কিছু বদলায় না। সংখ্যার সঙ্গে মিলটি লক্ষ করুন: ∅ আচরণ করে শূন্যের মতো (0 × x = 0), আর {ε} আচরণ করে একের মতো (1 × x = x). কিন্তু union-এ ∅ হলো শূন্য (L ∪ ∅ = L), আর {ε} যোগ করলে L বদলে যেতে পারে।
নতুনরা প্রায়ই union আর concatenation গুলিয়ে ফেলেন, কারণ দুটিই “দুই language মেলানো”। কিন্তু অর্থ আলাদা। L ∪ M মানে “L-এর কোনো string অথবা M-এর কোনো string”; LM মানে “L-এর একটি string, তারপর M-এর একটি”। L = {BG-}, M = {0042}: L ∪ M = {BG-, 0042}, দুটি আলাদা টুকরো; LM = {BG-0042}, একটি পূর্ণ কোড। আকারেও পার্থক্য: |L ∪ M| ≤ |L| + |M|, আর |LM| ≤ |L| · |M|. পরে regex-এ (পর্ব ১৩) এই দুটিই হবে “∪ বা +” আর “পাশাপাশি লেখা”।
Complement আর concatenation একসঙ্গে এলে সতর্ক থাকুন: LM-এর complement সাধারণত L̄M̄ নয়। এক চিহ্নের alphabet {a}-এ L = M = {a} নিন। LM = {aa}, তাই এর complement-এ aa নেই। কিন্তু L̄ = Σ∗ ∖ {a}-এ ε আর aa দুটিই আছে, ফলে aa = aa · ε ∈ L̄M̄. একটি string-ই যথেষ্ট প্রমাণ যে দুই পাশ আলাদা। “চিহ্ন বিতরণ করে দেওয়া” (De Morgan-এর মতো) কৌশল set operation-এ চলে, concatenation-এ চলে না।
৬ · Kleene star, plus, reversal আর homomorphism
L∗ = L0 ∪ L1 ∪ L2 ∪ ⋯, অর্থাৎ L-এর শূন্য বা তার বেশি string পরপর জুড়ে পাওয়া সব string. শূন্যটি জুড়লে পাওয়া যায় ε, তাই সবসময় ε ∈ L∗. Kleene plus: L+ = L1 ∪ L2 ∪ ⋯ = LL∗, অন্তত একটি string.
পকেটে শুধু ২ টাকা আর ৫ টাকার কয়েন, প্রতিটি যত খুশি। কোন অঙ্ক ঠিকঠাক দেওয়া যায়? একটি কয়েনকে দৈর্ঘ্য হিসেবে ভাবুন: L = {aa, aaaaa}, এক চিহ্নের alphabet {a}-এর ওপর। তাহলে L∗ = {an : n = 2x + 5y, x, y ≥ 0}. হিসাব করলে n = 0, 2, 4, 5, 6, 7, 8, … সব আসে, শুধু 1 আর 3 আসে না। শূন্য টাকাও “দেওয়া যায়”, কোনো কয়েন না দিয়েই। এটিই ε ∈ L∗.
L∗ সাধারণত অসীম, তাই হাতে হিসাব মানে একটি দৈর্ঘ্য পর্যন্ত কাটা। L-এর প্রতিটি string-এর দৈর্ঘ্য অন্তত 1 হলে Lk-এর প্রতিটি string-এর দৈর্ঘ্য অন্তত k; তাই দৈর্ঘ্য ≤ n পর্যন্ত চাইলে L0 থেকে Ln দেখলেই যথেষ্ট। নিচে L = {a, ab}-এর L∗ দৈর্ঘ্য 3 পর্যন্ত তৈরি করা হলো; এটিই ছবি ৩.২-এর সবুজ ঘরগুলো।
1L⁰ = {ε}2L¹ = L⁰ · L3L² = L¹ · L4L³ = L² · L5L⁴: সবচেয়ে ছোট দৈর্ঘ্য 46L∗ (দৈর্ঘ্য ≤ 3) = ?
| Lᵏ | |
| দৈর্ঘ্য ≤ 3 অংশ | |
| এ পর্যন্ত L∗ |
- L0 = {ε}. শূন্যটি string জুড়লে ফাঁকা string. L যা-ই হোক, এই ধাপ একই।
- L1 = L = {a, ab}. দুটিই দৈর্ঘ্য ≤ 3, দুটিই রাখা হলো। মোট ৩টি।
- L2 = {a, ab}{a, ab}. a·a = aa, a·ab = aab, ab·a = aba, ab·ab = abab. abab-এর দৈর্ঘ্য 4, বাদ। ৩টি নতুন, মোট ৬টি।
- L3. ৮টি string, কিন্তু দৈর্ঘ্য 3-এর একটিই: aaa, অর্থাৎ তিনবার a জোড়া। বাকিগুলোতে অন্তত একটি ab আছে, তাই দৈর্ঘ্য ≥ 4. মোট ৭টি।
- L4. চারটি অংশ, প্রতিটির দৈর্ঘ্য ≥ 1, তাই সবচেয়ে ছোট string aaaa-র দৈর্ঘ্য 4. দৈর্ঘ্য ≤ 3-এ আর কিছু আসা সম্ভব নয়। থামার এই যুক্তি কাজ করে কারণ ε ∉ L.
- ফল। shortlex ক্রমে: ε, a, aa, ab, aaa, aab, aba. লক্ষ করুন, ba নেই: L-এর প্রতিটি string a দিয়ে শুরু, আর প্রতিটি b-এর ঠিক আগে একটি a. সুন্দর একটি বর্ণনা: L∗ = ε অথবা a দিয়ে শুরু, আর কোথাও bb নেই।
Star-এর কয়েকটি চরম মান: ∅∗ = {ε}, কারণ L0 = {ε} আর বাকি সব Lk = ∅. {ε}∗ = {ε}. আর Σ∗ আসলে Σ-কে এক-চিহ্নের string-এর language ধরে তার star. একটি সূক্ষ্ম তথ্য: L∗ সসীম হয় কেবল দুটি ক্ষেত্রে, L = ∅ অথবা L = {ε}. L-এ দৈর্ঘ্য ≥ 1-এর একটি string x থাকলেই ε, x, xx, xxx, … সবাই L∗-এ, তাই অসীম।
Reversal আর homomorphism
Language-এর reversal: LR = {wR : w ∈ L}. যেমন {ab, abb}R = {ba, bba}. অনুশীলন ২-এর ফলের সঙ্গে মিলিয়ে একই যুক্তিতে দেখা যায় (L∗)R = (LR)∗: কয়েকটি টুকরো জুড়ে উল্টালে টুকরোর ক্রম উল্টায় আর প্রতিটি টুকরোও উল্টায়, কিন্তু উল্টানো টুকরোগুলো তবু LR-এর সদস্য। আর homomorphism হলো প্রতিটি চিহ্নের জায়গায় একটি string বসানোর নিয়ম: একটি ফাংশন h : Σ → Γ∗ (Γ আরেকটি alphabet), যা string-এ ছড়ায় h(ε) = ε, h(wσ) = h(w)h(σ) দিয়ে। ফলে h(uv) = h(u)h(v), আর h(L) = {h(w) : w ∈ L}. উদাহরণ: বাজারঘরের সেন্সর লাইনে h(a) = 01, h(b) = 1 হলে h(aab) = 01011. h(σ) = ε-ও চলে; তখন h সেই চিহ্নটি মুছে দেয়, যেমন “সব হাইফেন মোছা” নিয়মটি BG-0042 থেকে BG0042 বানায়। একটি language-এ প্রয়োগের উদাহরণ: {0, 1}-এর ওপর h(0) = ε, h(1) = 1 নিন, অর্থাৎ সব 0 মুছে ফেলা। তাহলে h(EVEN1) = {ε, 11, 1111, …} = {11}∗: 0-গুলো মুছলে থাকে কেবল জোড় সংখ্যক 1. উল্টো দিকের operation-ও আছে, inverse homomorphism: h−1(M) = {w : h(w) ∈ M}, অর্থাৎ যেসব string-কে h দিয়ে বদলালে M-এ পৌঁছায়। এই h-এর জন্য h−1({11}∗) = EVEN1 ফিরে আসে। কিন্তু সাধারণভাবে h−1(h(L)) = L হয় না; শুধু L ⊆ h−1(h(L)) নিশ্চিত। পর্ব ১৬-এ প্রমাণ হবে, regular language-এর ওপর reversal, homomorphism আর inverse homomorphism করলে regular-ই থাকে।
৭ · অভেদ আর ফাঁদ — কোনটি সত্য, কোনটি নয়
সংখ্যার বীজগণিতে x(y + z) = xy + xz সবাই জানেন। Language-এর বীজগণিতেও অনেক অভেদ আছে, কিন্তু কয়েকটি “দেখতে ঠিক” সূত্র আসলে ভুল। নিচের টেবিলে L, M, K যেকোনো language.
| দাবি | সত্য? | মন্তব্য |
|---|---|---|
| ∅L = L∅ = ∅ | সবসময় | ∅ হলো concatenation-এর “শূন্য” |
| {ε}L = L{ε} = L | সবসময় | {ε} হলো “এক” |
| (LM)K = L(MK) | সবসময় | string-এর associativity থেকে |
| L(M ∪ K) = LM ∪ LK | সবসময় | union-এর ওপর বণ্টন, দুই দিকেই |
| L(M ∩ K) = LM ∩ LK | না | কেবল ⊆ সত্য; পাল্টা-উদাহরণ নিচে |
| ∅∗ = {ε}, {ε}∗ = {ε} | সবসময় | L0 = {ε} থেকে |
| (L∗)∗ = L∗, L∗L∗ = L∗ | সবসময় | star-এর ওপর আবার star নতুন কিছু দেয় না |
| L+ = LL∗ = L∗L | সবসময় | L∗ = L+ ∪ {ε}-ও সবসময় |
| L+ = L∗ ∖ {ε} | শর্তসাপেক্ষ | ঠিক তখনই, যখন ε ∉ L |
| (L ∪ M)∗ = (L∗M∗)∗ | সবসময় | regex সরল করতে কাজে লাগে (পর্ব ১৩) |
| (LM)∗ = L∗M∗ | না | কোনো দিকেই ⊆ নয়, নিচের stepper দেখুন |
| LM = ML | না | একটি চিহ্নের alphabet-এ অবশ্য সত্য |
| (LM)R = MRLR | সবসময় | ক্রম উল্টে যায়; অনুশীলন ২ |
“সবসময় সত্য” দাবিগুলো প্রমাণ করতে হয় দুই দিকের subset দেখিয়ে। একটি নমুনা: L(M ∪ K) = LM ∪ LK. (১) w ∈ L(M ∪ K) হলে w = uv, u ∈ L, v ∈ M ∪ K — concatenation-এর সংজ্ঞা। (২) v ∈ M হলে w ∈ LM, আর v ∈ K হলে w ∈ LK; যেকোনো ক্ষেত্রে w ∈ LM ∪ LK — union-এর সংজ্ঞা, দুটি ক্ষেত্র। (৩) উল্টো দিকে, w ∈ LM হলে w = uv, u ∈ L, v ∈ M ⊆ M ∪ K, তাই w ∈ L(M ∪ K); LK-র জন্যও একই — কারণ M ⊆ M ∪ K সবসময় সত্য। (৪) দুই দিকের subset মিলিয়ে সমতা। ∎ একই কৌশলে ∩-এর বেলায় কেবল প্রথম দিক চলে: w = uv, v ∈ M ∩ K হলে w ∈ LM আর w ∈ LK. কিন্তু উল্টো দিকে w ∈ LM ∩ LK হলে দুই ভাঙন w = u1v1 = u2v2 আলাদা হতে পারে, আর তখন যুক্তি ভেঙে পড়ে।
আরেকটি নমুনা, star-এর জন্য: (L∗)∗ = L∗. (১) যেকোনো X-এর জন্য X ⊆ X∗, কারণ X = X1; X = L∗ বসালে L∗ ⊆ (L∗)∗ — star-এর সংজ্ঞায় k = 1 নিয়ে। (২) উল্টো দিকে w ∈ (L∗)∗ হলে w = w1w2⋯wk, প্রতিটি wi ∈ L∗; k = 0 হলে w = ε ∈ L∗ — star-এর সংজ্ঞা। (৩) প্রতিটি wi নিজেই L-এর কয়েকটি string-এর জোড়া, তাই সব মিলিয়ে w-ও L-এর কয়েকটি string-এর জোড়া, অর্থাৎ w ∈ L∗ — concatenation associative বলে। (৪) দুই দিক মিলিয়ে সমতা। ∎ “জোড়ার জোড়া আসলে একটি বড় জোড়া”, এই এক লাইনের ধারণাই প্রমাণের প্রাণ।
প্রমাণ আর গণনা একসঙ্গে চলুক। নিচের ব্লক দৈর্ঘ্য ≤ 6-এর সব string ধরে অভেদগুলো যাচাই করে। দৈর্ঘ্যে কাটা এখানে নির্ভুল: uv-এর দৈর্ঘ্য ≤ 6 হলে u আর v দুটিই ছোট, তাই কাটা সেট থেকে কোনো দরকারি অংশ হারায় না।
N = 6 # look only at strings of length <= N
def cat(A, B): return {u + v for u in A for v in B if len(u + v) <= N}
def power(L, k):
P = {""} # L^0 = {ε}
for _ in range(k): P = cat(P, L)
return P
def star(L): # L* cut at length N (exact up to N)
out, layer = {""}, {""}
while layer:
layer = cat(layer, L) - out
out |= layer
return out
def show(S): return sorted(S, key=lambda s: (len(s), s))
E, EPS = set(), {""}
L, M, K = {"a", "ab"}, {"b", "ba"}, {"", "b"}
checks = {
"∅L = ∅": cat(E, L) == E,
"{ε}L = L": cat(EPS, L) == L,
"∅* = {ε}": star(E) == EPS,
"(L*)* = L*": star(star(L)) == star(L),
"L*L* = L*": cat(star(L), star(L)) == star(L),
"L(M∪K) = LM∪LK": cat(L, M | K) == cat(L, M) | cat(L, K),
"LL* = L* - {ε}": cat(L, star(L)) == star(L) - EPS,
"KK* = K* - {ε}": cat(K, star(K)) == star(K) - EPS,
"LM = ML": cat(L, M) == cat(M, L),
}
for name, ok in checks.items(): print(name.ljust(16), ok)
print("L^2 =", show(power(L, 2)))
print("L* up to 3:", [w for w in show(star(L)) if len(w) <= 3])
print("LM =", show(cat(L, M)), " ML =", show(cat(M, L)))আসল আউটপুট (ব্রাউজারের Python):
∅L = ∅ True
{ε}L = L True
∅* = {ε} True
(L*)* = L* True
L*L* = L* True
L(M∪K) = LM∪LK True
LL* = L* - {ε} True
KK* = K* - {ε} False
LM = ML False
L^2 = ['aa', 'aab', 'aba', 'abab']
L* up to 3: ['', 'a', 'aa', 'ab', 'aaa', 'aab', 'aba']
LM = ['ab', 'aba', 'abb', 'abba'] ML = ['ba', 'baa', 'bab', 'baab']
প্রথম ছয়টি অভেদ খেটেছে। LL∗ = L∗ ∖ {ε} খেটেছে L = {a, ab}-এর জন্য, কারণ ε ∉ L. কিন্তু K = {ε, b}-এ ε আছে, তাই K+ = KK∗-এ ε থেকে যায় (ε · ε = ε), আর সমতা ভাঙে: False. LM আর ML-এর তালিকা দেখলেই বোঝা যায় কেন commutativity ভাঙে: একটির সব string a দিয়ে শুরু, অন্যটির b দিয়ে। L∗-এর তালিকা দ্বিতীয় stepper-এর ফলের সঙ্গে হুবহু মেলে। মনে রাখবেন, “True” মানে কেবল এই তিনটি language আর দৈর্ঘ্য ≤ 6-এ সত্য; সাধারণ সত্যের জন্য প্রমাণ লাগে।
এবার ভুল অভেদের পাল্টা-উদাহরণ। সবচেয়ে জনপ্রিয় ভুলটি (LM)∗ = L∗M∗. সবচেয়ে ছোট language নিয়ে দেখুন:
1A = {a}, B = {b}2(AB)∗ = {ab}∗3A∗B∗ = {aⁱbʲ}4a: ডানে আছে, বাঁয়ে নেই5abab: বাঁয়ে আছে, ডানে নেই
| (AB)∗ | |
| A∗B∗ |
- সবচেয়ে ছোট পরীক্ষা। পাল্টা-উদাহরণ খুঁজতে সবচেয়ে সরল language নিন: A = {a}, B = {b}. বড় উদাহরণে ভুল লুকিয়ে থাকে, ছোট উদাহরণে বেরিয়ে আসে।
- বাঁ পাশ। AB = {ab}, তাই (AB)∗ = {ε, ab, abab, ababab, …} = {(ab)n : n ≥ 0}.
- ডান পাশ। A∗ = {ai}, B∗ = {bj}, তাই A∗B∗ = {aibj : i, j ≥ 0}: আগে যত খুশি a, তারপর যত খুশি b.
- একটি দিক ভাঙে। a = a1b0 ∈ A∗B∗. কিন্তু (AB)∗-এর প্রতিটি string-এ a আর b সমান সংখ্যায়, তাই a ∉ (AB)∗.
- অন্য দিকও ভাঙে। abab ∈ (AB)∗, কিন্তু এতে একটি b-এর পরে a এসেছে, তাই এটি aibj রূপের নয়: abab ∉ A∗B∗. দুই সেটের কোনোটি অন্যটির subset নয়। সঠিক অভেদটি ভিন্ন: (A ∪ B)∗ = (A∗B∗)∗.
হাতে পাল্টা-উদাহরণ খোঁজা সবসময় এত সহজ নয়। তখন কম্পিউটারকে দিয়ে সব ছোট ক্ষেত্র খুঁজিয়ে নিন। নিচের ব্লক প্রথমে stepper-এর ফল যাচাই করে, তারপর {a, b}-এর ওপর দৈর্ঘ্য ≤ 2-এর string দিয়ে বানানো এক বা দুই সদস্যের সব language নিয়ে L(M ∩ K) ≠ LM ∩ LK-এর প্রথম উদাহরণ খোঁজে।
from itertools import product, combinations
N = 4
def cat(A, B): return {u + v for u in A for v in B if len(u + v) <= N}
def star(L):
out, layer = {""}, {""}
while layer:
layer = cat(layer, L) - out
out |= layer
return out
def show(S): return sorted(S, key=lambda s: (len(s), s))
def first(S): return show(S)[0] if S else None
A, B = {"a"}, {"b"}
lhs, rhs = star(cat(A, B)), cat(star(A), star(B))
print("(AB)* :", show(lhs))
print("only in (AB)*:", first(lhs - rhs), " only in A*B*:", first(rhs - lhs))
words = ["", "a", "b", "aa", "ab", "ba", "bb"]
small = [set(c) for r in (1, 2) for c in combinations(words, r)]
trip = list(product(small, repeat=3))
for L, M, K in trip: # look for L(M ∩ K) != LM ∩ LK
if cat(L, M & K) != cat(L, M) & cat(L, K):
print("L =", show(L), " M =", show(M), " K =", show(K))
print("L(M∩K) =", show(cat(L, M & K)), " LM∩LK =", show(cat(L, M) & cat(L, K)))
break
sub = all(cat(L, M & K) <= cat(L, M) & cat(L, K) for L, M, K in trip)
eq = sum(cat(L, M & K) == cat(L, M) & cat(L, K) for L, M, K in trip)
print("triples:", len(trip), " L(M∩K) ⊆ LM∩LK always:", sub, " equal in", eq)আসল আউটপুট (ব্রাউজারের Python):
(AB)* : ['', 'ab', 'abab']
only in (AB)*: abab only in A*B*: a
L = ['', 'a'] M = [''] K = ['a']
L(M∩K) = [] LM∩LK = ['a']
triples: 21952 L(M∩K) ⊆ LM∩LK always: True equal in 20476
প্রথম দুই লাইন stepper-এর দুই সাক্ষী, abab আর a, নিজে থেকেই খুঁজে পেয়েছে। তারপর ২৮টি ছোট language-এর 21952টি ত্রয়ীর মধ্যে প্রথম পাল্টা-উদাহরণ: L = {ε, a}, M = {ε}, K = {a}. M ∩ K = ∅, তাই L(M ∩ K) = ∅. অথচ a = a · ε ∈ LM, আবার a = ε · a ∈ LK: একই string দুই আলাদা ভাঙনে দুই সেটে ঢুকেছে, ঠিক প্রমাণে যেখানে যুক্তি ভেঙেছিল। ⊆ দিকটি সব ত্রয়ীতে খেটেছে, আর 1476টি ত্রয়ীতে সমতা ভেঙেছে। পরীক্ষায় একটি ছোট, হাতে যাচাই করা যায় এমন পাল্টা-উদাহরণই পূর্ণ উত্তর।
৮ · String-এর ওপর induction — reversal-এর সূত্রের প্রমাণ
Python প্রায় হাজারটি জোড়ায় দেখিয়েছে (uv)R = vRuR. কিন্তু string অসীম সংখ্যক, তাই সব ক্ষেত্রের জন্য প্রমাণ লাগে। String recursive ভাবে তৈরি: ε দিয়ে শুরু, তারপর ডানে একটি করে চিহ্ন যোগ। তাই প্রমাণের স্বাভাবিক হাতিয়ার দৈর্ঘ্যের ওপর mathematical induction (এক লাইনের recap: P(0) আর “P(n) ⇒ P(n + 1)” দেখালে সব n-এর জন্য P(n); বিস্তারিত ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ১০-এ, আর recursive সংজ্ঞায় structural induction আছে পর্ব ১২-এ)। এই কোর্সে প্রমাণের সব কৌশল একসঙ্গে দেখা হবে পর্ব ০৪-এ।
Σ-এর ওপর সব string u আর v-এর জন্য (uv)R = vRuR.
প্রমাণ (|v|-এর ওপর induction; u স্থির নয়, যেকোনো)। P(n) বলে: “সব u আর |v| = n-এর সব v-এর জন্য (uv)R = vRuR.”
- Base, n = 0: তখন v = ε. (uε)R = uR = εuR = εRuR. — uε = u; ε বাঁয়ে বসালে কিছু বদলায় না; εR = ε (সংজ্ঞা)
- Inductive hypothesis: কোনো n ≥ 0-এর জন্য P(n) সত্য। — induction-এর কাঠামো
- |v| = n + 1 হলে v = xσ লেখা যায়, যেখানে |x| = n আর σ ∈ Σ. — শেষ চিহ্নটি আলাদা করা
- (uv)R = (u x σ)R = σ (ux)R. — reversal-এর সংজ্ঞা, ux-কে একটি string ধরে
- = σ (xRuR). — hypothesis, কারণ |x| = n
- = (σxR) uR = (xσ)R uR = vRuR. — associativity, তারপর আবার reversal-এর সংজ্ঞা
- তাই P(n + 1) সত্য, আর induction-এ সব n-এর জন্য P(n). ∎
1εᴿ = ε, (xσ)ᴿ = σxᴿ2base: (uε)ᴿ = εᴿuᴿ3v = xσ, ∣x∣ = n4(uxσ)ᴿ = σ(ux)ᴿ5= σ xᴿuᴿ (IH)6= (xσ)ᴿuᴿ = vᴿuᴿ ∎
| দাবির অংশ | |
| মান |
- সংজ্ঞা দিয়ে শুরু। Reversal-এর recursive সংজ্ঞা: শেষ চিহ্নটি সামনে আনুন, বাকিটা উল্টান। (cd)R = d (c)R = d · c = dc. প্রমাণের প্রতিটি ধাপ এই দুই নিয়মের কোনো একটি ব্যবহার করবে।
- Base. v = ε হলে দুই পাশ uR: u = ab-এ ba. ফাঁকা string-এর ক্ষেত্রটি সবচেয়ে সহজ, কিন্তু বাদ দিলে প্রমাণ অসম্পূর্ণ।
- শেষ চিহ্ন আলাদা। v = cd-কে x = c আর σ = d-তে ভাঙা হলো, |x| = 1. Hypothesis ধরে নিয়েছে দৈর্ঘ্য 1-এর v-তে দাবি সত্য।
- সংজ্ঞা এক ধাপ। uv = abcd, যার শেষ চিহ্ন d. সংজ্ঞায় (abcd)R = d (abc)R. এখানে ux = abc-কে একটি গোটা string হিসেবে দেখা হয়েছে।
- Hypothesis. (abc)R = (a b · c)R = cR(ab)R = c · ba = cba, ছোট দৈর্ঘ্যের দাবি থেকে। তাই বাঁ পাশ d · cba = dcba.
- ডান পাশে ফেরা। d · cR = (cd)R = dc, তাই ডান পাশ vRuR = dc · ba = dcba. দুই পাশ মিলল। উদাহরণ প্রমাণ নয়; এটি শুধু দেখায় প্রতিটি সাধারণ ধাপ একটি নির্দিষ্ট string-এ কী করছে।
উপপাদ্যটি থেকে দুটি ফল সরাসরি আসে। (wR)R = w, |w|-এর ওপর induction-এ: (xσ)R = σxR, তাই ((xσ)R)R = (σxR)R = (xR)RσR = xσ. আর (LM)R = MRLR, যা অনুশীলন ২-এ করবেন। খেয়াল করুন, induction কোন অংশের ওপর চলবে, সেটি বাছাই করাই আসল কাজ। এখানে v-এর ওপর চালানো সুবিধাজনক ছিল, কারণ সংজ্ঞাটি শেষ চিহ্ন দিয়ে লেখা।
String নিয়ে গাণিতিক কাজের একটি শুরু ধরা হয় নরওয়ের গণিতবিদ Axel Thue-র ১৯০৬ ও ১৯১২ সালের প্রবন্ধকে, যেখানে তিনি এমন অসীম শব্দ নিয়ে ভাবেন যাতে কোনো অংশ পরপর দুবার আসে না। Emil Post ১৯৪০-এর দশকে string পুনর্লিখনের নিয়ম নিয়ে কাজ করেন (১৯৪৬ সালের correspondence problem পর্ব ৫৪-এ আসবে)। তারকা চিহ্নটি এসেছে Stephen Kleene-এর ১৯৫৬ সালে প্রকাশিত প্রবন্ধ থেকে (এর আগের RAND প্রতিবেদন ১৯৫১ সালের)। আর Noam Chomsky ১৯৫৬ সালে ভাষাকে “বাক্যের সেট” হিসেবে দেখার যে কাঠামো দেন, “language = string-এর সেট” সংজ্ঞাটি তারই উত্তরাধিকার (পর্ব ০৬)।
আরও গভীরে: Σ∗, concatenation আর ε মিলে বীজগণিতের ভাষায় Σ-এর ওপর free monoid: associative, একটি identity, আর কোনো বাড়তি সম্পর্ক নেই। Levi-র lemma বলে, uv = xy হলে এমন একটি w আছে যাতে হয় u = xw ও y = wv, নয় x = uw ও v = wy; শব্দের সমীকরণের প্রায় সব প্রমাণ এর ওপর দাঁড়ায়। Lyndon আর Schützenberger-এর ১৯৬২ সালের কাজ থেকে আসা একটি ফল বলে, uv = vu ঠিক তখনই, যখন u আর v একই string-এর power (ভাবনার প্রশ্ন ৩)। পরের ধাপে regular language-এর গঠন finite monoid দিয়ে বোঝা যায় (syntactic monoid), যা Myhill–Nerode (পর্ব ১৮)-এর বীজগণিতীয় রূপ।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- ε, {ε} আর ∅-এর পার্থক্য কী? প্রথমটি string, দ্বিতীয়টি এক সদস্যের language, তৃতীয়টি সদস্যহীন language; ∅L = ∅ কিন্তু {ε}L = L.
- |Σ| = m হলে দৈর্ঘ্য n-এর string কতটি? দৈর্ঘ্য n-এর string-এর prefix কতটি? mn; prefix n + 1টি (ε আর string নিজেসহ)।
- L∗ কখন সসীম? কেবল L = ∅ বা L = {ε} হলে; দুই ক্ষেত্রেই L∗ = {ε}.
- (LM)∗ = L∗M∗ কি? না; L = {a}, M = {b}: a ডান পাশে আছে, বাঁ পাশে নেই।
- (uv)R = vRuR প্রমাণ করুন। |v|-এর ওপর induction, v = xσ ভেঙে, উপরের সাত ধাপ।
এই কোর্সের notation — এক টেবিলে
পরের সব পর্ব এই চিহ্নগুলোই ব্যবহার করবে। কোনো বই অন্য চিহ্ন দিলে এই টেবিলের সঙ্গে মিলিয়ে নিন।
| চিহ্ন | অর্থ |
|---|---|
| Σ, Γ | alphabet (সসীম, অশূন্য) |
| a, b, c, σ | একটি চিহ্ন |
| u, v, w, x, y, z | string |
| ε | empty string (অন্য বইয়ে λ) |
| |w|, |w|a, wi | দৈর্ঘ্য, a-এর সংখ্যা, i-তম চিহ্ন (1 থেকে গোনা) |
| uv, wk, wR | concatenation, power (w0 = ε), reversal |
| Σk, Σ∗, Σ+ | দৈর্ঘ্য k-এর সব, সব, ε ছাড়া সব string |
| L, M, K বা L1, L2 | language, L ⊆ Σ∗ |
| ∅, {ε} | সদস্যহীন language, শুধু ε-এর language |
| L̄ | complement, Σ∗ ∖ L |
| LM, Lk, L∗, L+, LR, h(L) | concatenation, power, star, plus, reversal, homomorphism |
| shortlex | আগে দৈর্ঘ্য, তারপর অভিধান ক্রম |
৯ · AI-এর যুগে string আর language
AI assistant এই বিষয়ের সংজ্ঞা নির্ভুলভাবে আওড়াতে পারে, কিন্তু হিসাবে আর প্রমাণে প্রায়ই সূক্ষ্ম ভুল করে, আর সেই ভুল আত্মবিশ্বাসী ভাষায় আসে। এই পর্বের বিষয়ে যে ভুলগুলো বারবার দেখা যায়:
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
| ∅ আর {ε} গুলিয়ে ফেলা, যেমন “∅∗ = ∅” | L0 = {ε} সংজ্ঞা থেকে হিসাব; Python-এ star(set()) |
| “L+ = L∗ ∖ {ε}” শর্ত ছাড়া | ε ∈ L এমন একটি L নিয়ে চেষ্টা, যেমন {ε, b} |
| (LM)∗ = L∗M∗ বা L(M ∩ K) = LM ∩ LK দাবি | ছোট language-এ brute force, পাল্টা-উদাহরণ খোঁজা |
| গোনায় off-by-one: “দৈর্ঘ্য ≤ n” আর “ঠিক n” গুলানো, ε বাদ পড়া | n = 0, 1, 2-এ হাতে তালিকা করে সূত্র মেলানো |
Shortlex চেয়ে sorted() দেওয়া | আউটপুটে b কি aa-র আগে? না হলে ভুল |
| Induction-এ base বাদ, বা hypothesis ভুল দৈর্ঘ্যে প্রয়োগ | প্রতিটি ধাপের পাশে যুক্তি লিখে মেলানো |
| বানানো রেফারেন্স (“অমুক বইয়ের অমুক উপপাদ্য”) | Sipser বা Hopcroft–Motwani–Ullman-এ নিজে খুঁজে দেখা |
AI-কে কাজে লাগানোর ভালো উপায় হলো তাকে দিয়ে দাবি যাচাইযোগ্য করানো: উত্তরের সঙ্গে ছোট পাল্টা-উদাহরণ বা পরীক্ষার কোড চাওয়া, যা আপনি নিজে চালাতে পারবেন।
(উত্তরটি নিজে যাচাই করুন: L = {a}, M = {b} হলে ab ∈ (L ∪ M)∗, কিন্তু ab ∉ L∗ ∪ M∗. তাই অভেদটি মিথ্যা, কেবল ⊇ দিক সত্য।)
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১L0 = {ε} আর ∅∗ = {ε} কেন? “কিছুই না” থেকে একটি সদস্য আসে কীভাবে, আর বাস্তবে এর মূল্য কী?
গণিতে “ফাঁকা গুণফল” সবসময় গুণের identity হয়। 20 = 1, 0! = 1, আর কোনো সংখ্যা না নিয়ে যোগ করলে 0. কারণটি নিয়ম রক্ষা: am · an = am+n সূত্র n = 0-তেও খাটাতে হলে a0 = 1 হতেই হবে। Language-এর বেলায় গুণ হলো concatenation, আর তার identity {ε}, কারণ {ε}L = L. তাই LmLn = Lm+n সূত্রটি টিকিয়ে রাখতে L0 = {ε} নিতেই হয়। ∅∗-এর হিসাব তখন সরল: L0 = {ε}, আর k ≥ 1-এ ∅k = ∅, কারণ ∅-এর সঙ্গে কিছু জোড়া যায় না। Union করলে {ε}.
অর্থের দিক থেকেও এটি স্বাভাবিক। ∅∗ মানে “∅-এর শূন্য বা বেশি string জুড়ে কী পাওয়া যায়”। একটিও না জুড়লে ফাঁকা string পাওয়া যায়, যেমন ২ আর ৫ টাকার কয়েনের উদাহরণে শূন্য টাকা দিতে কোনো কয়েন লাগে না।
বাস্তবের software-এ এই পার্থক্য নিরাপত্তা আর সঠিকতার প্রশ্ন। ধরুন বাজারঘরের ফোন নম্বরের ঘরে কেউ regex লিখলেন ^[0-9]*$. Star-এ ε থাকে, তাই ফাঁকা ঘরও “বৈধ” হয়ে যায়; ডেটাবেসে খালি নম্বর জমা পড়ে। Python-এ re.fullmatch("[0-9]*", "") একটি match দেয়, None নয়। সঠিক নিয়ম হতো + (অন্তত একটি), অথবা দৈর্ঘ্যের নির্দিষ্ট সীমা। উল্টো দিকের ভুলও হয়: কোনো validator যদি একটিও ইনপুট গ্রহণ না করে, তার language ∅, যা পরীক্ষায় ধরা কঠিন কারণ “সব বাতিল” দেখতে কড়া নিরাপত্তার মতো লাগে। Grammar-এ ε-production (পর্ব ২৮) আর automaton-এ ε-transition (পর্ব ১১) ঠিক এই ফাঁকা string-কে আলাদা করে সামলানোর কৌশল।
মূল উপলব্ধি: ε, {ε} আর ∅ তিনটি আলাদা বস্তু, আর এদের আচরণ সূত্রের সামঞ্জস্য থেকে আসে, খেয়াল থেকে নয়। Validator লেখার সময় প্রথম প্রশ্ন হোক: ফাঁকা ইনপুট কি এই language-এ থাকার কথা?
প্র ০২Alphabet কি সবসময় অক্ষরের সেট? বাংলা লেখা, Unicode আর token-এর জগতে “একটি চিহ্ন” আসলে কী?
সংজ্ঞা শুধু বলে, Σ সসীম আর অশূন্য। কোনটিকে “একটি চিহ্ন” ধরবেন, সেটি মডেল বানানোর সিদ্ধান্ত, আর এই সিদ্ধান্ত ফলাফল বদলে দেয়। একই লেখাকে তিনভাবে দেখা যায়। প্রথম, byte হিসেবে: UTF-8-এ প্রতিটি byte একটি চিহ্ন, alphabet-এ 256টি চিহ্ন। বাংলার প্রতিটি অক্ষর সাধারণত তিন byte, তাই “কি” লেখাটি দৈর্ঘ্য 6-এর string. দ্বিতীয়, Unicode code point হিসেবে: Unicode-এর code point 0 থেকে 0x10FFFF, মোট 1,114,112টি সম্ভাব্য মান, যা বড় হলেও সসীম। Python-এর string এই মডেল ব্যবহার করে (Python কোর্সের পর্ব ০৯-এ বাংলা Unicode-এর আলোচনা আছে)। তখন “কি” হলো দুই চিহ্ন: U+0995 কোডের ক আর U+09BF কোডের ি-কার। তৃতীয়, চোখে দেখা অক্ষর-গুচ্ছ (grapheme cluster) হিসেবে: “কি” একটি চিহ্ন।
এখন reversal ভাবুন। Python-এ "কি"[::-1] দেয় “িক”: স্বরচিহ্নটি আগে চলে এসে একা ঝুলে থাকে। গণিত ভুল করেনি; wR-এর সংজ্ঞা code point-এর alphabet ধরে ঠিকই কাজ করেছে। ভুল হয়েছে alphabet বাছাইয়ে। মানুষের চোখে উল্টানো মানে grapheme cluster উল্টানো। যুক্তাক্ষর (যেমন “ক্ষ”, যা ক + ্ + ষ) এই পার্থক্য আরও স্পষ্ট করে।
Compiler-এর জগতে alphabet আরও বিমূর্ত। Lexer অক্ষরের string পড়ে token বানায় (পর্ব ২২), আর parser-এর কাছে প্রতিটি token, যেমন NUMBER বা IF, একটি চিহ্ন। তখন parser-এর alphabet হলো token-এর ধরনগুলোর সেট, যা সসীম, যদিও সম্ভাব্য সংখ্যা অসীম। DNA বিশ্লেষণে alphabet {A, C, G, T}; বাজারঘরের সেন্সরে {0, 1}.
সসীমতার শর্তটি কেন জরুরি, সেটাও এখানে বোঝা যায়। Finite automaton-এর transition table-এ প্রতিটি চিহ্নের জন্য একটি কলাম; চিহ্ন অসীম হলে টেবিল লেখা যেত না। অসীম alphabet-এর ওপর automaton (যেমন register automaton, যা ডেটার মান তুলনা করে) গবেষণার একটি আলাদা শাখা, কিন্তু সেগুলো এই কোর্সের মূল মডেলের বাইরে।
মূল উপলব্ধি: “একটি চিহ্ন কী” প্রশ্নের উত্তর আগে ঠিক করুন, তারপর দৈর্ঘ্য, reversal বা সদস্যতার কথা বলুন। Byte, code point আর token তিনটি আলাদা alphabet, আর একই লেখা তিনটিতে তিন রকম string.
প্র ০৩Concatenation commutative নয়, কিন্তু কখনো কখনো uv = vu হয়। ঠিক কখন? আর এই প্রশ্ন বাস্তবে কোথায় লাগে?
কয়েকটি উদাহরণ দেখুন। u = ab, v = abab হলে uv = ababab = vu. u = aa, v = aaa হলে দুই দিকেই a5. কিন্তু u = ab, v = ba হলে uv = abba, vu = baab, আলাদা। প্রথম দুই জোড়ায় একটি মিল আছে: দুটি string-ই একটি ছোট string-এর power, ab আর (ab)2, বা a2 আর a3.
এটিই সাধারণ নিয়ম, যা সাধারণত Lyndon আর Schützenberger-এর ১৯৬২ সালের কাজের সঙ্গে যুক্ত করে উল্লেখ করা হয়: uv = vu ঠিক তখনই, যখন কোনো string z আর সংখ্যা i, j ≥ 0 আছে যাতে u = zi আর v = zj. এক দিক সহজ: u = zi, v = zj হলে দুই দিকেই zi+j. অন্য দিকের প্রমাণের রূপরেখা: |u| + |v|-এর ওপর strong induction. ধরুন |u| ≤ |v| আর u ≠ ε. uv = vu-তে দুই পাশের শুরু তুলনা করলে u হলো v-এর prefix, তাই v = uv′. বসালে u·uv′ = uv′·u, বাঁ থেকে u কেটে uv′ = v′u. এখন |u| + |v′| ছোট, তাই hypothesis-এ u আর v′ একই z-এর power, আর তখন v = uv′-ও। (u = ε হলে z = v নিলেই চলে।)
এই ফলের পেছনে আছে “পর্যায়” (period) ধারণা। যে string নিজে অন্য কোনো string-এর power নয়, তাকে বলে primitive; প্রতিটি অশূন্য string একটি অনন্য primitive string-এর power. Fine আর Wilf ১৯৬৫ সালে দেখান, একটি string-এর দুটি period p আর q থাকলে আর দৈর্ঘ্য যথেষ্ট বড় হলে (অন্তত p + q − gcd(p, q)), gcd(p, q)-ও একটি period. String matching-এর KMP algorithm-এর failure function (পর্ব ২৩) ঠিক এই period আর “border” (একই সঙ্গে prefix ও suffix) নিয়ে কাজ করে। Data compression-এ পুনরাবৃত্তি খোঁজা, DNA-তে tandem repeat খোঁজা, আর প্রতিযোগিতামূলক programming-এ “string-টি কোন ছোট string-এর পুনরাবৃত্তি” ধরনের প্রশ্ন, সবই এই তত্ত্বের প্রয়োগ।
মূল উপলব্ধি: String-এর বীজগণিত সংখ্যার মতো সরল নয়, কিন্তু নিয়মহীনও নয়। uv = vu-এর মতো একটি সরল সমীকরণ string-এর গভীর গঠন (period, primitive root) প্রকাশ করে, আর সেই গঠনই দ্রুত algorithm-এর ভিত্তি।
প্র ০৪Concatenation-এর পর কি মূল টুকরোগুলো ফিরে পাওয়া যায়? কোড, SMS আর lexer-এ “অনন্যভাবে ভাঙা” কেন জরুরি?
ধরুন বাজারঘর একটি SMS-এ একাধিক কোড জুড়ে পাঠায়, মাঝে কোনো ফাঁকা জায়গা ছাড়া। গ্রাহকের ফোন কি বুঝবে কোথায় একটি কোড শেষ, পরেরটি শুরু? এটি language-এর ভাষায় প্রশ্ন: C একটি “কোড”-এর সেট হলে C∗-এর প্রতিটি string কি C-এর সদস্যে একভাবেই ভাঙা যায়?
সবসময় যায় না। C = {0, 01, 10} নিন। 010 = 0 · 10 = 01 · 0, দুই রকম ভাঙন। এমন C দিয়ে বার্তা পাঠালে গ্রাহক ভুল পড়তে পারেন। অন্যদিকে বাজারঘরের কুপন সবসময় দৈর্ঘ্য 6, তাই প্রতি ৬ চিহ্নে কাটলেই চলে: সমান দৈর্ঘ্যের কোড সবসময় অনন্যভাবে ভাঙা যায়। আরেকটি নিরাপদ শ্রেণি prefix code: কোনো code word অন্যটির prefix নয়। তখন বাঁ থেকে পড়তে পড়তে যেই একটি code word মেলে, সেখানেই কাটা যায়। David Huffman ১৯৫২ সালে data compression-এর যে কোড দেন, সেটি একটি prefix code.
যেকোনো সসীম কোড অনন্যভাবে ভাঙা যায় কি না, সেটি যাচাইয়ের একটি algorithm দেন Sardinas আর Patterson, ১৯৫৩ সালে। মূল ধারণা: দুই ভিন্ন ভাঙন একই string দিলে কোথাও একটি code word অন্যটির prefix, আর বাকি “অবশিষ্ট অংশ”-গুলো অনুসরণ করে দেখা যায় কোনো অবশিষ্ট নিজেই code word হয় কি না। Algorithm-টি সসীম সংখ্যক ধাপে থামে, কারণ সম্ভাব্য অবশিষ্টের সংখ্যা সসীম।
Compiler-এও একই সমস্যা। x=>y লেখাটি কি x, =>, y, নাকি x, =, >y? Lexer সাধারণত “সবচেয়ে লম্বা মিল” (maximal munch) নিয়ম মেনে এই দ্ব্যর্থতা মেটায় (পর্ব ২২)। Grammar-এর স্তরে একই প্রশ্ন ambiguity নামে আসে: একটি বাক্যের দুটি parse tree (পর্ব ২৭)। আর আরও কঠিন রূপ, দুই তালিকার string জুড়ে একই string বানানো যায় কি না, সেটি Post correspondence problem, যা কোনো algorithm দিয়েই সাধারণভাবে সমাধান করা যায় না (পর্ব ৫৪)।
মূল উপলব্ধি: জোড়া দেওয়া সহজ, ভাঙা কঠিন। নকশার সময়েই টুকরোগুলো এমনভাবে বেছে নিন (সমান দৈর্ঘ্য, prefix-free, বা স্পষ্ট বিভাজক) যাতে ভাঙন অনন্য হয়।
প্র ০৫Σ = {0, 1}-এর ওপর মোট কতগুলো language আছে? আর প্রতিটির জন্য কি একটি program লেখা সম্ভব?
ছোট টুকরো দিয়ে শুরু করুন। দৈর্ঘ্য ≤ 2-এর binary string ৭টি: ε, 0, 1, 00, 01, 10, 11. এদের থেকে বানানো language মানে এই ৭টির যেকোনো subset, তাই 27 = 128টি। দৈর্ঘ্য ≤ n নিলে string 2n+1 − 1টি, আর language 22n+1 − 1টি, দ্বিগুণ-সূচকীয় হারে বাড়ে। পুরো Σ∗ নিলে language-এর সেট হলো P(Σ∗), Σ∗-এর power set.
এখানে দুটি অসীমের তুলনা আসে। Σ∗ গোনা যায়: shortlex ক্রমে প্রতিটি string একটি স্বাভাবিক সংখ্যার অবস্থানে বসে (পর্ব ০২-এ প্রমাণ)। কিন্তু Georg Cantor ১৮৯১ সালে diagonal যুক্তিতে দেখান, কোনো সেটের power set তার চেয়ে কঠোরভাবে বড়। তাই P(Σ∗) গোনা যায় না (uncountable); ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ১৮-এ এই যুক্তি আছে।
এবার program গুনুন। প্রতিটি program, তা Python হোক বা Turing machine-এর বর্ণনা, একটি সসীম string, কোনো সসীম alphabet-এর ওপর। তাই সব program-এর সেটও গোনা যায়। প্রতিটি program বড়জোর একটি language চেনে। গোনা যায় এমন সেট থেকে গোনা যায় না এমন সেটের সব সদস্যে পৌঁছানো অসম্ভব। ফলাফল চমকপ্রদ: বেশিরভাগ language-এর জন্য কোনো program-ই নেই, এমনকি “হ্যাঁ” উত্তরগুলো চিনে নেওয়ার মতো দুর্বল program-ও নয়। পর্ব ৫০-৫১-এ এই যুক্তি নিখুঁত হবে, আর একটি নির্দিষ্ট, স্বাভাবিক প্রশ্ন (halting problem) দেখানো হবে যার উত্তর কোনো program দিতে পারে না। বাজারঘরের “এই program কি নিশ্চিতভাবে থামবে?” প্রশ্নটি সেখানেই ফিরে আসবে।
একটি সান্ত্বনাও আছে। যে language-গুলো নিয়ে মানুষ আসলে কাজ করে, সেগুলোর প্রায় সবারই একটি সসীম বর্ণনা আছে: regex, grammar, বা program. আর প্রতিটি সসীম language (যেমন ORDER আর COUPON) সহজেই চেনা যায়, কারণ পুরো তালিকাটিই একটি সসীম বর্ণনা।
মূল উপলব্ধি: “Language = Σ∗-এর যেকোনো subset” সংজ্ঞাটি ইচ্ছা করেই উদার। এই উদারতার কারণেই পরে প্রমাণ করা যায় যে কিছু প্রশ্নের উত্তর কোনো যন্ত্রই দিতে পারে না।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। হিসাবগুলো চাইলে উপরের Python ব্লকে বসিয়েও যাচাই করতে পারেন।
-
নকশা (নিয়ম আর যন্ত্র): (ক) BAL-এর জন্য তিনটি নিয়মের একটি recursive সংজ্ঞা দিন, যা ঠিক সুষম বন্ধনী-string তৈরি করে, আর সেটি দিয়ে দৈর্ঘ্য ≤ 6-এর সব সদস্য তালিকা করুন। (খ) EVEN1-এর জন্য দুই state-এর একটি যন্ত্রের transition table নকশা করুন, আর EVEN1-কে {0}, {1} থেকে concatenation আর star দিয়ে লিখুন।
(ক) নিয়ম: (১) ε ∈ BAL; (২) x ∈ BAL হলে [x] ∈ BAL; (৩) x, y ∈ BAL হলে xy ∈ BAL. Grammar হিসেবে লিখলে S → ε, S → [S], S → SS; পর্ব ২৫-এ এটিই প্রথম context-free grammar. দৈর্ঘ্য ≤ 6-এর ৯টি সদস্য: ε, [], [[]], [][], [[[]]], [[][]], [[]][], [][[]], [][][]. Scratch-এ এই নিয়মগুলো বারবার প্রয়োগ করে পাওয়া সেট “গভীরতা কখনো ঋণাত্মক নয়, শেষে শূন্য” পরীক্ষার সেটের সঙ্গে দৈর্ঘ্য 6 পর্যন্ত হুবহু মিলেছে।
(খ) State E (জোড়, শুরু, গ্রহণযোগ্য) আর O (বিজোড়)। Transition: E-তে 0 পড়লে E, 1 পড়লে O; O-তে 0 পড়লে O, 1 পড়লে E. শুরুতে কোনো 1 পড়া হয়নি, শূন্য জোড়, তাই ε গ্রহণযোগ্য। Language হিসেবে: EVEN1 = {0}∗({1}{0}∗{1}{0}∗)∗, অর্থাৎ শুরুর 0-গুলো, তারপর “একটি 1, কিছু 0, আরেকটি 1, কিছু 0” ব্লক যতবার খুশি। দৈর্ঘ্য 10 পর্যন্ত সব 2047টি binary string-এ এই রূপ আর “1-এর সংখ্যা জোড়” শর্ত মিলেছে। পর্ব ০৭-এ এই যন্ত্রই প্রথম DFA.
-
প্রমাণ: উপপাদ্য ৮.১ ব্যবহার করে প্রমাণ করুন, সব language L, M-এর জন্য (LM)R = MRLR.
দুই দিকের subset দেখাতে হবে।
- w ∈ (LM)R ধরুন। তাহলে w = zR, কোনো z ∈ LM-এর জন্য। — LR-এর সংজ্ঞা
- z = uv, যেখানে u ∈ L, v ∈ M. — concatenation-এর সংজ্ঞা
- w = (uv)R = vRuR. — উপপাদ্য ৮.১
- vR ∈ MR আর uR ∈ LR, তাই w ∈ MRLR. — reversal আর concatenation-এর সংজ্ঞা
- উল্টো দিকে, w ∈ MRLR হলে w = vRuR, v ∈ M, u ∈ L. উপপাদ্য ৮.১-এ w = (uv)R, আর uv ∈ LM, তাই w ∈ (LM)R. — একই সংজ্ঞাগুলো উল্টো ক্রমে
- দুই দিকের subset মিলিয়ে সমতা। ∎
খেয়াল করুন, ক্রম উল্টে যায়: LRMR লিখলে ভুল হতো। L = {a}, M = {b} নিলে (LM)R = {ba}, কিন্তু LRMR = {ab}.
-
প্রমাণের ভুল ধরুন: দাবি: “সব language L, M-এর জন্য LM = ML.” যুক্তি: “w ∈ LM হলে w = uv, u ∈ L, v ∈ M. |uv| = |vu|, আর uv ও vu-তে একই চিহ্ন একই সংখ্যায় আছে। তাই uv = vu, আর w ∈ ML. একইভাবে ML ⊆ LM. ∎” ভুল কোথায়? একটি পাল্টা-উদাহরণ দিন, আর বলুন কোন বিশেষ ক্ষেত্রে দাবিটি সত্য।
ভুল তৃতীয় বাক্যে। সমান দৈর্ঘ্য আর একই চিহ্ন একই সংখ্যায় থাকলেই দুটি string সমান হয় না; string-এ ক্রম-ই আসল। ab আর ba-র দৈর্ঘ্য সমান, চিহ্নও একই, কিন্তু ab ≠ ba. পাল্টা-উদাহরণ: L = {a}, M = {b}: LM = {ab}, ML = {ba}, আলাদা।
দাবিটি সত্য কিছু বিশেষ ক্ষেত্রে: L = M হলে; L বা M-এর একটি ∅ বা {ε} হলে; আর alphabet-এ একটিমাত্র চিহ্ন থাকলে, কারণ তখন প্রতিটি string an রূপের আর aman = anam. সাধারণভাবে, L আর M-এর সব string যদি একই string z-এর power হয়, তাহলেও সত্য (ভাবনার প্রশ্ন ৩)।
-
হিসাব ও আউটপুট অনুমান: (ক) L = {ε, ab, b} হলে L2-এর সব সদস্য shortlex ক্রমে লিখুন; কতটি? (খ) Python-এ
sorted(["ab", "b", "aab", ""])আরsorted(["ab", "b", "aab", ""], key=lambda s: (len(s), s))কী ছাপবে? (গ) Σ = {a, b}-এর ওপর দৈর্ঘ্য ≤ 5-এর string কতটি, আর দৈর্ঘ্য ঠিক 5-এর যে string-এ a জোড় সংখ্যায়, সেগুলো কতটি?(ক) ৯টি জোড়া: ε·ε = ε, ε·ab = ab, ε·b = b, ab·ε = ab, ab·ab = abab, ab·b = abb, b·ε = b, b·ab = bab, b·b = bb. আলাদা string: ε, b, ab, bb, abb, bab, abab, মোট ৭টি। ε ∈ L বলে L ⊆ L2, আর ab, b দুবার এসেছে।
(খ) প্রথমটি অভিধান ক্রম:
['', 'aab', 'ab', 'b']. দ্বিতীয়টি shortlex:['', 'b', 'ab', 'aab']. দুটিই scratch-এ Python চালিয়ে মেলানো।(গ) 1 + 2 + 4 + 8 + 16 + 32 = 26 − 1 = 63. দৈর্ঘ্য 5-এর 32টি string-এর ঠিক অর্ধেক, 16টি, a জোড় সংখ্যায় রাখে: প্রথম চারটি চিহ্ন যা খুশি (24 = 16), শেষ চিহ্নটি জোড়-বিজোড় ঠিক করে দেয়। Brute force-এও 16.
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমΣ = {a, b}-এর এই string-গুলো shortlex ক্রমে (আগে দৈর্ঘ্য, তারপর অভিধান ক্রম) সাজান (▲▼ চেপে সরান)
- ε (ফাঁকা string)
- b
- aa
- ab
- bb
- aab
Σ = {0, 1, 2} হলে দৈর্ঘ্য ঠিক 4-এর string কতটি?
- 12
- 64
- 81
- 4
যেকোনো language L-এর জন্য ∅L (ফাঁকা language আর L-এর concatenation) কী?
- L
- ∅
- {ε}
- L ∪ {ε}
∅∗ (ফাঁকা language-এর Kleene star) কী?
- ∅
- Σ∗
- একটি অসীম language
- {ε}
L = {a, ab} হলে নিচের কোন string L∗-এ নেই?
- ba
- ε
- aab
- aba
যেকোনো দুটি string u আর v-এর জন্য (uv)R সমান কোনটি?
- uRvR
- vRuR
- vu
- uv
L+ = L∗ ∖ {ε} সমতাটি ঠিক কখন সত্য?
- সবসময়
- কখনো না
- L অসীম হলে
- ε ∉ L হলে
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Σ সসীম, অশূন্য চিহ্নের সেট; string সসীম সারি; ε দৈর্ঘ্য 0-এর একমাত্র string; |Σk| = |Σ|k.
- Language মানে Σ∗-এর যেকোনো subset; ∅ ≠ {ε}, আর complement সবসময় Σ∗-এর সাপেক্ষে।
- LM = {uv}, L0 = {ε}, L∗ = ⋃ Lk; ∅L = ∅, {ε}L = L, ∅∗ = {ε}.
- LM ≠ ML, (LM)∗ ≠ L∗M∗, L(M ∩ K) ⊊ LM ∩ LK হতে পারে, আর L+ = L∗ ∖ {ε} কেবল ε ∉ L হলে।
- String-এর ধর্ম প্রমাণ হয় দৈর্ঘ্যের ওপর induction-এ, যেমন (uv)R = vRuR; ছোট দৈর্ঘ্যে brute force ভুল দাবি ধরে।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ০৪ · Theory of Computation-এর প্রমাণ — string-এর ওপর induction, construction আর diagonalizationপরবর্তী পর্বএই পর্বের induction থেকে পুরো প্রমাণ-কৌশলের ভান্ডারে।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র আর তিনটি শেখার পথ।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৩ — Grammar আর formal languageপটভূমিGrammar আর formal language-এর একটি ছোট পরিচয়, BNF থেকে Chomsky-র শ্রেণি।
- Python প্রোগ্রামিং · পর্ব ০৯ — string আর বাংলা Unicodeপাশের ট্র্যাকPython-এর string, slicing আর বাংলা লেখার code point.
- DSA · পর্ব ৫৮ — String matchingগভীরে যানRabin-Karp, KMP আর Z algorithm: prefix আর suffix-এর ধারণা কাজে।