এই পর্বে যা পাবেন
- বর্ণনা থেকে DFA: বিভাজ্যতা, substring, mod k গণনা, product construction আর বাজারঘরের অর্ডার-কোড
- NFA নকশা, subset construction-এর পূর্ণ টেবিল, ε-closure আর ε-NFA থেকে NFA, আর 2n state-এর নিচের সীমা
- Table-filling minimization, regex নকশা, state elimination আর DFA থেকে regular grammar
- CFG নকশা (anbn-এর রূপভেদ, সমান সংখ্যা, query-র শর্ত), ambiguity দূর করা, CNF রূপান্তর আর CYK টেবিল
- PDA নকশা ও configuration trace, Turing machine নকশা ও ধাপ গোনা, Mealy/Moore sequence detector
- মিশ্র “নকশা করুন, যাচাই করুন” সমস্যা, AI-র ভুল ধরা আর ২০ মিনিটের মিনি-সেট
১ · পাতার নিয়ম, ভাগের মানচিত্র আর নকশার পাঁচ ধাপ
মডিউল ১৪-এ স্বাগতম। দর্জি জামা সেলাই করে শেষে গায়ে পরিয়ে মাপ মিলিয়ে দেখেন; মাপ না মিললে কোথায় ভুল, সেটিও তখনই ধরা পড়ে। Automaton আর grammar নকশাও এমন: যন্ত্র বানানো অর্ধেক কাজ, বাকি অর্ধেক হলো দেখানো যে যন্ত্রটি ঠিক সেই language গ্রহণ করে, বেশিও না, কমও না। বিশ্ববিদ্যালয়ের Theory of Computation বা Automata কোর্সে, প্রোগ্রামার পদের লিখিত পরীক্ষায় আর contest-এর প্রস্তুতিতে এই দুই কাজ বারবার আসে। মডিউলের অন্য পর্বগুলো অন্য দিক দেখবে: পর্ব ৮২ “MCQ প্রশ্নব্যাংক — গণনার তত্ত্ব”, পর্ব ৮৩ “লিখিত ও মৌখিক (ভাইভা) প্রশ্ন”, পর্ব ৮৪ “প্রমাণ লেখার অনুশীলন” (pumping lemma, reduction, diagonalization) আর পর্ব ৮৫ “ইন্টারভিউ আর প্রতিযোগিতায় গণনার তত্ত্ব”. তাই এই পাতায় লম্বা প্রমাণ কম; নকশা, রূপান্তর আর trace বেশি।
কোন ভাগে কী, কোন পর্ব ঝালাবেন
| ভাগ | কী আছে | মূল পর্ব |
|---|---|---|
| ২ | DFA: বিভাজ্যতা, substring, mod গণনা, product, অর্ডার-কোড | ০৭, ০৮, ১৮ |
| ৩ | NFA, subset construction, ε-NFA, state বিস্ফোরণ | ০৯–১১ |
| ৪ | Minimization, regex নকশা, state elimination, regular grammar | ০৬, ১৩, ১৫, ১৯ |
| ৫ | CFG নকশা, ambiguity দূর করা, query-র শর্ত | ২৫–২৭, ৪২ |
| ৬ | CNF রূপান্তর, CYK টেবিল | ২৮, ২৯, ৩১ |
| ৭ | PDA নকশা, configuration trace, ভুল খোঁজা | ৩২–৩৪ |
| ৮ | Turing machine: crossing off, {w#w}, binary decrement | ৪৩, ৪৪ |
| ৯ | Mealy/Moore, language-এর শ্রেণি চেনা, AI-র ভুল | ১২, ১৬, ৩৬ |
এই পাতার নিয়ম — প্রশ্নে অন্য কিছু না বললে
| বিষয় | নিয়ম |
|---|---|
| DFA | M = (Q, Σ, δ, q0, F), δ সম্পূর্ণ (total). ছবিতে না আঁকা তীর একটি dead state-এ যায়। |
| Binary সংখ্যা | সবচেয়ে গুরুত্বপূর্ণ বিট আগে পড়া হয়; val(ε) = 0, তাই ε যেকোনো m দিয়ে বিভাজ্য (পর্ব ০৮-এর রীতি)। |
| Regex | Formal regex: ∪, জোড়া লেখা, ∗; চেকারে Python-এর | দিয়ে লেখা, শুধু যাচাইয়ের জন্য |
| PDA | Sipser-এর 6-tuple; তীর “a, x → y” মানে a পড়া, x তোলা, y রাখা; y-র বাঁ চিহ্ন stack-এর ওপরে। শুরুতে $ রাখা হয়, গ্রহণ final state-এ। |
| Turing machine | 7-tuple, তীর “a → b, R”, configuration u q v. প্রথম ঘরে L মানে head নড়ে না; না লেখা নিয়ম মানে reject. চেকার ␣-কে _ দিয়ে ছাপে। |
| CNF | A → BC বা A → a; শুধু নতুন start S0 → ε চলে, আর S0 কোনো ডান পাশে থাকে না। |
| “যাচাই” | প্রশ্নে বলা দৈর্ঘ্য পর্যন্ত সব string-এ brute force; এটি ভুল ধরার জাল, প্রমাণ নয় |
১. প্রতিটি state-এর অর্থ এক লাইনে। “s2 মানে শেষ দুটি চিহ্ন ab”. অর্থ লেখা থাকলে transition প্রায় নিজে থেকেই আসে, আর পরীক্ষক দ্রুত নম্বর দেন।
২. অর্থ থেকে transition. প্রতিটি state আর প্রতিটি চিহ্নের জন্য প্রশ্ন করুন: এই চিহ্ন পড়ার পর মনে রাখার তথ্যটি কী হলো?
৩. শুরু আর গ্রহণ। ε কোন state-এ থাকে আর সেটি গ্রহণযোগ্য কি না, আলাদা করে ভাবুন। সবচেয়ে বেশি নম্বর কাটে এখানেই।
৪. Correctness-এর যুক্তি। DFA-তে invariant (“δ̂(q0, w) = w-এর অর্থ”), grammar-এ দুই দিক: যা উৎপন্ন হয় তা language-এ আছে, আর language-এর সব কিছু উৎপন্ন হয়।
৫. প্রান্তের string দিয়ে পরীক্ষা। ε, এক চিহ্ন, শুধু একটি চিহ্ন দিয়ে গড়া string, আর সীমার ঠিক এপার-ওপার। তারপর ছোট দৈর্ঘ্যে brute force; এই পাতার চেকারগুলো ঠিক এই কাজটিই করে।
খাতায় একটি নকশার উত্তর কীভাবে সাজাবেন
প্রশ্ন: “Σ = {0, 1}-এ শেষ চিহ্ন 1 এমন string-এর DFA দিন।” পূর্ণ নম্বরের উত্তরে পাঁচটি অংশ থাকে, প্রতিটি এক-দুই লাইনের:
1. states and meaning : p = "last symbol is not 1 (or empty)", q = "last symbol is 1"
2. tuple : M = ({p, q}, {0, 1}, δ, p, {q})
3. table : δ(p,0) = p, δ(p,1) = q, δ(q,0) = p, δ(q,1) = q
4. invariant : δ̂(p, w) = q ⇔ w ends in 1 (induction on |w|)
5. tests : ε -> p reject ; 01 -> q accept ; 10 -> p reject
এই কাঠামো সব প্রশ্নে খাটে: PDA-তে “অর্থ” হয় stack-এর invariant, grammar-এ প্রতিটি variable কোন string-গুলো তৈরি করে, TM-এ প্রতিটি state কোন কাজের অংশ। নিচের উত্তরগুলোতে প্রায় সর্বত্র প্রথম তিনটি অংশ লেখা; চতুর্থ অংশ বাংলা ব্যাখ্যায়, আর পঞ্চম অংশের কাজটি করে চেকার।
২ · DFA নকশা — বিভাজ্যতা, substring, mod গণনা আর অর্ডার-কোড
ঝালিয়ে নিন: পর্ব ০৭ · DFA, পর্ব ০৮ · DFA নকশা, পর্ব ১৮ · Myhill–Nerode, পর্ব ১৯ · DFA minimization.
Binary-তে m দিয়ে বিভাজ্যতা: state r = মান mod m, δ(r, b) = (2r + b) mod m, শুরু আর গ্রহণ r0. Substring p খোঁজা: state = “এখন পর্যন্ত p-এর সবচেয়ে লম্বা যে prefix শেষে মিলেছে”. Product construction: state (p, q), দুই যন্ত্র একসঙ্গে চলে; ∩-এ F = F1 × F2, ∪-এ F = (F1 × Q2) ∪ (Q1 × F2). Complement: সম্পূর্ণ DFA-তে শুধু accepting আর বাকি state অদলবদল।
২.১(সহজ) বাজারঘরের গুদামে পণ্য ৫টি করে প্যাক হয়। Σ = {0, 1}-এর ওপর এমন একটি DFA নকশা করুন, যা ঠিক সেই binary string গ্রহণ করে যাদের মান ৫ দিয়ে বিভাজ্য (বড় বিট আগে, val(ε) = 0). (ক) Transition table লিখুন। (খ) 1010 আর 10011-এ state-এর ধারা দেখান। (গ) কেন ৫টির কম state-এ এই কাজ সম্ভব নয়? (ঝালিয়ে নিন: পর্ব ০৮, ১৮)
state r = (value so far) mod 5 ; start r0 ; F = {r0} ; δ(r, b) = (2r + b) mod 5
0 1
r0 r0 r1
r1 r2 r3
r2 r4 r0
r3 r1 r2
r4 r3 r4
(b) 1010 (= 10): r0 -1-> r1 -0-> r2 -1-> r0 -0-> r0 accept
10011 (= 19): r0 -1-> r1 -0-> r2 -0-> r4 -1-> r4 -1-> r4 reject (19 mod 5 = 4)
(c) take residues i ≠ j. Pick a 3-bit suffix z with 8i + val(z) ≡ 0 (mod 5);
val(z) runs over 0..7, so such z exists. Then 8j + val(z) ≢ 0, because
8(j - i) ≢ 0 (mod 5). So r_i and r_j are distinguishable: 5 classes, 5 states.
Invariant হলো δ̂(r0, w) = rval(w) mod 5, আর এর induction প্রমাণ পর্ব ০৮-এর mod 3-এর প্রমাণের হুবহু রূপ। (গ)-র যুক্তি আসলে Myhill–Nerode: পাঁচটি string (ε, 1, 10, 11, 100) জোড়ায় জোড়ায় আলাদা করা যায়। সাধারণ ভুল: বিট উল্টো ক্রমে (ছোট বিট আগে) পড়া ধরে নেওয়া; তখন যন্ত্র সম্পূর্ণ আলাদা হয়।
২.২(সহজ) বাজারঘরের একটি coupon-নিয়ম Σ = {a, b}-এর string-এ “aba” খোঁজে (ওভারল্যাপ চলবে)। (ক) “aba” substring হিসেবে আছে এমন string-এর DFA দিন, প্রতিটি state-এর অর্থসহ। (খ) “aba” নেই এমন string-এর DFA কীভাবে পাবেন? (গ) দৈর্ঘ্য ৬-এর কয়টি string-এ “aba” নেই? (ঝালিয়ে নিন: পর্ব ০৮)
meaning of states (longest prefix of "aba" that ends the input):
s0 = nothing s1 = "a" s2 = "ab" s3 = "aba" already seen (absorbing)
a b
s0 s1 s0
s1 s1 s2 "aa" still ends with "a"
s2 s3 s0 "abb" ends with no prefix of "aba"
s3 s3 s3
start s0 ; F = {s3}
(b) the DFA is complete, so swap: F' = {s0, s1, s2}
(c) 37 strings of length 6 avoid "aba" (checker below)
দুটি তীর ভাবনার: s1 থেকে a-তে s1-এ থাকা (নতুন a নিজেই শুরু), আর s2 থেকে b-তে s0-তে ফেরা। ওভারল্যাপ মানে “ababa”-তে দুবার পাওয়া, কিন্তু “আছে কি না” প্রশ্নে s3 শোষক (absorbing), তাই এর প্রভাব নেই। (খ)-র অদলবদল শুধু সম্পূর্ণ DFA-তে চলে; dead state বাদ দেওয়া partial ছবিতে F উল্টালে ভুল language আসে।
“aba” খোঁজার DFA
s0: কিছু মেলেনি, s1: শেষে a, s2: শেষে ab, s3: aba পাওয়া গেছে। দুই দাগের বৃত্ত accepting, বাঁয়ের খোলা তীর শুরু।
২.৩(মাঝারি) Σ = {a, b}. L1 = {w : a-এর সংখ্যা ≡ 1 (mod 3)}, L2 = {w : b-এর সংখ্যা জোড়}। (ক) Product construction দিয়ে L1 ∩ L2-এর DFA দিন। (খ) একই state-সেটে L1 ∪ L2-এর F কী? (গ) দুই language-এর সবচেয়ে ছোট string কী কী? (ঝালিয়ে নিন: পর্ব ০৮)
M1: states 0, 1, 2 (count of a mod 3) ; M2: states E, O (parity of b)
product: states (i, p), 3 × 2 = 6 ; start (0, E)
δ((i, p), a) = ((i + 1) mod 3, p) δ((i, p), b) = (i, flip p)
(a) ∩ : F = {(1, E)}
(b) ∪ : F = {(1, E), (1, O), (0, E), (2, E)} -> 4 accepting states
(c) shortest in L1 ∩ L2 : "a" shortest in L1 ∪ L2 : ε (0 b's is even)
checker: both machines have 6 states and are already minimal
∪-এর F-এ ভুলটি সাধারণ: অনেকে F1 × F2-এর সঙ্গে শুধু দুই-একটি state যোগ করেন। নিয়মটি মনে রাখুন: “যেকোনো এক উপাদান গ্রহণ করলেই”, তাই (1, ·) দুটি আর (·, E) তিনটি, একটি দুবার গোনা, মোট ৪টি। (গ)-তে ε-কে ভুলবেন না: L2-তে ε আছে, তাই ∪-তেও আছে।
২.৪(মাঝারি) বাজারঘরের অর্ডার-কোড দুই রকম: পুরোনো “BG-” আর তারপর ঠিক ৪টি অঙ্ক, নতুন “BG-” আর তারপর ঠিক ৫টি অঙ্ক। অঙ্ককে একটি চিহ্ন d ধরে Σ = {B, G, -, d}. (ক) দুই রূপই গ্রহণ করে এমন সবচেয়ে ছোট সম্পূর্ণ DFA-তে কয়টি state? (খ) “৪ অঙ্কের পর accept” আর “৫ অঙ্কের পর accept” state দুটি কেন এক করা যায় না? (ঝালিয়ে নিন: পর্ব ০৮, ১৯)
0 -B-> 1 -G-> 2 ---> 3 -d-> 4 -d-> 5 -d-> 6 -d-> 7* -d-> 8*
every other move goes to dead ; from 8 every symbol goes to dead ; dead loops
(a) 9 useful states + dead = 10 states (checker: minimal size 10)
(b) suffix z = "d": from 7 we reach 8 (accept), from 8 we reach dead (reject).
0..6 differ too: each needs a different remaining suffix to accept.
এখানে language সসীম (মাত্র দুটি string), তবু ১০টি state লাগে, কারণ যন্ত্রকে মনে রাখতে হয় কোডের কতটুকু পড়া হলো। পরীক্ষায় dead state গোনা হবে কি না প্রশ্নে লেখা থাকে না; “সম্পূর্ণ DFA” বললে গুনবেন, আর উত্তরে স্পষ্ট লিখবেন যে গুনেছেন।
from itertools import product
def words(sigma, n): return ["".join(t) for k in range(n + 1) for t in product(sigma, repeat=k)]
def run(d, q, w): # d[(state, symbol)] -> state : a total DFA
for c in w: q = d[(q, c)]
return q
def check(name, d, q0, F, sigma, pred, n):
W = words(sigma, n); bad = [w for w in W if (run(d, q0, w) in F) != pred(w)]
R, todo = {q0}, [q0] # reachable states, then Moore refinement
while todo:
q = todo.pop()
for c in sigma:
if d[(q, c)] not in R: R.add(d[(q, c)]); todo.append(d[(q, c)])
part = {q: q in F for q in R}
while True:
new = {q: (part[q],) + tuple(part[d[(q, c)]] for c in sigma) for q in R}
if len(set(new.values())) == len(set(part.values())): break
part = new
print(f"{name}: {len(W)} strings, mismatches {bad[:3]}, minimal states {len(set(part.values()))}")
d5 = {(r, b): (2 * r + int(b)) % 5 for r in range(5) for b in "01"}
check("2.1 div5", d5, 0, {0}, "01", lambda w: int(w or "0", 2) % 5 == 0, 12)
aba = {(0,"a"):1, (0,"b"):0, (1,"a"):1, (1,"b"):2, (2,"a"):3, (2,"b"):0, (3,"a"):3, (3,"b"):3}
check("2.2 has aba", aba, 0, {3}, "ab", lambda w: "aba" in w, 12)
check("2.2 no aba ", aba, 0, {0, 1, 2}, "ab", lambda w: "aba" not in w, 12)
print(" length-6 strings without aba:", sum("aba" not in w for w in words("ab", 6) if len(w) == 6))
pr = {((i, p), c): ((i + (c == "a")) % 3, p ^ (c == "b")) for i in range(3) for p in (0, 1) for c in "ab"}
check("2.3 AND", pr, (0, 0), {(1, 0)}, "ab", lambda w: w.count("a") % 3 == 1 and w.count("b") % 2 == 0, 10)
check("2.3 OR ", pr, (0, 0), {q for q in set(pr.values()) if q[0] == 1 or q[1] == 0}, "ab", lambda w: w.count("a") % 3 == 1 or w.count("b") % 2 == 0, 10)
S = "BG-d"; nxt = {(0,"B"):1, (1,"G"):2, (2,"-"):3, (3,"d"):4, (4,"d"):5, (5,"d"):6, (6,"d"):7, (7,"d"):8}
oc = {(q, c): nxt.get((q, c), "dead") for q in list(range(9)) + ["dead"] for c in S}
check("2.4 order code", oc, 0, {7, 8}, S, lambda w: w in ("BG-dddd", "BG-ddddd"), 8)প্রতিটি লাইনে তিনটি তথ্য: কয়টি string পরীক্ষা হলো, কয়টিতে যন্ত্র আর সংজ্ঞা অমিল (mismatches [] মানে শূন্য), আর reachable state থেকে Moore refinement চালিয়ে পাওয়া minimal state সংখ্যা। ৫ দিয়ে বিভাজ্যতায় 8191 strings ... minimal states 5, “aba”-র যন্ত্র আর তার complement দুটিতেই minimal states 4, দৈর্ঘ্য ৬-এ “aba” ছাড়া 37টি string. Product-এর ∩ আর ∪ দুটিই minimal states 6, আর অর্ডার-কোডে দৈর্ঘ্য ৮ পর্যন্ত 87381 strings-এ কোনো অমিল নেই, minimal states 10.
৩ · NFA নকশা, subset construction আর ε-NFA
ঝালিয়ে নিন: পর্ব ০৯ · NFA, পর্ব ১০ · NFA থেকে DFA, পর্ব ১১ · ε-NFA, পর্ব ১৮ · Myhill–Nerode.
Subset construction: DFA-র শুরু E({q0}), আর δD(S, a) = E(⋃q ∈ S δ(q, a)); শুধু নাগালের উপসেট লিখুন, ∅ হলো dead state, আর যে উপসেটে NFA-র কোনো accepting state আছে সেটি accepting. ε-transition দূর করা: δ′(q, a) = E(δ(E(q), a)), আর q accepting যদি E(q)-তে পুরোনো কোনো accepting state থাকে।
৩.১(মাঝারি) Σ = {a, b}, L = {w : |w| ≥ 2 আর শেষ দুটি চিহ্ন সমান}, অর্থাৎ aa বা bb দিয়ে শেষ। (ক) পাঁচ state-এর একটি NFA দিন। (খ) Subset construction-এর পূর্ণ টেবিল লিখুন (শুধু নাগালের উপসেট)। (গ) ফলের DFA কি minimal? (ঝালিয়ে নিন: পর্ব ০৯, ১০, ১৮)
(a) NFA: 0 loops on a, b ; 0 -a-> a1 -a-> a2 ; 0 -b-> b1 -b-> b2 ; F = {a2, b2}
(the NFA guesses that the last two symbols start now)
(b) subset a b
{0} {0,a1} {0,b1}
{0,a1} {0,a1,a2}* {0,b1}
{0,b1} {0,a1} {0,b1,b2}*
{0,a1,a2}* {0,a1,a2}* {0,b1}
{0,b1,b2}* {0,a1} {0,b1,b2}*
5 reachable subsets out of 2^5 = 32 ; * = accepting
(c) yes. Classes: ε | ends in a, not aa | ends in b, not bb | ends in aa | ends in bb.
ε vs "a": suffix "a" ("a" no, "aa" yes). "a" vs "b": suffix "a". Two accepting
classes differ on suffix "a". So 5 states are needed.
নিচের stepper টেবিলটি সারি ধরে ধরে বানায়। লক্ষ করুন, ৩২টি সম্ভাব্য উপসেটের মাত্র ৫টি নাগালে আসে; পরীক্ষায় সব উপসেট লিখলে সময় নষ্ট, আর অপ্রয়োজনীয় state গোনা হয়। ∅ এখানে আসেনি, কারণ state 0 সব চিহ্নে নিজের কাছে থাকে।
start = {0}
{0} a → {0,a1}
b → {0,b1}
new: {0,a1}, {0,b1}
{0,a1} a → {0,a1,a2}*
b → {0,b1}
found: {0} {0,a1} {0,b1}
{0,a1,a2}
{0,b1} a → {0,a1}
b → {0,b1,b2}*
found: 5 subsets
{0,a1,a2}* a → {0,a1,a2}
b → {0,b1}
{0,b1,b2}* a → {0,a1}
b → {0,b1,b2}
no new subset
DFA: 5 states, 2 accepting
of 2^5 = 32 possible
- শুরু। এই NFA-তে ε নেই, তাই শুরুর state শুধু {0}. a পড়লে 0 নিজে থাকে আর a1-এ যায়: {0,a1}. b-তে একইভাবে {0,b1}.
- প্রথম নতুন সারি। {0,a1}-এ a পড়লে 0 থেকে {0,a1} আর a1 থেকে a2: মোট {0,a1,a2}, যাতে a2 আছে, তাই accepting. b-তে a1-এর কোনো তীর নেই, শুধু 0 থেকে {0,b1}.
- প্রতিসম সারি। {0,b1}-এ b পড়লে {0,b1,b2}, accepting. এখন পাঁচটি উপসেট পাওয়া গেছে।
- Accepting সারি দুটি। {0,a1,a2}-এ a পড়লে আবার নিজে (a2 থেকে কোনো তীর নেই), b-তে {0,b1}. {0,b1,b2}-এ উল্টোটা।
- থামা। নতুন কোনো উপসেট আসেনি, তাই DFA-তে ৫টি state, যার দুটি accepting. সম্ভাব্য ৩২টির বাকি ২৭টি কখনো নাগালে আসে না।
৩.২(মাঝারি) একটি ε-NFA: state q0, q1, q2; q0 –a→ q0, q0 –ε→ q1, q1 –b→ q1, q1 –ε→ q2, q2 –c→ q2; শুরু q0, F = {q2}. (ক) তিন state-এর ε-closure বের করুন। (খ) ε-ছাড়া NFA-র টেবিল আর নতুন F লিখুন। (গ) Subset construction-এ DFA-তে কয়টি state (∅ সহ)? (ঘ) Language-টি এক কথায় কী? (ঝালিয়ে নিন: পর্ব ১১)
(a) E(q0) = {q0, q1, q2} E(q1) = {q1, q2} E(q2) = {q2}
(b) δ'(q, x) = E(δ(E(q), x))
a b c
q0 {q0,q1,q2} {q1,q2} {q2}
q1 ∅ {q1,q2} {q2}
q2 ∅ ∅ {q2}
F' = {q0, q1, q2} (every closure contains q2)
(c) A = {q0,q1,q2} (start, accept): a -> A, b -> B, c -> C
B = {q1,q2} : a -> ∅, b -> B, c -> C
C = {q2} : a -> ∅, b -> ∅, c -> C ; ∅ : dead
4 states including ∅
(d) L = a*b*c*
সবচেয়ে সাধারণ ভুল F′ = {q2} রেখে দেওয়া: তখন ε, “a”, “ab”-এর মতো string বাদ পড়ে, কারণ q0 থেকে ε-তীর ধরে q2-তে যাওয়া যায় অথচ নতুন যন্ত্রে ε-তীর নেই। দ্বিতীয় ভুল শুরুর state-এর closure না নেওয়া; DFA-র শুরু {q0} নয়, E(q0) = {q0, q1, q2}.
৩.৩(কঠিন) Ln = {w ∈ {0, 1}∗ : শেষ থেকে n-তম চিহ্ন 1}। (ক) n + 1 state-এর NFA দিন। (খ) n = 3-এ subset construction-এ কয়টি নাগালের উপসেট? (গ) প্রমাণ করুন যে Ln-এর যেকোনো DFA-তে অন্তত 2nটি state লাগে। (ঝালিয়ে নিন: পর্ব ১০, ১৮)
(a) p0 loops on 0, 1 ; p0 -1-> p1 ; p1 -0,1-> p2 ; ... ; p(n-1) -0,1-> pn ; F = {pn}
(b) n = 3 : 8 reachable subsets (checker: 2, 4, 8, ..., 64 for n = 1..6)
(c) take the 2^n strings of length n. If x ≠ y, they differ at some position i
(1 ≤ i ≤ n). Let z = 0^(i-1). In xz the n-th symbol from the end is x_i,
in yz it is y_i. One is 1, the other 0: exactly one of xz, yz is in L_n.
So the 2^n strings are pairwise distinguishable (a fooling set), and a DFA
must send them to 2^n different states. ∎
এটি পর্ব ১০-এর সেই বিখ্যাত বিস্ফোরণ: n + 1 state-এর NFA, অথচ DFA-তে ঠিক 2n. (গ)-র যুক্তিতে মূল চাল হলো z-এর দৈর্ঘ্য এমনভাবে বাছা যাতে i-তম অবস্থানটি ঠিক “শেষ থেকে n-তম” জায়গায় সরে আসে: |xz| = n + i − 1, আর শেষ থেকে n-তম অবস্থান (n + i − 1) − n + 1 = i.
from itertools import product
from functools import reduce
def closure(eps, S): # epsilon-closure by DFS
S, todo = set(S), list(S)
while todo: todo += [r for r in eps.get(todo.pop(), ()) if r not in S and not S.add(r)]
return frozenset(S)
def subset(delta, eps, q0, sigma): # only reachable subsets; frozenset() is the dead state
start = closure(eps, {q0}); T, todo = {}, [start]
while todo:
S = todo.pop()
if S in T: continue
T[S] = {c: closure(eps, {r for q in S for r in delta.get((q, c), ())}) for c in sigma}
todo += T[S].values()
return start, T
def mismatches(start, T, F, sigma, pred, n):
W = ("".join(t) for k in range(n + 1) for t in product(sigma, repeat=k))
return [w for w in W if bool(reduce(lambda S, c: T[S][c], w, start) & F) != pred(w)]
def show(S): return "{" + ",".join(sorted(S)) + "}" if S else "∅"
N = {("0","a"): {"0","a1"}, ("0","b"): {"0","b1"}, ("a1","a"): {"a2"}, ("b1","b"): {"b2"}}
st, T = subset(N, {}, "0", "ab")
for S in sorted(T, key=lambda S: (len(S), show(S))): print("3.1", show(S).ljust(10), "a ->", show(T[S]["a"]).ljust(10), "b ->", show(T[S]["b"]), "*" * bool(S & {"a2", "b2"}))
print("3.1 mismatches up to length 10:", mismatches(st, T, {"a2", "b2"}, "ab", lambda w: len(w) > 1 and w[-1] == w[-2], 10))
E = {"q0": ["q1"], "q1": ["q2"]}; D = {("q0","a"): {"q0"}, ("q1","b"): {"q1"}, ("q2","c"): {"q2"}}
print("3.2 closures:", [show(closure(E, {q})) for q in ("q0", "q1", "q2")], "| new delta(q0,b) =", show(closure(E, {r for p in closure(E, {"q0"}) for r in D.get((p, "b"), ())})))
st, T = subset(D, E, "q0", "abc")
print("3.2 DFA states incl. ∅:", len(T), "| mismatches vs a*b*c* up to length 8:", mismatches(st, T, {"q2"}, "abc", lambda w: "".join(sorted(w)) == w, 8))
for n in range(1, 7): # L_n: the n-th symbol from the end is 1
print(f"3.3 n={n}: NFA {n + 1} states -> {len(subset({("p0","0"): {"p0"}, ("p0","1"): {"p0","p1"}, **{(f"p{i}", c): {f"p{i+1}"} for i in range(1, n) for c in "01"}}, {}, "p0", "01")[1])} reachable subsets")প্রথম পাঁচ লাইন ৩.১-এর টেবিল, ঠিক উত্তরের মতো; তারকা (*) চিহ্নিত দুটি সারি accepting, আর দৈর্ঘ্য ১০ পর্যন্ত অমিল []. ৩.২-এ closure তিনটি {q0,q1,q2}, {q1,q2}, {q2}, নতুন δ′(q0, b) = {q1,q2}, DFA-তে ∅ সহ 4টি state, আর a∗b∗c∗-এর সঙ্গে দৈর্ঘ্য ৮ পর্যন্ত কোনো অমিল নেই। শেষ ছয় লাইনে Ln-এর নাগালের উপসেট 2, 4, 8, 16, 32, 64: ঠিক 2n.
৪ · Minimization, regex নকশা আর state elimination
ঝালিয়ে নিন: পর্ব ০৬ · Chomsky hierarchy, পর্ব ১৩ · Regular expression, পর্ব ১৫ · Automaton থেকে regex, পর্ব ১৯ · DFA minimization.
Table-filling: আগে নাগালের বাইরের state বাদ; তারপর (accepting, non-accepting) জোড়া দাগানো; এরপর বারবার: (p, q) দাগান যদি কোনো চিহ্নে (δ(p, a), δ(q, a)) আগেই দাগানো। না-দাগানো জোড়াগুলো সমতুল্য। State elimination: নতুন s আর f যোগ করে মাঝের state k সরান; প্রতিটি p → k → q-এর জন্য নতুন লেবেল R1R2∗R3 ∪ R4, যেখানে R1 = p → k, R2 = k-এর loop, R3 = k → q, R4 = আগের p → q.
৪.১(মাঝারি) Σ = {a, b}-এর ওপর DFA: state 0–6; সব q-তে δ(q, a) = q; q ≤ 5-এ δ(q, b) = (q + 1) mod 6; δ(6, b) = 0; শুরু 0; F = {0, 3, 6}. (ক) কোন state অপ্রয়োজনীয়? (খ) Table-filling-এর প্রতিটি রাউন্ডে কোন জোড়া দাগানো হয়? (গ) Minimal DFA আর language কী? (ঝালিয়ে নিন: পর্ব ১৯)
(a) from 0 only 0..5 are reachable -> remove 6 first
(b) round 1: mark every {accepting, non-accepting} pair: 2 · 4 = 8 pairs
round 2 (look at b; a keeps pairs fixed):
(1,2) -> (2,3) marked => mark (1,5) -> (2,0) marked => mark
(2,4) -> (3,5) marked => mark (4,5) -> (5,0) marked => mark
(0,3) -> (1,4), (1,4) -> (2,5), (2,5) -> (3,0): not marked yet
round 3: nothing new -> stop
(c) unmarked: (0,3), (1,4), (2,5) -> classes {0,3} {1,4} {2,5}
minimal DFA: 3 states counting b mod 3 ; L = {w : #b(w) ≡ 0 (mod 3)}
State 6 আগে বাদ না দিলে কী হতো? (6, 0) জোড়া b-তে (0, 1)-এ যায়, যা দাগানো; (6, 3) যায় (0, 4)-এ, তাও দাগানো। ফলে 6 নিজে একটি আলাদা শ্রেণি হয়ে থাকত, আর উত্তর আসত ৪টি state: language একই, কিন্তু “minimal” নয়। তাই ধাপের ক্রম মুখস্থ রাখুন: নাগাল আগে, জোড়া পরে।
৪.২(সহজ থেকে মাঝারি) Σ = {a, b}-এর ওপর regular expression লিখুন: (ক) a-এর সংখ্যা জোড়; (খ) কোথাও “aa” নেই; (গ) প্রতিটি a-এর ঠিক পরেই b; (ঘ) “ab” ঠিক একবার substring হিসেবে আছে। আর বলুন (ক)-র জন্য (aa ∪ b)∗ আর (খ)-র জন্য (b ∪ ab)∗ কেন ভুল। (ঝালিয়ে নিন: পর্ব ১৩)
(a) b*(ab*ab*)* wrong: (aa ∪ b)* misses "aba" (the two a's need not touch)
(b) (b ∪ ab)*(ε ∪ a) wrong: (b ∪ ab)* misses "a" and every string ending in a
(c) (b ∪ ab)* (this one IS the answer of (c): every a is glued to a b)
(d) b*aa*bb*a* i.e. b* a+ b+ a* : one block of a's, then one block of b's
checker: 0 mismatches for all four on 2047 strings (length ≤ 10);
the two wrong answers fail first on "aba" and on "a"
(খ) আর (গ) পাশাপাশি রাখলে শিক্ষাটি পরিষ্কার: একই regex (b ∪ ab)∗ একটি প্রশ্নের সঠিক উত্তর, অন্যটির ভুল। পার্থক্য শুধু শেষে একা একটি a থাকতে পারে কি না। (ঘ)-তে যুক্তি: “ab” মানে a-এর পরে b-তে পা রাখা; ঠিক একবার মানে a-ব্লক থেকে b-ব্লকে একবারই যাওয়া, তার আগে-পরে যা খুশি b বা a.
৪.৩(কঠিন) DFA D: state r0 (শুরু, accepting), r1, r2; a পড়লে ri → r(i+1) mod 3, b পড়লে ri → r(i−1) mod 3. অর্থাৎ L(D) = {w : #a − #b ≡ 0 (mod 3)}. Sipser-এর GNFA পদ্ধতিতে আগে r2, তারপর r1, শেষে r0 সরিয়ে একটি regex বের করুন। (ঝালিয়ে নিন: পর্ব ১৫)
GNFA: s -ε-> r0 ; r0 -ε-> f ; a: r0->r1, r1->r2, r2->r0 ; b: r0->r2, r2->r1, r1->r0
remove r2 (no loop; in: r0 via b, r1 via a ; out: to r0 via a, to r1 via b)
r0 -> r0 : ba r0 -> r1 : a ∪ bb
r1 -> r0 : b ∪ aa r1 -> r1 : ab
remove r1 (loop ab):
r0 -> r0 : ba ∪ (a ∪ bb)(ab)*(b ∪ aa)
remove r0 (loop above, s -ε-> r0 -ε-> f):
s -> f : (ba ∪ (a ∪ bb)(ab)*(b ∪ aa))*
checker: 0 mismatches against "#a - #b ≡ 0 (mod 3)" on all 8191 strings of length ≤ 12
নিচের stepper প্রতিটি সরানো দেখায়। r2 সরানোর সময় চারটি পথ জোড়া লাগে: r0 –b→ r2 –a→ r0 থেকে ba, r0 –b→ r2 –b→ r1 থেকে bb, r1 –a→ r2 –a→ r0 থেকে aa, আর r1 –a→ r2 –b→ r1 থেকে ab. আগের সরাসরি তীর (r0 –a→ r1, r1 –b→ r0) ∪ দিয়ে যোগ হয়, নইলে উত্তর থেকে “a” দিয়ে শুরু পথগুলো হারায়।
s -ε-> r0 -ε-> f a: r0→r1→r2→r0 b: r0→r2→r1→r0
r0→r0 : ba r0→r1 : a ∪ bb r1→r0 : b ∪ aa r1→r1 : ab
r0→r0 :
ba ∪ (a ∪ bb)(ab)*(b ∪ aa)
s→f :
(ba ∪ (a ∪ bb)(ab)*(b ∪ aa))*
8191 strings: 0 mismatches
- GNFA. নতুন শুরু s থেকে r0-তে আর r0 থেকে নতুন accepting f-এ ε-তীর। এখন s-এ কোনো তীর ঢোকে না, f থেকে বের হয় না।
- r2 সরানো। r2-এ নিজের loop নেই, তাই R2∗ = ε. চারটি দুই-ধাপের পথ নতুন লেবেল দেয়; r0 → r1 আর r1 → r0-তে আগের একক তীর ∪ দিয়ে থেকে যায়।
- r1 সরানো। r1-এর loop ab, তাই r0 → r1 → r0 পথের লেবেল (a ∪ bb)(ab)∗(b ∪ aa); আগের loop ba-এর সঙ্গে ∪.
- r0 সরানো। s → r0 → f পথে r0-এর loop-এর star বসে। চেকার দৈর্ঘ্য ১২ পর্যন্ত সব string-এ এই regex আর DFA মিলিয়েছে।
৪.৪(সহজ) ২.২-এর “aba আছে” DFA (s0 শুরু, s3 accepting; s0: a→s1, b→s0; s1: a→s1, b→s2; s2: a→s3, b→s0; s3: a, b→s3) থেকে একটি right-linear regular grammar লিখুন, আর “aaba”-র derivation দেখান। (ঝালিয়ে নিন: পর্ব ০৬)
one variable per state, one rule per arrow, X -> ε for accepting X:
S0 -> aS1 ∣ bS0 S1 -> aS1 ∣ bS2
S2 -> aS3 ∣ bS0 S3 -> aS3 ∣ bS3 ∣ ε
aaba : S0 ⇒ aS1 ⇒ aaS1 ⇒ aabS2 ⇒ aabaS3 ⇒ aaba
checker: the grammar generates 1233 strings of length ≤ 10, exactly those containing "aba"
নিয়মটি যান্ত্রিক: δ(p, x) = q থেকে P → xQ, আর accepting P থেকে P → ε. উল্টো দিকেও একই: right-linear grammar-এর প্রতিটি variable একটি NFA-state. প্রতিটি derivation-এ sentential form-এ ঠিক একটি variable থাকে, শেষে; সেটিই যন্ত্রের “বর্তমান state”.
import re
from itertools import product, combinations
# 4.1: states 0..6 over {a, b}; b adds 1 (mod 6), a stays; state 6 is unreachable
d = {(q, "a"): q for q in range(7)} | {(q, "b"): (q + 1) % 6 for q in range(6)} | {(6, "b"): 0}
F = {0, 3, 6}
R, todo = {0}, [0]
while todo:
q = todo.pop()
for c in "ab":
if d[(q, c)] not in R: R.add(d[(q, c)]); todo.append(d[(q, c)])
print("4.1 reachable:", sorted(R))
marked = {(p, q) for p, q in combinations(sorted(R), 2) if (p in F) != (q in F)}
rnd = 1; print(f" round {rnd}: {len(marked)} pairs marked (accept vs non-accept)")
while True:
new = {(p, q) for p, q in combinations(sorted(R), 2) if (p, q) not in marked
and any(tuple(sorted((d[(p, c)], d[(q, c)]))) in marked for c in "ab")}
if not new: break
marked |= new; rnd += 1; print(f" round {rnd}: newly marked {sorted(new)}")
print(" equivalent pairs:", [pq for pq in combinations(sorted(R), 2) if pq not in marked])
W = ["".join(t) for k in range(11) for t in product("ab", repeat=k)]
def test(name, rx, pred):
bad = [w for w in W if bool(re.fullmatch(rx, w)) != pred(w)]
print(f"4.2 {name:<12} {rx:<16} mismatches: {len(bad)}" + (f", shortest {bad[0]!r}" if bad else ""))
test("even a", "b*(ab*ab*)*", lambda w: w.count("a") % 2 == 0)
test("even a WRONG", "(aa|b)*", lambda w: w.count("a") % 2 == 0)
test("no aa", "(b|ab)*(|a)", lambda w: "aa" not in w)
test("no aa WRONG", "(b|ab)*", lambda w: "aa" not in w)
test("a then b", "(b|ab)*", lambda w: all(w[i + 1:i + 2] == "b" for i, c in enumerate(w) if c == "a"))
test("one ab", "b*aa*bb*a*", lambda w: sum(w[i:i + 2] == "ab" for i in range(len(w))) == 1)প্রথম অংশে নাগালের state [0, 1, 2, 3, 4, 5]: 6 বাদ। রাউন্ড ১-এ 8 pairs, রাউন্ড ২-এ ঠিক চারটি নতুন জোড়া [(1, 2), (1, 5), (2, 4), (4, 5)], তারপর থামা; সমতুল্য জোড়া [(0, 3), (1, 4), (2, 5)]. Regex অংশে চারটি সঠিক উত্তরের প্রতিটিতে mismatches: 0; দুটি ভুল উত্তরে অমিল 792 আর 143টি, সবচেয়ে ছোট উদাহরণ 'aba' আর 'a'.
import re
from itertools import product
W = ["".join(t) for k in range(13) for t in product("ab", repeat=k)]
pred = lambda w: (w.count("a") - w.count("b")) % 3 == 0
# GNFA: s -> r0 (eps), r0 -> f (eps); r_i --a--> r_(i+1), r_i --b--> r_(i-1) (mod 3)
G = {("s", "r0"): "", ("r0", "f"): ""}
for i in range(3): G[(f"r{i}", f"r{(i + 1) % 3}")] = "a"; G[(f"r{i}", f"r{(i - 1) % 3}")] = "b"
def alt(x, y): return y if x is None else x if y is None or x == y else f"({x}|{y})"
def star(x): return "" if not x else f"({x})*"
for k in ["r2", "r1", "r0"]: # eliminate: R1 R2* R3 | R4
ins = [p for (p, q) in G if q == k and p != k]; outs = [q for (p, q) in G if p == k and q != k]
loop = star(G.get((k, k)))
for p in ins:
for q in outs: G[(p, q)] = alt(G.get((p, q)), G[(p, k)] + loop + G[(k, q)])
G = {e: x for e, x in G.items() if k not in e}
print(f"after removing {k}:", {f"{p}->{q}": x for (p, q), x in G.items()})
mine = "(ba|(a|bb)(ab)*(b|aa))*"
for name, rx in (("eliminated", G[("s", "f")]), ("hand", mine)):
print(f"4.3 {name} regex: {sum(bool(re.fullmatch(rx, w)) != pred(w) for w in W)} mismatches on {len(W)} strings")
# 4.4: right-linear grammar read off the 'contains aba' DFA
R = {"S0": ["aS1", "bS0"], "S1": ["aS1", "bS2"], "S2": ["aS3", "bS0"], "S3": ["aS3", "bS3", ""]}
gen, frontier = set(), [("", "S0")]
while frontier:
s, A = frontier.pop()
for rhs in R[A]:
if rhs == "": gen.add(s)
elif len(s) < 10: frontier.append((s + rhs[0], rhs[1:]))
print("4.4 grammar strings up to length 10:", len(gen), "| equal to {w : 'aba' in w}:",
gen == {w for w in W if len(w) <= 10 and "aba" in w})প্রতিটি সরানোর পর তীরের লেবেল ছাপা হয়েছে; r2 সরানোর পরের চারটি লেবেল ba, (a|bb), (b|aa), ab, ঠিক stepper-এর ধাপ ২. শেষে কোডের বানানো regex আর হাতে লেখা regex দুটিরই 0 mismatches on 8191 strings. শেষ লাইনে right-linear grammar দৈর্ঘ্য ১০ পর্যন্ত 1233টি string উৎপন্ন করে, আর সেটটি “aba আছে” সংজ্ঞার সঙ্গে হুবহু সমান: True.
৫ · CFG নকশা আর ambiguity দূর করা
ঝালিয়ে নিন: পর্ব ২৫ · CFG, পর্ব ২৬ · Derivation আর parse tree, পর্ব ২৭ · Ambiguity, পর্ব ৪২ · Grammar নকশা.
নকশার তিন কৌশল: বাসা বাঁধা (S → aSb জোড়া মেলায়), ভাগ করা (S → XY, প্রতিটি অংশ আলাদা grammar), মিলন (S → A ∣ B). একটি string-এর দুটি আলাদা parse tree (বা দুটি leftmost derivation) থাকলে grammar ambiguous. Precedence আর associativity দিয়ে ambiguity দূর করতে স্তর বানান: কম precedence ওপরের স্তরে, আর left associativity-র জন্য left recursion.
৫.১(সহজ থেকে মাঝারি) CFG লিখুন: (ক) {anb2n : n ≥ 0}; (খ) {aibj : i ≤ j}; (গ) {aibj : i ≠ j}; (ঘ) {aibjck : j = i + k}. প্রতিটি কি unambiguous? (খ)-র জন্য S → aSb ∣ Sb ∣ ε কেন দুর্বল উত্তর? (ঝালিয়ে নিন: পর্ব ২৫, ২৭)
(a) S -> aSbb ∣ ε
(b) S -> aSb ∣ B ; B -> bB ∣ ε pairs first, then extra b's
(c) S -> aSb ∣ A ∣ B ; A -> aA ∣ a ; B -> bB ∣ b pairs, then ≥ 1 extra on ONE side
(d) S -> XY ; X -> aXb ∣ ε ; Y -> bYc ∣ ε a^i b^j c^k = (a^i b^i)(b^k c^k)
checker: 0 mismatches on all strings of length ≤ 10 (≤ 7 for (d)),
and every string has exactly 1 parse tree
S -> aSb ∣ Sb ∣ ε gives the right language but "abb" has 2 trees:
S ⇒ Sb ⇒ aSbb ⇒ abb and S ⇒ aSb ⇒ aSbb ⇒ abb
(ঘ)-র কৌশলটি মনে রাখার মতো: j = i + k দেখে b-গুলোকে দুই ভাগে ভাবুন, প্রথম i-টি a-এর জোড়া, বাকি k-টি c-এর জোড়া। (গ)-তে “≠”-কে দুই ক্ষেত্রে ভাঙা হয়েছে: i > j (বাড়তি a) আর i < j (বাড়তি b). (খ)-র দুর্বল grammar-এ language ঠিক, কিন্তু বাড়তি b কোন ধাপে আসবে তা নির্দিষ্ট নয়, তাই দুটি গাছ।
৫.২(কঠিন) Σ = {a, b}, L = {w : a আর b-এর সংখ্যা সমান}। (ক) G: S → aSbS ∣ bSaS ∣ ε কেন L তৈরি করে, তার মূল যুক্তি দিন। (খ) দেখান G ambiguous (“abab”). (গ) একটি unambiguous grammar দিন। (ঝালিয়ে নিন: পর্ব ২৫, ২৭)
(a) ⊆ : each rule adds one a and one b -> counts stay equal.
⊇ : take w ≠ ε in L, say w starts with a. Walk along w keeping d = #a - #b
of the prefix. d starts at 1 and ends at 0; at the FIRST return to 0
the symbol is a b. So w = a u b v, where u and v are balanced and
shorter -> by induction S ⇒* u, S ⇒* v -> S ⇒ aSbS ⇒* w.
(b) abab : S ⇒ aSbS ⇒ abS ⇒ abaSbS ⇒ ababS ⇒ abab (a·ε·b · ab)
S ⇒ aSbS ⇒ abSaSbS ⇒ abaSbS ⇒ ababS ⇒ abab (a·ba·b · ε)
(c) S -> aBS ∣ bAS ∣ ε ; A -> a ∣ bAA ; B -> b ∣ aBB
(B derives the shortest piece that has one more b than a, so the split is forced)
checker: both grammars give exactly L up to length 10; G has 2 trees for abab,
5 for ababab ; the new grammar has 1 tree for every string
(ক)-র “প্রথম ফেরা” যুক্তিই ambiguity-র উৎস দেখায়: G “কোন b-এর সঙ্গে প্রথম a-টি জোড়া বাঁধবে” তা নির্দিষ্ট করে না, তাই abab-এ প্রথম a প্রথম b-এর সঙ্গে বা দ্বিতীয় b-এর সঙ্গে জোড়া বাঁধতে পারে। (গ)-তে B-কে সবচেয়ে ছোট “এক b বেশি” অংশ বানিয়ে সেই পছন্দ মুছে ফেলা হয়েছে। এটি Dyck language-এর জোড়া মেলানোর ভাবনার রূপভেদ।
৫.৩(মাঝারি) বাজারঘরের order-query-র WHERE অংশে শর্তের token: c (একটি তুলনা, যেমন amount >= 1000), AND, OR, NOT, ( আর ). Grammar E → E AND E ∣ E OR E ∣ NOT E ∣ (E) ∣ c. (ক) “c OR c AND c”-এর দুটি গাছ দেখান আর বলুন অর্থে পার্থক্য কী। (খ) NOT > AND > OR precedence আর বাঁ দিক থেকে associativity রেখে একটি unambiguous grammar দিন। (ঝালিয়ে নিন: পর্ব ২৭, ৪২)
(a) tree 1: c OR (c AND c) tree 2: (c OR c) AND c
with c1 = true, c2 = true, c3 = false: tree 1 -> true, tree 2 -> false
(b) E -> E OR T ∣ T
T -> T AND F ∣ F
F -> NOT F ∣ ( E ) ∣ c
checker: up to 7 tokens both grammars give the same 207 strings; in the
ambiguous one 108 of them have 2 or more trees, in the layered one every
string has exactly 1 (c AND c AND c AND c: 5 trees vs 1)
অর্থের পার্থক্যটিই আসল বিপদ: বাজারঘরের query “district = Dhaka OR amount >= 1000 AND paid = no”-এর দুটি ব্যাখ্যায় আলাদা অর্ডার-তালিকা আসে। স্তর বানালে OR সবচেয়ে ওপরে, তাই AND আগে বাঁধে; E → E OR T-এর left recursion “c OR c OR c”-কে বাঁ দিক থেকে জোড়ে। Recursive descent parser লিখতে হলে এই left recursion সরাতে হয় (পর্ব ৩০, ৩৮).
from itertools import product
from functools import lru_cache
def trees(G, w, start="S"): # number of parse trees of w (G has no A =>+ A cycle)
ml = {A: 99 for A in G} # shortest yield of each symbol, by fixpoint
for _ in G: ml = {A: min(sum(ml.get(X, 1) for X in r) for r in G[A]) for A in G}
@lru_cache(None)
def cnt(A, i, j): return sum(seq(rhs, 0, i, j) for rhs in G[A])
@lru_cache(None)
def seq(rhs, k, i, j):
if k == len(rhs): return int(i == j)
X, rest = rhs[k], sum(ml.get(Y, 1) for Y in rhs[k + 1:])
if X not in G: return seq(rhs, k + 1, i + 1, j) if i < j and w[i] == X else 0
return sum(cnt(X, i, m) * seq(rhs, k + 1, m, j) for m in range(i + ml[X], j - rest + 1))
return cnt(start, 0, len(w))
def check(name, G, sigma, pred, n):
W = ["".join(t) for k in range(n + 1) for t in product(sigma, repeat=k)]
T = {w: trees(G, w) for w in W}; bad = [w for w in W if (T[w] > 0) != pred(w)]
print(f"{name}: {len(W)} strings, mismatches {bad[:3]}, max parse trees {max(T.values())}")
return T
c = str.count; ab = lambda w: w == "a" * c(w, "a") + "b" * c(w, "b") # w is in a*b*
check("5.1a a^n b^2n ", {"S": ["aSbb", ""]}, "ab", lambda w: ab(w) and 2 * c(w, "a") == c(w, "b"), 10)
check("5.1b i <= j ", {"S": ["aSb", "B"], "B": ["bB", ""]}, "ab", lambda w: ab(w) and c(w, "a") <= c(w, "b"), 10)
check("5.1c i != j ", {"S": ["aSb", "A", "B"], "A": ["aA", "a"], "B": ["bB", "b"]}, "ab", lambda w: ab(w) and c(w, "a") != c(w, "b"), 10)
check("5.1d j = i + k", {"S": ["XY"], "X": ["aXb", ""], "Y": ["bYc", ""]}, "abc", lambda w: "".join(sorted(w)) == w and c(w, "b") == c(w, "a") + c(w, "c"), 7)
T = check("5.2 equal (amb)", {"S": ["aSbS", "bSaS", ""]}, "ab", lambda w: c(w, "a") == c(w, "b"), 10)
print(" trees: ab ->", T["ab"], "| abab ->", T["abab"], "| aabb ->", T["aabb"], "| ababab ->", T["ababab"])
check("5.2 equal (unamb)", {"S": ["aBS", "bAS", ""], "A": ["a", "bAA"], "B": ["b", "aBB"]}, "ab", lambda w: c(w, "a") == c(w, "b"), 10)৫.১-এর চারটি grammar-এ mismatches [] আর max parse trees 1: language ঠিক, আর পরীক্ষিত কোনো string-এ দুটি গাছ নেই। ৫.২-এর G-তে অমিল নেই, কিন্তু max parse trees 42; ছোট উদাহরণে ab -> 1, abab -> 2, aabb -> 1, ababab -> 5. নতুন grammar-এ একই language, আর max parse trees 1. মনে রাখবেন, “দৈর্ঘ্য ১০ পর্যন্ত একটি গাছ” unambiguity-র প্রমাণ নয়; প্রমাণ হলো (গ)-র “বিভাজন বাধ্যতামূলক” যুক্তি।
# runs after the previous block (data-shared): reuses trees()
# tokens: c = condition, & = AND, + = OR, ! = NOT, ( and )
AMB = {"E": ["E&E", "E+E", "!E", "(E)", "c"]}
LAY = {"E": ["E+T", "T"], "T": ["T&F", "F"], "F": ["!F", "(E)", "c"]}
def lang(G, n): # leftmost expansion; no eps-rules, so forms never shrink
out, seen, todo = set(), {"E"}, ["E"]
while todo:
f = todo.pop()
i = next((k for k, X in enumerate(f) if X in G), None)
if i is None: out.add(f); continue
for rhs in G[f[i]]:
g = f[:i] + rhs + f[i + 1:]
if len(g) <= n and g not in seen: seen.add(g); todo.append(g)
return out
A, L = lang(AMB, 7), lang(LAY, 7)
print("5.3 strings up to 7 tokens: ambiguous", len(A), "| layered", len(L), "| same set:", A == L)
tA = {w: trees(AMB, w, "E") for w in A}; tL = {w: trees(LAY, w, "E") for w in L}
print(" ambiguous grammar: strings with 2+ trees =", sum(t > 1 for t in tA.values()),
"| layered grammar: max trees =", max(tL.values()))
pretty = lambda w: w.replace("&", " AND ").replace("+", " OR ").replace("!", "NOT ")
for w in ["c+c&c", "!c&c", "c&c&c&c", "(c+c)&!c"]:
print(f" {pretty(w):<22} trees: ambiguous {tA.get(w, trees(AMB, w, 'E'))}, layered {trees(LAY, w, 'E')}")এই ব্লক আগের ব্লকের trees() ব্যবহার করে (দুটি একসঙ্গে চলে)। ৭টি token পর্যন্ত দুই grammar-এর language একই, 207টি string, same set: True. দ্ব্যর্থক grammar-এ 108টির একাধিক গাছ, স্তরের grammar-এ max trees = 1. শেষ চার লাইনে c OR c AND c আর NOT c AND c-এ ২টি গাছ, c AND c AND c AND c-এ ৫টি (Catalan সংখ্যা C3), স্তরের grammar-এ সবসময় ১টি।
৬ · CNF রূপান্তর আর CYK টেবিল
ঝালিয়ে নিন: পর্ব ২৮ · Grammar সরলীকরণ, পর্ব ২৯ · Chomsky normal form, পর্ব ৩১ · CYK.
CNF-এ রূপান্তরের ক্রম: নতুন start S0 → S; nullable বের করে ε-rule দূর; unit rule দূর; লম্বা ডান পাশ ভেঙে দুই-চিহ্নে; দুই-চিহ্নের ডান পাশে terminal থাকলে নতুন variable. CNF-এ দৈর্ঘ্য n ≥ 1-এর string-এর derivation ঠিক 2n − 1 ধাপ। CYK: T[i, l] = w-এর i থেকে l দৈর্ঘ্যের টুকরো যেসব variable থেকে আসে; l = 1 সরাসরি, তারপর প্রতিটি ভাগ k-এর জন্য A → BC যেখানে B ∈ T[i, k], C ∈ T[i + k, l − k].
৬.১(মাঝারি) G: S → aSc ∣ B, B → bB ∣ ε. L(G) = {anbmcn : n, m ≥ 0}. (ক) Sipser-এর ক্রমে G-কে CNF-এ রূপান্তর করুন, প্রতিটি ধাপ দেখিয়ে। (খ) CNF grammar-এ “abbc”-এর leftmost derivation-এ কয়টি ধাপ? (ঝালিয়ে নিন: পর্ব ২৮, ২৯)
1. new start : S0 -> S
2. nullable : B (B -> ε), S (S -> B), S0 (S0 -> S)
remove ε-rules : S0 -> S ∣ ε ; S -> aSc ∣ ac ∣ B ; B -> bB ∣ b
3. unit rules : S -> B gives S -> bB ∣ b
S0 -> S gives S0 -> aSc ∣ ac ∣ bB ∣ b ∣ ε
4. terminals : A -> a ; C -> c ; D -> b
5. long rules : aSc -> A U with U -> S C
final CNF:
S0 -> AU ∣ AC ∣ DB ∣ b ∣ ε
S -> AU ∣ AC ∣ DB ∣ b
U -> SC B -> DB ∣ b
A -> a C -> c D -> b
(b) |abbc| = 4 -> 2·4 - 1 = 7 steps:
S0 ⇒ AU ⇒ aU ⇒ aSC ⇒ aDBC ⇒ abBC ⇒ abbC ⇒ abbc
ধাপ ২-এ সবচেয়ে বেশি ভুল হয়: S → aSc থেকে S মুছে “ac” যোগ করতে ভুলে গেলে n = 1, m = 0-এর string “ac” হারিয়ে যায়। চেকার CNF-এর আকার (প্রতিটি rule ঠিক রূপে, S0 কোনো ডান পাশে নেই) আর দৈর্ঘ্য ৭ পর্যন্ত {a, b, c}-এর সব ৩২৮০টি string-এ language মিলিয়েছে।
৬.২(মাঝারি) CNF grammar: S → AB ∣ BC, A → BA ∣ a, B → CC ∣ b, C → AB ∣ a. CYK দিয়ে দেখান “abaab” ∈ L(G) কি না; পুরো টেবিল দিন। চূড়ার ঘরের S কোন কোন ভাগ থেকে আসে, আর তা থেকে parse tree সম্পর্কে কী বলা যায়? (ঝালিয়ে নিন: পর্ব ৩১)
w = a b a a b (row l = length of the piece, left to right by start i)
l=5: {C,S}
l=4: {A,S} ∅
l=3: {B} ∅ {B}
l=2: {C,S} {A,S} {B} {C,S}
l=1: {A,C} {B} {A,C} {A,C} {B}
S ∈ T[0,5] -> abaab ∈ L(G)
S at the top comes from two splits:
k = 3 : aba ∣ ab with S -> BC (B ∈ T[0,3], C ∈ T[3,2])
k = 4 : abaa ∣ b with S -> AB (A ∈ T[0,4], B ∈ T[4,1])
-> at least two different parse trees (count: exactly 2)
পর্ব ৩১-এ একই grammar “baaba”-তে চালানো হয়েছিল; এখানে নতুন string, তাই হাতে করে মিলিয়ে নিন। দুটি ফাঁকা ঘর “baab” আর “baa”: কোনো ভাগেই নিয়মের ডান পাশ মেলে না। চূড়ায় দুটি আলাদা back-pointer মানে grammar-টি ambiguous, কারণ একই string-এর দুটি গাছ।
a b a a b
{A,C} {B} {A,C} {A,C} {B}
ab ba aa ab
{C,S} {A,S} {B} {C,S}
{A,C} {B} {A,C} {A,C} {B}
aba baa aab
{B} ∅ {B}
{C,S} {A,S} {B} {C,S}
abaa baab
{A,S} ∅
{B} ∅ {B}
abaab
{C,S} S আছে: গৃহীত
k=3: B·C k=4: A·B
- এক অক্ষরের ঘর। a আসে A → a আর C → a থেকে, তাই {A,C}; b আসে শুধু B → b থেকে, {B}.
- দুই অক্ষর। “ab”: জোড় AB আর CB; S → AB আর C → AB মেলে, {C,S}. “ba”: BA আর BC থেকে A আর S. “aa”: শুধু CC মেলে, B → CC, তাই {B}.
- তিন অক্ষর। “aba”-র ভাগ a∣ba দেয় AA, AS, CA, CS: কিছু মেলে না; ab∣a দেয় CC: {B}. “baa”-র কোনো ভাগে মিল নেই: ∅. “aab”: a∣ab-এ CC মেলে, তাই {B}.
- চার অক্ষর। “abaa”-র ভাগ aba∣a থেকে BA আর BC: {A,S}. “baab”-এর তিনটি ভাগের কোনোটিতে মিল নেই: ∅.
- চূড়া। aba∣ab থেকে BC = S, আর abaa∣b থেকে AB = S আর C. চূড়ায় S, তাই string গৃহীত; S দুটি ভাগ থেকে আসায় দুটি parse tree.
from itertools import product
def cyk(G, w, start): # G: {A: [("B", "C") or ("a",)]} in CNF; T[i, l] = vars deriving w[i:i+l]
n = len(w); T = {}
if n == 0: return ("",) in G[start], T
for i in range(n): T[i, 1] = {A for A in G if (w[i],) in G[A]}
for l in range(2, n + 1):
for i in range(n - l + 1):
T[i, l] = {A for A in G for r in G[A] if len(r) == 2 and any(
r[0] in T[i, k] and r[1] in T[i + k, l - k] for k in range(1, l))}
return start in T[0, n], T
# 6.1: S -> aSc | B, B -> bB | eps converted to CNF (start S0)
CNF = {"S0": [("A","U"), ("A","C"), ("D","B"), ("b",), ("",)], "S": [("A","U"), ("A","C"), ("D","B"), ("b",)],
"U": [("S","C")], "B": [("D","B"), ("b",)], "A": [("a",)], "C": [("c",)], "D": [("b",)]}
ok_form = all((len(r) == 2 and all(x in CNF and x != "S0" for x in r)) or (len(r) == 1 and r[0] not in CNF)
or (A == "S0" and r == ("",)) for A in CNF for r in CNF[A])
W = ["".join(t) for k in range(8) for t in product("abc", repeat=k)]
pred = lambda w: w == "a" * w.count("a") + "b" * w.count("b") + "c" * w.count("c") and w.count("a") == w.count("c")
print("6.1 CNF shape ok:", ok_form, "| mismatches vs a^n b^m c^n up to length 7:",
[w for w in W if cyk(CNF, w, "S0")[0] != pred(w)][:3], f"({len(W)} strings)")
# 6.2: the grammar S -> AB | BC, A -> BA | a, B -> CC | b, C -> AB | a
G = {"S": [("A","B"), ("B","C")], "A": [("B","A"), ("a",)], "B": [("C","C"), ("b",)], "C": [("A","B"), ("a",)]}
for w in ["abaab", "bbab"]:
acc, T = cyk(G, w, "S")
print(f"6.2 {w}: accepted = {acc}")
for l in range(len(w), 0, -1):
print(f" l={l}:", " ".join("{" + ",".join(sorted(T[i, l])) + "}" if T[i, l] else "∅" for i in range(len(w) - l + 1)))প্রথম লাইন: CNF-এর আকার True, আর {a, b, c}-এর 3280টি string-এ anbmcn-এর সঙ্গে অমিল []. তারপর “abaab”-এর টেবিল ওপরের সারি থেকে নিচে: l=5: {C,S}, l=4: {A,S} ∅, … , l=1: {A,C} {B} {A,C} {A,C} {B}, উত্তরের সঙ্গে হুবহু এক। শেষে তুলনার জন্য আরেকটি string “bbab”: সেটিও গৃহীত, চূড়ায় {C,S}.
৭ · PDA নকশা আর configuration trace
ঝালিয়ে নিন: পর্ব ৩২ · Pushdown automaton, পর্ব ৩৩ · PDA-র গ্রহণ, পর্ব ৩৪ · PDA আর CFG.
PDA P = (Q, Σ, Γ, δ, q0, F). তীর “a, x → y”: a পড়ুন (ε হলে কিছু না পড়ে), stack-এর ওপর থেকে x তুলুন, y রাখুন। Configuration (q, বাকি input, stack), stack-এর ওপর বাঁ দিকে; এক ধাপ ⊢. নকশার ধাঁচ: শুরুতে $, জমা করার ধাপ আর মেলানোর ধাপ, শেষে “ε, $ → ε” দিয়ে খালি stack নিশ্চিত করে accepting state.
৭.১(সহজ) {anb2n : n ≥ 0}-এর PDA নকশা করুন (একবারে দুটি চিহ্ন রাখার সংক্ষিপ্ত রূপ “a, ε → xx” চলবে)। “aabbbb”-এর পুরো configuration ধারা লিখুন। ε কীভাবে গৃহীত হয়? (ঝালিয়ে নিন: পর্ব ৩২)
states q1 (start), q2, q3, q4 ; F = {q4}
q1 -> q2 : ε, ε -> $
q2 -> q2 : a, ε -> xx (two x for every a)
q2 -> q3 : b, x -> ε
q3 -> q3 : b, x -> ε
q3 -> q4 : ε, $ -> ε
q2 -> q4 : ε, $ -> ε (n = 0: accepts ε)
aabbbb: (q1, aabbbb, ε) ⊢ (q2, aabbbb, $) ⊢ (q2, abbbb, xx$) ⊢ (q2, bbbb, xxxx$)
⊢ (q3, bbb, xxx$) ⊢ (q3, bb, xx$) ⊢ (q3, b, x$) ⊢ (q3, ε, $) ⊢ (q4, ε, ε)
q2 → q4-এর ε-তীর শুধু তখনই চলে যখন ওপরে $, অর্থাৎ কোনো a পড়া হয়নি; তাই এটি ε ছাড়া আর কিছু বাড়তি গ্রহণ করে না। এই তীর বাদ দিলে যন্ত্রটি ε বর্জন করে, আর language হয়ে যায় n ≥ 1, প্রশ্নের চেয়ে ছোট।
৭.২(মাঝারি) {w ∈ {a, b}∗ : #a = #b}-এর PDA নকশা করুন, stack-এর invariant লিখুন, আর “abba”-র configuration ধারা দিন। (ঝালিয়ে নিন: পর্ব ৩২, ৩৪)
states q1 (start), q2, q3 ; F = {q3}
q1 -> q2 : ε, ε -> $
q2 -> q2 : a, $ -> a$ ; a, a -> aa ; a, b -> ε
q2 -> q2 : b, $ -> b$ ; b, b -> bb ; b, a -> ε
q2 -> q3 : ε, $ -> ε
invariant: after reading u, the stack is s^k $ where k = |#a(u) - #b(u)|
and s is the symbol that is ahead (no s when k = 0)
abba: (q1, abba, ε) ⊢ (q2, abba, $) ⊢ (q2, bba, a$) ⊢ (q2, ba, $)
⊢ (q2, a, b$) ⊢ (q2, ε, $) ⊢ (q3, ε, ε)
Invariant থেকেই সঠিকতা: input শেষে ওপরে $ মানে k = 0, অর্থাৎ সংখ্যা সমান, আর তখনই q3-তে যাওয়া যায়। ε-তীরটি input-এর মাঝেও নেওয়া যায় (nondeterminism), কিন্তু q3 থেকে আর কোনো তীর নেই, তাই মাঝপথে গেলে সেই শাখা মরে যায়।
৭.৩(কঠিন) একজন {wwR : w ∈ {a, b}∗}-এর জন্য এই PDA লিখেছেন: q1 → q2: ε, ε → $; q2 → q2: a, ε → a আর b, ε → b; q2 → q3: ε, ε → ε; q3 → q3: a, a → ε আর b, b → ε; q3 → q4: ε, ε → ε; F = {q4}. ভুলটি খুঁজুন, সবচেয়ে ছোট counterexample দিন, আর ঠিক করুন। (ঝালিয়ে নিন: পর্ব ৩২)
bug: q3 -> q4 does not check that the stack is back at $.
"a": (q1, a, ε) ⊢ (q2, a, $) ⊢ (q2, ε, a$) ⊢ (q3, ε, a$) ⊢ (q4, ε, a$) accept!
in fact every string is accepted: push everything, guess the middle at the end,
jump to q4. checker: 1984 wrong answers among 2047 strings (all but the 63 even
palindromes of length ≤ 10); shortest counterexamples a, b, ab, ba
fix: q3 -> q4 : ε, $ -> ε checker after the fix: 0 mismatches
এই ভুল AI-এর বানানো PDA-তে প্রায়ই দেখা যায়: “মাঝখান অনুমান, তারপর মেলানো” অংশ ঠিক থাকে, কিন্তু শেষে stack খালি হলো কি না পরীক্ষা থাকে না। ছোট string-এ brute force চালালে প্রথম string “a”-তেই ধরা পড়ে।
from itertools import product
def accepts(P, F, w, trace=False): # P: list of (state, read, pop, push, next); "" means eps; stack top on the LEFT
start = ("q1", 0, ""); prev = {start: None}; todo = [start]
while todo:
q, i, st = c = todo.pop(0)
if i == len(w) and q in F:
path = []
while c: path.append(f"({c[0]}, {w[c[1]:] or 'ε'}, {c[2] or 'ε'})"); c = prev[c]
if trace: print(trace, " ⊢ ".join(reversed(path)))
return True
for (p, a, x, y, r) in P:
if p == q and (a == "" or w[i:i + 1] == a) and st.startswith(x):
nxt = (r, i + len(a), y + st[len(x):])
if len(nxt[2]) <= len(w) + 2 and nxt not in prev: prev[nxt] = c; todo.append(nxt)
return False
W = ["".join(t) for k in range(11) for t in product("ab", repeat=k)]
P1 = [("q1","","","$","q2"), ("q2","a","","xx","q2"), ("q2","b","x","","q3"), ("q3","b","x","","q3"),
("q3","","$","","q4"), ("q2","","$","","q4")]
P2 = [("q1","","","$","q2")] + [("q2",a,x,y,"q2") for a, o in ("ab", "ba") for x, y in
(("$", a + "$"), (a, a + a), (o, ""))] + [("q2","","$","","q3")]
P3 = [("q1","","","$","q2"), ("q2","a","","a","q2"), ("q2","b","","b","q2"), ("q2","","","","q3"),
("q3","a","a","","q3"), ("q3","b","b","","q3"), ("q3","","","","q4")] # last move: BUG
tests = [("7.1 a^n b^2n", P1, {"q4"}, lambda w: w == "a" * (len(w) // 3) + "b" * (2 * len(w) // 3)),
("7.2 #a = #b ", P2, {"q3"}, lambda w: w.count("a") == w.count("b")),
("7.3 ww^R ? ", P3, {"q4"}, lambda w: len(w) % 2 == 0 and w == w[::-1]),
("7.3 fixed ", P3[:-1] + [("q3","","$","","q4")], {"q4"}, lambda w: len(w) % 2 == 0 and w == w[::-1])]
for name, P, F, pred in tests:
bad = [w for w in W if accepts(P, F, w) != pred(w)]
print(f"{name}: {len(W)} strings, {len(bad)} mismatches, shortest: {bad[:4]}")
accepts(P1, {"q4"}, "aabbbb", "7.1 aabbbb:"); accepts(P2, {"q3"}, "abba", "7.2 abba:")Simulator nondeterministic PDA-র configuration-গুলো BFS-এ ঘোরে, stack-এর উচ্চতা input-এর দৈর্ঘ্য + ২-এ বেঁধে (এই দুই যন্ত্রের গৃহীত string-এর জন্য তা যথেষ্ট)। ৭.১ আর ৭.২-এ দৈর্ঘ্য ১০ পর্যন্ত 0 mismatches; ভুল PDA-তে 1984 mismatches, সবচেয়ে ছোট ['a', 'b', 'ab', 'ba']; ঠিক করার পর আবার 0. শেষ দুই লাইনের configuration ধারা উত্তরের সঙ্গে হুবহু মেলে, যেমন (q2, bbbb, xxxx$) ⊢ (q3, bbb, xxx$).
৮ · Turing machine নকশা, trace আর ধাপ গোনা
TM M = (Q, Σ, Γ, δ, q0, qaccept, qreject), δ(q, a) = (r, b, L/R). Configuration u q v: tape-এ uv, head v-এর প্রথম চিহ্নে। নকশার কৌশল: crossing off (X, Y দিয়ে দাগানো), zig-zag, প্রথম ঘর চিহ্নিত করা (বাঁ প্রান্তের ফাঁদ এড়াতে), না লেখা নিয়ম = implicit reject.
৮.১(মাঝারি) {0n1n : n ≥ 0}-এর crossing-off TM নকশা করুন (Γ = {0, 1, X, Y, ␣})। (ক) Transition table দিন। (খ) “0011”-এর configuration ধারা লিখুন। (গ) 0n1n-এ মোট কয় ধাপ? (ঝালিয়ে নিন: পর্ব ৪৩, ৪৪)
(a) q0: 0 -> X, R, q1 ; Y -> Y, R, q3 ; ␣ -> ␣, R, acc
q1: 0 -> 0, R ; Y -> Y, R ; 1 -> Y, L, q2 (find the first unmarked 1)
q2: 0 -> 0, L ; Y -> Y, L ; X -> X, R, q0 (back to the leftmost 0)
q3: Y -> Y, R ; ␣ -> ␣, R, acc (only Y's may remain)
every rule not listed: reject
(b) q0 0011 ⊢ X q1 011 ⊢ X0 q1 11 ⊢ X q2 0Y1 ⊢ q2 X0Y1 ⊢ X q0 0Y1 ⊢ XX q1 Y1
⊢ XXY q1 1 ⊢ XX q2 YY ⊢ X q2 XYY ⊢ XX q0 YY ⊢ XXY q3 Y ⊢ XXYY q3 ␣ ⊢ accept
13 steps
(c) one round = 1 (cross 0) + (n-1) right + 1 (cross 1) + (n-1) left + 1 (step off X)
= 2n + 1 ; n rounds = 2n² + n
final check: 1 (q0 reads Y) + (n-1) Y's + 1 (blank) = n + 1
total = 2n² + 2n + 1 (n = 1..5: 5, 13, 25, 41, 61, as the checker counts)
Rejection-এর পথগুলোও দেখুন: “011”-এ q3 একটি 1 দেখে, নিয়ম নেই, reject; “001”-এ দ্বিতীয় রাউন্ডে q1 ␣-এ পৌঁছায়, reject; “10”-এ q0 প্রথমেই 1 পড়ে, reject. প্রতি রাউন্ডে head প্রায় 2n ঘর হাঁটে বলেই এই যন্ত্রের সময় O(n2). এক tape-এই “প্রতি রাউন্ডে অর্ধেক কাটা” কৌশলে O(n log n) সম্ভব, আর দুই-tape যন্ত্রে O(n) (পর্ব ৫৭, পর্ব ৪৫)।
৮.২(মাঝারি) বাজারঘরে tape-এ দুটি অর্ডার-ID # দিয়ে আলাদা, প্রশ্ন: দুটি এক কি না, অর্থাৎ {w#w : w ∈ {0, 1}∗}. যন্ত্র (Sipser-এর M1-এর রূপ, শুরু q1): q1: 0 → x, R, q2; 1 → x, R, q3; # → R, q8. q2: 0, 1 → R; # → R, q4. q3: 0, 1 → R; # → R, q5. q4: x → R; 0 → x, L, q6. q5: x → R; 1 → x, L, q6. q6: 0, 1, x → L; # → L, q7. q7: 0, 1 → L; x → R, q1. q8: x → R; ␣ → R, accept. (ক) “01#01”-এ কয় ধাপে accept? (খ) “10#11” কোথায়, কয় ধাপে reject হয়? (ঝালিয়ে নিন: পর্ব ৪৩)
(a) 01#01 : accept after 18 steps, final tape xx#xx
(b) 10#11 : q1 10#11 ⊢ x q3 0#11 ⊢ x0 q3 #11 ⊢ x0# q5 11 ⊢ x0 q6 #x1 ⊢ x q7 0#x1
⊢ q7 x0#x1 ⊢ x q1 0#x1 ⊢ xx q2 #x1 ⊢ xx# q4 x1 ⊢ xx#x q4 1
q4 is looking for a 0 but reads 1: no rule -> reject at step 11
checker: 0 mismatches on all 3280 strings over {0, 1, #} of length ≤ 7
(খ)-তে প্রথম চিহ্ন মিলেছে (1 আর 1), দ্বিতীয়টিতে বাঁয়ে 0 আর ডানে 1. যন্ত্রটি বাঁয়ের চিহ্নটি state-এ “মনে রাখে”: q2 আর q4 মানে 0, q3 আর q5 মানে 1. Tape-এ লেখার দরকার নেই, কারণ একটি চিহ্ন মনে রাখতে সসীম state-ই যথেষ্ট।
৮.৩(কঠিন) Binary decrement-এর TM নকশা করুন: tape-এ binary w (বড় বিট বাঁয়ে, সব শূন্য নয়); যন্ত্র একই দৈর্ঘ্যে w − 1 লিখে accept করবে, আর w-এর সব বিট 0 হলে reject. বাঁ প্রান্তের ফাঁদ কীভাবে এড়াবেন? “100”-এর trace দিন। (ঝালিয়ে নিন: পর্ব ৪৪)
idea: mark the first cell (0 -> O, 1 -> I), go to the end, borrow leftwards
q0: 0 -> O, R, q1 ; 1 -> I, R, q1 (mark the first cell)
q1: 0, 1 -> R ; ␣ -> ␣, L, q2 (go to the last bit)
q2: 0 -> 1, L ; 1 -> 0, L, q3 ; I -> 0, R, acc (borrow; O here: reject)
q3: 0, 1 -> L ; O -> 0, R, acc ; I -> 1, R, acc (go back, unmark)
Γ = {0, 1, O, I, ␣}
100: q0 100 ⊢ I q1 00 ⊢ I0 q1 0 ⊢ I00 q1 ␣ ⊢ I0 q2 0 ⊢ I q2 01 ⊢ q2 I11 ⊢ 0 acc 11
7 steps, tape 011 (4 - 1 = 3)
checker: all 2046 binary strings of length 1..10 give w - 1 (same length) or reject on 0…0
পর্ব ৪৪-এর increment যন্ত্রের মতোই চিহ্নিত প্রথম ঘর এখানে দুই কাজে লাগে: borrow যখন প্রথম ঘরে পৌঁছায় (I থেকে 0), তখন যন্ত্র জানে যে আর বাঁয়ে যাওয়ার নেই; আর q2 যদি O পায়, তার মানে সব বিট 0 ছিল, তাই reject. চিহ্ন ছাড়া q2 প্রথম ঘরে L চাইলে Sipser-এর রীতিতে head নড়ে না, আর যন্ত্র তা টেরও পায় না।
from itertools import product
def tm(d, w, q="q0", show=False, cap=10_000): # d[(q, sym)] = (q', write, L/R); missing rule = reject; '_' = blank
t, h, steps = list(w) or ["_"], 0, 0
while q not in ("acc", "rej") and steps < cap:
if show: print(f" {''.join(t[:h])} {q} {''.join(t[h:]).rstrip('_') or '_'}")
q, t[h], mv = d.get((q, t[h]), ("rej", t[h], "-"))
h = max(0, h - 1) if mv == "L" else h + (mv == "R") # L on cell 0 stays put
if h == len(t): t.append("_")
steps += 1
if show: print(f" {''.join(t[:h])} {q} {''.join(t[h:]).rstrip('_') or '_'}")
return q, "".join(t).strip("_"), steps
def rules(spec): return {(q, s): (r, w or s, m) for q, s, r, w, m in (x.split() for x in spec.split(";"))}
Z = rules("q0 0 q1 X R;q0 Y q3 Y R;q0 _ acc _ R;q1 0 q1 0 R;q1 Y q1 Y R;q1 1 q2 Y L;"
"q2 0 q2 0 L;q2 Y q2 Y L;q2 X q0 X R;q3 Y q3 Y R;q3 _ acc _ R")
DEC = rules("q0 0 q1 O R;q0 1 q1 I R;q1 0 q1 0 R;q1 1 q1 1 R;q1 _ q2 _ L;q2 0 q2 1 L;q2 1 q3 0 L;"
"q2 I acc 0 R;q3 0 q3 0 L;q3 1 q3 1 L;q3 O acc 0 R;q3 I acc 1 R")
M1 = rules("q1 0 q2 x R;q1 1 q3 x R;q1 # q8 # R;q2 0 q2 0 R;q2 1 q2 1 R;q2 # q4 # R;q3 0 q3 0 R;q3 1 q3 1 R;"
"q3 # q5 # R;q4 x q4 x R;q4 0 q6 x L;q5 x q5 x R;q5 1 q6 x L;q6 0 q6 0 L;q6 1 q6 1 L;q6 x q6 x L;"
"q6 # q7 # L;q7 0 q7 0 L;q7 1 q7 1 L;q7 x q1 x R;q8 x q8 x R;q8 _ acc _ R")
W = lambda S, n: ["".join(p) for k in range(n + 1) for p in product(S, repeat=k)]
print("8.1 0^n1^n mismatches:", [w for w in W("01", 10) if (tm(Z, w)[0] == "acc") != (w == "0" * (len(w) // 2) + "1" * (len(w) // 2))])
print(" steps for n = 1..5:", [tm(Z, "0" * n + "1" * n)[2] for n in range(1, 6)], "| trace of 0011:"); tm(Z, "0011", show=True)
print("8.2 w#w mismatches:", [w for w in W("01#", 7) if (tm(M1, w, "q1")[0] == "acc") != (w.count("#") == 1 and w.split("#")[0] == w.split("#")[1])])
print(" 01#01 ->", tm(M1, "01#01", "q1"), "| 10#11 ->", tm(M1, "10#11", "q1"))
bad = [w for w in W("01", 10) if w and (tm(DEC, w)[:2] != (("acc", format(int(w, 2) - 1, f"0{len(w)}b")) if int(w, 2) else ("rej",) + tm(DEC, w)[1:2]))]
print("8.3 decrement mismatches:", bad, "| trace of 100:"); print(" ", tm(DEC, "100", show=True))৮.১: দৈর্ঘ্য ১০ পর্যন্ত সব binary string-এ অমিল [], ধাপ [5, 13, 25, 41, 61], যা 2n2 + 2n + 1-এর মান; তারপর “0011”-এর ১৪টি configuration, শেষটি XXYY_ acc _ (␣ ছাপা হয় _)। ৮.২: {0, 1, #}-এর ওপর দৈর্ঘ্য ৭ পর্যন্ত অমিল নেই; ('acc', 'xx#xx', 18) আর ('rej', 'xx#x1', 11). ৮.৩: decrement-এ অমিল [], আর “100”-এর trace শেষ হয় ('acc', '011', 7)-এ।
৯ · Mealy/Moore আর মিশ্র “নকশা করুন, যাচাই করুন”
ঝালিয়ে নিন: পর্ব ১২ · Mealy আর Moore, পর্ব ১৬ · Closure property, পর্ব ১৭ · Pumping lemma, পর্ব ৩৬ · CFL-এর pumping lemma.
৯.১(মাঝারি) বাজারঘরের সেন্সর-লাইনে প্যাটার্ন “0110” এলেই একটি বাতি জ্বলবে (ওভারল্যাপ চলবে)। (ক) Mealy machine দিন। (খ) সমতুল্য Moore machine-এ কয়টি state? (গ) Input 0110110-এর output কী? (ঝালিয়ে নিন: পর্ব ১২)
(a) Mealy, state = longest prefix of 0110 seen at the end:
input 0 input 1
s0 s1 / 0 s0 / 0
s1 s1 / 0 s2 / 0 s1 = "0"
s2 s1 / 0 s3 / 0 s2 = "01"
s3 s1 / 1 s0 / 0 s3 = "011" ; 0 completes 0110, keeps "0"
(b) Moore: s0..s3 with output 0, plus s4 = "0110 just seen" with output 1;
s3 --0--> s4 ; s4 behaves like s1: 0 -> s1, 1 -> s2 -> 5 states
(c) 0110110 -> 0001001 (the second 0110 reuses the last 0 of the first)
Mealy-তে output তীরের গায়ে, তাই “0 পড়ে s3 থেকে” ঘটনাটিই output 1. Moore-এ output state-এর গায়ে, তাই সেই ঘটনার জন্য আলাদা state s4 লাগে; Mealy থেকে Moore-এ যেতে সাধারণত এভাবেই state বাড়ে। (গ)-তে ওভারল্যাপ: চতুর্থ চিহ্নে প্রথম 0110 শেষ, আর তার শেষ 0 থেকেই দ্বিতীয়টি শুরু, যা সপ্তম চিহ্নে শেষ।
৯.২(কঠিন) Σ = {a, b}-এর চারটি language শ্রেণি অনুযায়ী সাজান (regular / context-free কিন্তু regular নয় / context-free নয়), প্রতিটির জন্য যন্ত্র বা grammar আর প্রমাণের হাতিয়ার বলুন: LA = {w : #a − #b ≡ 0 (mod 3)}; LB = {w : #a = #b}; LC = {w : w-এর প্রতিটি prefix-এ 0 ≤ #a − #b ≤ 2}; LD = {anbncn : n ≥ 0} (এখানে Σ = {a, b, c})। (ঝালিয়ে নিন: পর্ব ১৬, ১৭, ৩৬, ৪৩)
L_A : regular. 3-state DFA of 4.3 ; regex (ba ∪ (a ∪ bb)(ab)*(b ∪ aa))*
L_B : context-free, NOT regular. Grammar of 5.2 or PDA of 7.2.
not regular: L_B ∩ a*b* = {a^n b^n}, which is not regular (lesson 17);
regular languages are closed under ∩, so L_B cannot be regular.
L_C : regular! The difference never leaves 0..2, so a counter with 3 values
is enough: d0 (start) -a-> d1 -a-> d2 ; d2 -b-> d1 -b-> d0 ;
a at d2 or b at d0 -> dead. F = {d0, d1, d2}. 4 states with dead.
L_D : not context-free (CFL pumping lemma, lesson 36) ; decidable:
a crossing-off TM like 8.1, one a, one b and one c per round.
LC-ই ফাঁদ: দেখতে “গোনা”-র মতো, তাই অনেকে PDA লেখেন। কিন্তু গণনা একটি সসীম সীমার ভেতরে বাঁধা, তাই সসীম memory যথেষ্ট। নিয়মটি মনে রাখুন: অসীম গণনা লাগলে তবেই regular-এর বাইরে। LB-এর জন্য সরাসরি pumping-ও চলে (s = apbp), তবে closure-এর এক লাইনের যুক্তি দ্রুত; পূর্ণ প্রমাণ লেখার অনুশীলন পর্ব ৮৪-এর কাজ।
৯.৩(মাঝারি) ভুলটি খুঁজুন: একটি AI সহকারী বলল, “binary সংখ্যা ৪ দিয়ে বিভাজ্য ⇔ শেষ দুটি বিট 00”, আর তিন state-এর একটি DFA দিল যা শুধু 00 দিয়ে শেষ হওয়া string গ্রহণ করে। (val(ε) = 0 ধরে) যন্ত্রটি কোন string-এ ভুল? কীভাবে ঠিক করবেন, আর minimal DFA-তে কয়টি state? (ঝালিয়ে নিন: পর্ব ০৮, ১৯)
wrong on: ε and "0" (value 0 is divisible by 4, but they do not end in 00)
the claim is true only for strings of length ≥ 2
fix: use the mod-4 DFA δ(r, b) = (2r + b) mod 4 , F = {r0}
r1 and r3 have the same row (0 -> r2, 1 -> r3) and are both rejecting
-> merge them: minimal DFA has 3 states
r0 (accept, start) -0-> r0, -1-> r13 ; r13 -0-> r2, -1-> r13 ; r2 -0-> r0, -1-> r13
AI-এর উক্তি “প্রায়” ঠিক, আর এখানেই বিপদ: ভুল শুধু প্রান্তের দুটি string-এ, যা হাতে বাছা উদাহরণে চোখ এড়ায়। চেকার দৈর্ঘ্য ০ থেকে শুরু করে বলে প্রথম দুটি string-এই ধরে ফেলে। এই ধরনের off-by-one আর ε-ভুল নিয়ে আরও কথা নিচের AI অংশে।
from itertools import product
W = lambda S, n: ["".join(p) for k in range(n + 1) for p in product(S, repeat=k)]
# 9.1 detector for 0110 (overlap allowed). Mealy: (state, bit) -> (next, output)
ME = {(0,"0"): (1,"0"), (0,"1"): (0,"0"), (1,"0"): (1,"0"), (1,"1"): (2,"0"),
(2,"0"): (1,"0"), (2,"1"): (3,"0"), (3,"0"): (1,"1"), (3,"1"): (0,"0")}
MO = {(q, b): ME[(q, b)][0] for q in range(4) for b in "01"} | {(3, "0"): 4, (4, "0"): 1, (4, "1"): 2}
out = {0: "0", 1: "0", 2: "0", 3: "0", 4: "1"} # Moore: output written on the state
def mealy(w, q=0, s=""):
for b in w: q, o = ME[(q, b)]; s += o
return s
def moore(w, q=0, s=""): # initial output dropped, as agreed
for b in w: q = MO[(q, b)]; s += out[q]
return s
ref = lambda w: "".join("1" if w[:i + 1].endswith("0110") else "0" for i in range(len(w)))
I = W("01", 12)
print("9.1 Mealy == reference:", all(mealy(w) == ref(w) for w in I), "| Moore == Mealy:", all(moore(w) == mealy(w) for w in I),
f"| {len(I)} inputs | 0110110 ->", mealy("0110110"))
def run(d, q, w):
for c in w: q = d[(q, c)]
return q
# 9.2 every prefix has 0 <= #a - #b <= 2 (counter 0..2, then dead)
D = {(q, c): (q + (1 if c == "a" else -1) if q != "x" and 0 <= q + (1 if c == "a" else -1) <= 2 else "x") for q in (0, 1, 2, "x") for c in "ab"}
ok = lambda w: all(0 <= w[:i].count("a") - w[:i].count("b") <= 2 for i in range(len(w) + 1))
print("9.2 mismatches up to length 12:", [w for w in W("ab", 12) if (run(D, 0, w) != "x") != ok(w)])
# 9.3 a claimed DFA for 'binary value divisible by 4' that accepts exactly the strings ending in 00
AI = {(q, b): (q + 1 if b == "0" and q < 2 else 2 if b == "0" else 0) for q in range(3) for b in "01"}
print("9.3 AI's DFA wrong on:", [w for w in W("01", 10) if (run(AI, 0, w) == 2) != (int(w or "0", 2) % 4 == 0)][:4])
FIX = {(r, b): (2 * r + int(b)) % 4 for r in range(4) for b in "01"}
print(" mod-4 DFA wrong on:", [w for w in W("01", 10) if (run(FIX, 0, w) == 0) != (int(w or "0", 2) % 4 == 0)],
"| states 1 and 3 have equal rows:", [FIX[(1, b)] for b in "01"] == [FIX[(3, b)] for b in "01"])প্রথম লাইন: দৈর্ঘ্য ১২ পর্যন্ত 8191টি input-এ Mealy যন্ত্র সংজ্ঞার সঙ্গে আর Moore যন্ত্র Mealy-র সঙ্গে (শুরুর output বাদ দিয়ে) মেলে: দুটিই True; 0110110 -> 0001001. LC-এর চার state-এর DFA-তে দৈর্ঘ্য ১২ পর্যন্ত অমিল []. AI-এর DFA ভুল ঠিক ['', '0']-এ, আর mod-4 যন্ত্রে অমিল নেই; states 1 and 3 have equal rows: True দেখায় কেন দুটি state একত্র করে ৩টি state থাকে।
৯.৪(কঠিন) বাজারঘরের একটি coupon-নিয়মে দুটি শর্ত একসঙ্গে: Σ = {a, b}-এর string-এ a-এর সংখ্যা ৩ দিয়ে বিভাজ্য, আর কোথাও “bb” নেই। (ক) দুই শর্তের আলাদা DFA বানিয়ে product construction-এ কয়টি state আসে? (খ) Minimal DFA-তে কয়টি state, আর কোন state-গুলো এক হয়? (গ) সাধারণভাবে m আর n state-এর দুই DFA-র ∩-এর জন্য কোন সীমা মনে রাখবেন? (ঝালিয়ে নিন: পর্ব ০৮, ১৯)
M1 (a mod 3): states 0, 1, 2 ; F1 = {0}
M2 (no "bb") : n0 = last symbol is not b (start), n1 = last symbol is b, x = dead
n0 -a-> n0, n0 -b-> n1, n1 -a-> n0, n1 -b-> x, x loops
(a) product: 3 × 3 = 9 states, all reachable ; F = {(0, n0), (0, n1)}
(b) (0, x), (1, x), (2, x) never accept again -> one dead state
the other 6 are pairwise distinguishable -> minimal DFA: 6 + 1 = 7 states
(c) product of complete DFAs: at most m·n states ; the minimal one can be smaller
checker: 0 mismatches up to length 12 ; product 9 states, minimal 7
Product construction যান্ত্রিকভাবে ঠিক উত্তর দেয়, কিন্তু সবসময় সবচেয়ে ছোট নয়: একটি উপাদান dead হলে অন্য উপাদানের মান আর গুরুত্বপূর্ণ নয়, তাই সেই state-গুলো এক হয়ে যায়। পরীক্ষায় “minimal DFA” চাইলে product-এর পর এই একত্রীকরণ দেখাতে হবে; শুধু “৯টি state” লিখলে নম্বর কাটা যায়।
৯.৫(মাঝারি) বাজারঘরের order-query-তে দুই রকম বন্ধনী ( ) আর [ ] চলে, আর সেগুলো ঠিকভাবে বাসা বাঁধতে হবে, যেমন “([])()” বৈধ, “([)]” অবৈধ। (ক) একটি unambiguous CFG দিন। (খ) S → SS ∣ (S) ∣ [S] ∣ ε কেন খারাপ পছন্দ? (গ) এই language কি regular? (ঝালিয়ে নিন: পর্ব ২৫, ২৭, ৩২)
(a) S -> ( S ) S ∣ [ S ] S ∣ ε
the first symbol of a non-empty string opens a bracket; its matching closer
is forced, so the split "( inside ) rest" is unique -> one tree per string
(b) S -> SS with S -> ε: S ⇒ SS ⇒ S, so every string has INFINITELY many trees;
even without ε, "()()()" has 2 trees (grouping of SS)
(c) no: its intersection with the regular language {(^i )^j : i, j ≥ 0}
is {(^n )^n}, which is not regular (closure argument, as in 9.2)
checker: all 87381 strings over ( ) [ ] of length ≤ 8: 0 mismatches against a
stack check, 1 tree each ; 224 balanced strings of length 8 (= 14 · 2^4)
(ক)-র grammar আসলে Dyck language-এর দুই-বন্ধনী রূপ, আর এর PDA স্বাভাবিক: খোলা বন্ধনী stack-এ রাখুন, বন্ধ বন্ধনী এলে ওপরের চিহ্ন একই ধরনের হলে তুলুন, নইলে আটকে যান। দৈর্ঘ্য ৮-এর ২২৪টি বৈধ string-এর হিসাব: বন্ধনীর আকার Catalan C4 = ১৪ রকম, আর চার জোড়ার প্রতিটি গোল বা চৌকো, তাই ১৪ × ১৬.
from itertools import product
from functools import lru_cache, reduce
W = lambda S, n: ["".join(p) for k in range(n + 1) for p in product(S, repeat=k)]
# 9.4: (#a divisible by 3) AND (no "bb"); no-bb part: n0 = last symbol not b, n1 = last symbol b, x = dead
nb = {("n0","a"): "n0", ("n0","b"): "n1", ("n1","a"): "n0", ("n1","b"): "x", ("x","a"): "x", ("x","b"): "x"}
d = {((i, s), c): ((i + (c == "a")) % 3, nb[(s, c)]) for i in range(3) for s in ("n0", "n1", "x") for c in "ab"}
F = {(0, "n0"), (0, "n1")}; start = (0, "n0")
run = lambda q, w: reduce(lambda q, c: d[(q, c)], w, q)
print("9.4 mismatches up to length 12:", [w for w in W("ab", 12) if (run(start, w) in F) != (w.count("a") % 3 == 0 and "bb" not in w)])
part = {q: q in F for q in {k[0] for k in d}}
while True:
new = {q: (part[q], part[d[(q, "a")]], part[d[(q, "b")]]) for q in part}
if len(set(new.values())) == len(set(part.values())): break
part = new
print(" product states:", len(part), "| minimal:", len(set(part.values())))
def balanced(w): # 9.5: two kinds of brackets, S -> (S)S | [S]S | eps
st = []
for c in w:
if c in "([": st.append(c)
elif not st or st.pop() != {")": "(", "]": "["}[c]: return False
return not st
def trees(w):
@lru_cache(None)
def S(i, j): # parse trees of w[i:j] from S
return int(i == j) + sum(S(i + 1, m) * S(m + 1, j) for m in range(i + 1, j)
if w[i] + w[m] in ("()", "[]"))
return S(0, len(w))
T = {w: trees(w) for w in W("()[]", 8)}
print("9.5 strings:", len(T), "| mismatches:", sum((T[w] > 0) != balanced(w) for w in T), "| max trees:", max(T.values()),
"| balanced of length 8:", sum(balanced(w) for w in T if len(w) == 8))৯.৪: দৈর্ঘ্য ১২ পর্যন্ত অমিল [], product-এ 9টি state, Moore refinement-এর পর minimal: 7. ৯.৫: ৪টি চিহ্নের ওপর দৈর্ঘ্য ৮ পর্যন্ত 87381টি string, stack দিয়ে করা সোজা পরীক্ষার সঙ্গে mismatches: 0, প্রতিটি বৈধ string-এর ঠিক একটি গাছ (max trees: 1), আর দৈর্ঘ্য ৮-এ বৈধ string 224টি।
৯.৬(সহজ থেকে মাঝারি) ছয়টি দ্রুত নকশা, Σ = {a, b} (শেষেরটিতে {0, 1}): প্রতিটির minimal সম্পূর্ণ DFA-তে কয়টি state, আর প্রতিটি state-এর অর্থ কী? (ক) অন্তত দুটি a; (খ) ঠিক দুটি a; (গ) “ab” substring আছে; (ঘ) “ab” দিয়ে শেষ; (ঙ) দৈর্ঘ্য ৩-এর গুণিতক আর শেষ চিহ্ন a; (চ) binary মান ৩ দিয়ে বিভাজ্য আর দৈর্ঘ্য জোড়। বোনাস: দৈর্ঘ্য ৮-এর কয়টি string-এ “bb” নেই? (ঝালিয়ে নিন: পর্ব ০৮, ১৮)
(a) 3 : 0 a, 1 a, ≥ 2 a (accept, absorbing)
(b) 4 : 0, 1, 2 (accept), ≥ 3 (dead)
(c) 3 : nothing, last is a, "ab" seen (absorbing)
(d) 3 : last is not a and not "ab", last is a, ends in "ab" (accept)
(e) 4 : length ≡ 0 and last a (accept) ; length ≡ 0, last not a (start) ;
length ≡ 1 ; length ≡ 2 (when length ≢ 0, the last symbol does not matter)
(f) 6 : (value mod 3) × (length mod 2) ; accept (0, even)
bonus: 55 strings (a Fibonacci number: f(n) = f(n-1) + f(n-2), f(1) = 2, f(2) = 3)
scratch check: Myhill–Nerode classes of all prefixes up to length 7, separated by
all suffixes up to length 7, give exactly these counts; the DFAs above reach them
(ঙ)-র উত্তর অনেকে ৬ লেখেন (৩ × ২), কিন্তু দৈর্ঘ্য ৩-এর গুণিতক না হলে শেষ চিহ্ন কোনো ভূমিকা রাখে না: পরে আরও চিহ্ন আসবে, আর শেষ চিহ্ন তখন বদলে যাবে। তাই দুটি জোড়া করে state এক হয়। (চ)-তে তা হয় না, কারণ দুটি গণনাই শেষ পর্যন্ত লাগে। বোনাস প্রশ্নটি ২.২-এর গোনার মতো: শেষ চিহ্ন a হলে আগের অংশ যেকোনো বৈধ string, b হলে তার আগে a থাকতেই হবে।
আরও গভীরে: ৯.৪-এর m · n সীমা ∩-এর জন্য আঁটসাঁট: কিছু language-জোড়ায় minimal DFA-তে সত্যিই m · n state লাগে, আর এই ধরনের প্রশ্ন “state complexity” নামের গবেষণার বিষয়। বিপরীতে NFA-র complement-এ 2n-এর কাছাকাছি state লাগতে পারে, যা ৩.৩-এর বিস্ফোরণেরই আরেক রূপ। আর ৫.২ বা ৯.৫-এর মতো grammar আসলে unambiguous কি না, তা সাধারণভাবে কোনো algorithm দিয়ে ঠিক করা যায় না (পর্ব ২৭, ৫৪); তাই এই পাতার “একটি গাছ” পরীক্ষা শুধু নির্দিষ্ট দৈর্ঘ্য পর্যন্ত যাচাই; সাধারণ প্রমাণ আসে হাতের যুক্তি থেকে।
পরীক্ষা ও ইন্টারভিউতে: “DFA-তে কয়টি state?” প্রশ্নে dead state গোনা হবে কি না নিজে লিখে দিন। “NFA দিন” বললে ছোট NFA-ই প্রত্যাশিত, DFA দিলেও চলে কিন্তু সময় নষ্ট। “Grammar দিন” প্রশ্নে unambiguous grammar দিলে বাড়তি নম্বর মেলে, বিশেষ করে query বা expression-এর grammar-এ। Turing machine-এর প্রশ্নে পূর্ণ table না চাইলে implementation-level বর্ণনা (কোন চিহ্ন দাগাবেন, কোন দিকে হাঁটবেন) যথেষ্ট। আর প্রতিটি নকশার শেষে দুটি ছোট পরীক্ষা লিখুন: একটি গৃহীত, একটি বর্জিত string.
শেষ মুহূর্তের নিয়ম-তালিকা আর সাধারণ ভুল
পরীক্ষার আগের রাতে এই এক টেবিলই যথেষ্ট; তৃতীয় কলামের ভুলগুলো মনে রাখাই বেশি কাজের।
| বিষয় | নিয়ম | সাধারণ ভুল | পর্ব |
|---|---|---|---|
| DFA নকশা | state-এর অর্থ; δ সম্পূর্ণ | ε-এর state ভুল; dead state বাদ; গণনায় এক কম বা বেশি | ০৭, ০৮ |
| Product | ∩: F1 × F2; ∪: যেকোনো একটি | ∪-এ কিছু accepting state বাদ | ০৮ |
| Complement | সম্পূর্ণ DFA-তে F উল্টানো | partial DFA বা NFA-তে F উল্টানো | ০৮, ১৬ |
| Subset construction | শুধু নাগালের উপসেট; ∅ = dead | সব 2n উপসেট লেখা; accepting চিহ্ন ভুল | ১০ |
| ε-NFA | δ′ = E(δ(E(q), a)); F′-এ closure | শুরুর closure বাদ; F′ না বাড়ানো | ১১ |
| Minimization | নাগাল আগে, তারপর table-filling | unreachable state রেখে দেওয়া | ১৯ |
| State elimination | R1R2∗R3 ∪ R4 | পুরোনো সরাসরি তীর (R4) ভুলে যাওয়া | ১৫ |
| CFG নকশা | বাসা, ভাগ, মিলন; দুই দিকের যুক্তি | ঠিক language কিন্তু ambiguous grammar | ২৫, ২৭ |
| CNF | S0, ε, unit, লম্বা, terminal | ε দূর করার পর বিকল্প (“ac”) যোগ না করা | ২৮, ২৯ |
| CYK | T[i, l], সব ভাগ k | কোনো একটি ভাগ বাদ দেওয়া | ৩১ |
| PDA | $ দিয়ে শুরু, “ε, $ → ε” দিয়ে শেষ | শেষে খালি stack পরীক্ষা না করা | ৩২, ৩৩ |
| Turing machine | crossing off; প্রথম ঘর চিহ্নিত | বাঁ প্রান্তে L; ␣-এর নিয়ম ভুলে যাওয়া | ৪৩, ৪৪ |
| Mealy/Moore | Moore-এ output-এর জন্য বাড়তি state | ওভারল্যাপে ফেরার state ভুল | ১২ |
২০ মিনিটের মিনি-সেট — ঘড়ি ধরে করুন
আটটি ছোট প্রশ্ন, প্রতিটিতে আড়াই মিনিট। কাগজ-কলম চলবে, চেকার নয়। ৭–৮ ঠিক হলে প্রস্তুত, ৫–৬ হলে সংশ্লিষ্ট ভাগ আবার, ৪-এর কম হলে ভাগ ২ থেকে আবার শুরু করুন।
- Binary-তে ৪ দিয়ে বিভাজ্যতার (val(ε) = 0) minimal DFA-তে কয়টি state?
- “শেষ থেকে চতুর্থ চিহ্ন 1”-এর NFA থেকে subset construction-এ কয়টি নাগালের উপসেট?
- {a, b}-এর দৈর্ঘ্য ৪-এর কয়টি string-এ “ab” substring আছে?
- CNF grammar-এ দৈর্ঘ্য ৬-এর একটি string-এর derivation-এ কয় ধাপ?
- দৈর্ঘ্য ৫-এর string-এ CYK টেবিলে মোট কয়টি ঘর?
- ৮.১-এর 0n1n যন্ত্র “000111”-এ কয় ধাপে accept করে?
- “0110” detector-এর সমতুল্য Moore machine-এ কয়টি state?
- {aibj : i ≤ j} কি regular? এক লাইনে কারণ বলুন।
উত্তরমিনি-সেটের উত্তর আর এক লাইনের কারণ (নিজে করার পরে খুলুন)
1. 3 (mod-4 DFA, r1 and r3 merge ; 9.3)
2. 16 (2^4 ; 3.3)
3. 11 (16 - 5 strings without "ab": b^i a^(4-i), i = 0..4)
4. 11 (2n - 1 with n = 6)
5. 15 (5 + 4 + 3 + 2 + 1)
6. 25 (2n² + 2n + 1 with n = 3)
7. 5 (4 Mealy states + one output state ; 9.1)
8. No. Pumping: s = a^p b^p ; since |xy| ≤ p, y = a^k with k ≥ 1 ;
pump up (i = 2): p + k a's but p b's -> not in L. It is context-free:
S -> aSb ∣ B, B -> bB ∣ ε (5.1)
সবচেয়ে বেশি ভুল হয় ৩ আর ৬-এ। ৩-এ “ab নেই” মানে string-টি b∗a∗ আকারের, দৈর্ঘ্য ৪-এ এমন ৫টি; বাকি ১১টিতে ab আছে। ৬-এ অনেকে শুধু n2 গোনেন, অথচ প্রতি রাউন্ডে ফেরার পথ আর শেষের Y-পরীক্ষাও ধাপ।
AI-এর যুগে — AI-এর বানানো যন্ত্র আর grammar যাচাই
AI সহকারীকে “এই language-এর DFA দাও” বললে পরিষ্কার, আত্মবিশ্বাসী উত্তর আসে, অনেক সময় সুন্দর ছবিসহ। তাতে প্রায়ই এমন ভুল থাকে যা দেখে ধরা কঠিন, কিন্তু brute force-এ এক মুহূর্তে ধরা পড়ে। ভুলগুলো চেনা:
| AI-এর ভুল | উদাহরণ | কীভাবে ধরবেন |
|---|---|---|
| ε বা প্রান্তের string ভুল | ৯.৩-এর “শেষে 00” DFA | দৈর্ঘ্য ০ থেকে brute force |
| গণনায় এক কম বা বেশি | “অন্তত ৩” চাওয়ায় “ঠিক ৩”-এর যন্ত্র | সীমার এপার-ওপারের string |
| Dead state বা অসম্পূর্ণ δ | partial DFA-তে F উল্টে complement | প্রতিটি state-এ সব চিহ্নের তীর গোনা |
| ঠিক language, ভুল গঠন | ৫.১-এর ambiguous grammar | ছোট string-এ parse tree গোনা |
| শেষের পরীক্ষা বাদ | ৭.৩-এর $ ছাড়া PDA | সবচেয়ে ছোট counterexample খোঁজা |
| শর্ত ছাড়া উপপাদ্য, ভুল দিকের যুক্তি | pumping-এ split নিজে বাছা, reduction উল্টো দিকে | প্রতিটি ধাপের কারণ লেখা; পর্ব ৮৪-এর তালিকা |
| বানানো reference | না থাকা উপপাদ্য বা বইয়ের পাতা | Sipser বা Hopcroft–Motwani–Ullman-এ খোঁজা |
AI-কে উত্তরদাতা নয়, যাচাইকারী হিসেবে ব্যবহার করুন। নিচের prompt-এ প্রথমে নিজের নকশা দিন, যাতে AI পুরো উত্তর না দিয়ে আপনার ভুলের জায়গা দেখায়।
যাচাইয়ের চেকলিস্ট
নিজেকে যাচাই করুন
প্রতিটি প্রশ্নে খাতায় হিসাব করে তবে উত্তর বাছুন। সব তথ্য প্রশ্নের ভেতরেই আছে।
ক্রমDFA থেকে regex বের করার state elimination-এর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- নতুন শুরু s আর নতুন accepting f যোগ করে ε-তীর দেওয়া
- একই দুই state-এর মধ্যের একাধিক তীর ∪ দিয়ে একটি লেবেলে আনা
- একটি মাঝের state k বেছে প্রতিটি p → k → q পথে R1R2∗R3 ∪ R4 লেখা
- মাঝের সব state শেষ না হওয়া পর্যন্ত আগের ধাপ আবার করা
- s → f তীরের লেবেলটিই উত্তরের regex
(সহজ) Binary string (বড় বিট আগে, val(ε) = 0) যার মান ৬ দিয়ে বিভাজ্য, তার minimal সম্পূর্ণ DFA-তে কয়টি state?
- 6
- 4
- 3
- 2
(সহজ) “শেষ থেকে চতুর্থ চিহ্ন 1” language-এর ৫ state-এর NFA থেকে subset construction-এ কয়টি নাগালের উপসেট আসে?
- 5
- 8
- 16
- 32
(মাঝারি) Σ = {a, b}. কোন regex ঠিক সেই string বর্ণনা করে যাদের কোথাও “bb” নেই?
- (a ∪ ba)∗(ε ∪ b)
- (a ∪ ba)∗
- (a ∪ ab)∗(ε ∪ b)
- (b ∪ ab)∗(ε ∪ a)
(মাঝারি) Chomsky normal form-এর একটি grammar-এ দৈর্ঘ্য ৬-এর একটি string-এর যেকোনো derivation-এ কয়টি ধাপ?
- 6
- 5
- 12
- 11
(মাঝারি) {anb2n}-এর PDA: q1 → q2: ε, ε → $; q2 → q2: a, ε → xx; q2 → q3: b, x → ε; q3 → q3: b, x → ε; q3 → q4: ε, $ → ε. শুরু থেকে “aab” পড়ার পর stack কী (ওপর বাঁয়ে)?
- xxx$
- xxxx$
- x$
- aab$
(মাঝারি) {0n1n}-এর crossing-off TM-এ (প্রতি রাউন্ডে একটি 0 আর একটি 1 দাগানো, তারপর শেষে Y-গুলো পার হয়ে ␣) n = 3-এ মোট ধাপ 2n2 + 2n + 1. “000111”-এ কয় ধাপ?
- 19
- 25
- 27
- 41
(কঠিন) Grammar S → aSbS ∣ bSaS ∣ ε-তে “ababab”-এর কয়টি আলাদা parse tree?
- 1
- 2
- 5
- 6
(মাঝারি) “0110” (ওভারল্যাপসহ) ধরার Mealy machine-এ ৪টি state. সমতুল্য Moore machine-এ ন্যূনতম কয়টি state?
- 4
- 5
- 8
- 6
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব শব্দ এখানে একসাথে:
মনে রাখুন
- অর্থ আগে, তীর পরে: প্রতিটি state, variable বা stack-চিহ্নের অর্থ এক লাইনে লিখলে নকশা প্রায় নিজে থেকেই দাঁড়ায়, আর correctness-এর যুক্তিও সেখান থেকে আসে।
- প্রান্তের string: ε, এক চিহ্ন, সীমার এপার-ওপার। ৭.১, ৯.৩ আর ৩.২-এর ভুলগুলো এখানেই লুকিয়ে ছিল।
- ক্রম মানুন: minimization-এ নাগাল আগে; CNF-এ S0, ε, unit, তারপর আকার; state elimination-এ পুরোনো তীর ∪ দিয়ে রাখা।
- ঠিক language যথেষ্ট নয়: grammar-এ ambiguity, PDA-তে শেষের $ পরীক্ষা, TM-এ বাঁ প্রান্ত। গঠনও নম্বর পায়।
- Brute force জাল, প্রমাণ নয়: দৈর্ঘ্য ১০ পর্যন্ত মিললে ভুলের সম্ভাবনা কমে; প্রমাণ আসে invariant আর দুই দিকের যুক্তি থেকে।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্বপুরো কোর্সের মানচিত্র আর ১৪টি মডিউল।
- পর্ব ০৮ · DFA নকশাআবার পড়ুননকশার ধাঁচ আর product construction-এর প্রমাণ।
- পর্ব ৩১ · CYK algorithmআবার পড়ুনটেবিল থেকে parse tree আর জটিলতার হিসাব।
- পর্ব ৪৪ · Turing machine নকশাআবার পড়ুনIncrement, যোগ, গুণ আর ধাপ গোনার আরও উদাহরণ।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৯ · Numerical অনুশীলনপাশের ট্র্যাকগণনা, recurrence আর ছোট automaton-এর হিসাব।
- DSA · পর্ব ৬৮ · Complexity আর dry-runপাশের ট্র্যাকAlgorithm-এর হাতে-করা trace আর জটিলতার অনুশীলন।
- সফটওয়্যার টেস্টিং · পর্ব ১০ · State transition testingপাশের ট্র্যাকState machine থেকে test case বানানো।