এই পর্বে যা শিখবেন
- Grammar-কে G = (V, Σ, R, S) rewriting system হিসেবে পড়া, derivation ⇒ আর ⇒∗, আর L(G)-এর সংজ্ঞা
- চারটি type-এর নিয়মের শর্ত চেনা, একটি grammar-এর সবচেয়ে কড়া type বের করা, আর ε-নিয়মের সূক্ষ্মতা
- প্রতিটি স্তরের machine, তার স্মৃতির ধরন, আর right-linear grammar থেকে NFA বানানোর প্রমাণ
- কঠোর অন্তর্ভুক্তির শিকল, প্রতিটি ধাপের আলাদা করার উদাহরণ, আর “CSL ⊆ decidable ⊋ CSL”-এর প্রমাণ
- Closure আর decision property-র মানচিত্র, complexity class-এর অবস্থান, আর regex বনাম parser বনাম সাধারণ প্রোগ্রামের ব্যবহারিক সীমা
১ · Grammar: নিয়ম দিয়ে string লেখা
বাজারের ফর্দ লেখার কথা ভাবুন। মা বললেন, “ফর্দ মানে একটি জিনিস, তারপর আরও ফর্দ, অথবা কিছুই না।” আর “জিনিস মানে চাল, ডাল বা তেল।” এই দুটি ছোট নিয়ম দিয়ে অসীম সংখ্যক ফর্দ লেখা যায়: “চাল ডাল”, “তেল”, “ডাল ডাল চাল”… সসীম নিয়মে অসীম ভাষা, এটাই grammar-এর মূল চাল। প্রশ্ন হলো, নিয়ম কতটা স্বাধীন হলে কতটা জটিল ভাষা তৈরি হয়, আর সেই ভাষা চিনতে কেমন যন্ত্র লাগে। এই প্রশ্নের উত্তরই Chomsky hierarchy.
আগের পাঁচ পর্বে আমরা language-কে Σ∗-এর subset হিসেবে দেখেছি (পর্ব ০৩), আর সমস্যাকে language হিসেবে লিখেছি (পর্ব ০৫)। এবার দুটি দৃষ্টিভঙ্গি পাশাপাশি রাখি। একটি তৈরির দৃষ্টি: grammar নিয়ম খাটিয়ে language-এর string বানায়। অন্যটি চেনার দৃষ্টি: machine একটি string পড়ে “হ্যাঁ” বা “না” বলে। Grammar-এর প্রাথমিক পরিচয় ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৭৩-এ আছে; এখানে আমরা পুরো মানচিত্রটি আঁকব, যা এই কোর্সের বাকি ৭৯টি পর্বের পথনির্দেশ।
একটি grammar হলো G = (V, Σ, R, S), যেখানে V হলো variable-এর (nonterminal) সসীম set, Σ হলো terminal-এর alphabet (V ∩ Σ = ∅), S ∈ V হলো start symbol, আর R হলো α → β আকারের নিয়মের সসীম set, যেখানে α, β ∈ (V ∪ Σ)∗ এবং α-তে অন্তত একটি variable আছে।
u ⇒ v (“u থেকে এক ধাপে v”) মানে u = xαy আর v = xβy, কোনো নিয়ম α → β আর কোনো x, y-এর জন্য। ⇒∗ হলো ⇒-এর reflexive-transitive closure (পর্ব ০২): শূন্য বা বেশি ধাপ। তাহলে
L(G) = { w ∈ Σ∗ : S ⇒∗ w }
সহজ কথায়: S দিয়ে শুরু করুন, যেকোনো জায়গায় কোনো নিয়মের বাঁ দিক খুঁজে পেলে তাকে ডান দিক দিয়ে বদলান, আর যখন শুধু terminal বাকি থাকে, সেই string-টি L(G)-এর সদস্য। মাঝপথের string-গুলোকে বলে sentential form, আর পুরো ক্রমটি একটি derivation. এই কোর্সের রীতি: বড় হাতের অক্ষর variable, ছোট হাতের অক্ষর, অঙ্ক আর বন্ধনী terminal, আর একই বাঁ দিকের কয়েকটি নিয়ম একসঙ্গে লেখা হয় A → x | y. ফাঁকা string সবসময় ε (কিছু বই λ লেখে)।
একটি তিন নিয়মের উদাহরণ: S → aSb | ab. Derivation S ⇒ aSb ⇒ aaSbb ⇒ aaabbb দেখায় aaabbb ∈ L(G), আর L(G) = {anbn : n ≥ 1}। কোনো derivation-এ a আর b-এর সংখ্যা আলাদা হতে পারে না, কারণ প্রতিটি নিয়ম দুটি একসঙ্গে যোগ করে; এমন “প্রতিটি নিয়ম একটি ধর্ম রক্ষা করে” ধরনের যুক্তি পর্ব ০৪-এর invariant-এর প্রমাণ। পূর্ণ context-free grammar-এর তত্ত্ব শুরু হবে পর্ব ২৫-এ।
২ · চার শ্রেণির নিয়ম: Type 0 থেকে Type 3
Noam Chomsky ১৯৫৬ সালের “Three models for the description of language” প্রবন্ধে আর ১৯৫৯ সালের “On certain formal properties of grammars” প্রবন্ধে নিয়মের আকারে বাধা দিয়ে grammar-এর কয়েকটি শ্রেণি আলাদা করেন; আজকের Type 0–3 নামকরণ মূলত দ্বিতীয় প্রবন্ধ থেকে এসেছে বলে ধরা হয়। পাঠ্যবইয়ে শর্তগুলো সামান্য ভিন্নভাবে লেখা হয়; এই কোর্সের রূপটি নিচে।
ধরুন A, B ∈ V, a ∈ Σ, আর α, β ∈ (V ∪ Σ)∗.
- Type 0 (unrestricted): সংজ্ঞা ১.১-এর যেকোনো নিয়ম α → β.
- Type 1 (context-sensitive): প্রতিটি নিয়মে |α| ≤ |β| (noncontracting). একমাত্র ব্যতিক্রম S → ε, তবে শুধু যদি S কোনো নিয়মের ডান দিকে না থাকে।
- Type 2 (context-free): প্রতিটি নিয়ম A → β, অর্থাৎ বাঁ দিকে ঠিক একটি variable; β = ε-ও চলে।
- Type 3 (right-linear বা regular): প্রতিটি নিয়ম A → aB, A → a বা A → ε.
একটি language type i, যদি কোনো type-i grammar তাকে তৈরি করে। Type 3 language-ই regular language, type 2 হলো context-free language (CFL), আর type 1 হলো context-sensitive language (CSL).
| Type | নিয়মের আকার | Machine | স্মৃতি | উদাহরণ |
|---|---|---|---|---|
| 3 · regular | A → aB ∣ a ∣ ε | DFA / NFA | শুধু সসীম state | BG-0042 ধাঁচের অর্ডার কোড, জোড় সংখ্যক 1 |
| 2 · context-free | A → β | PDA | state + একটি stack | aⁿbⁿ, অর্ডার-query-র সুষম বন্ধনী |
| 1 · context-sensitive | |α| ≤ |β| | LBA | ইনপুটের সমান দৈর্ঘ্যের tape | aⁿbⁿcⁿ |
| 0 · unrestricted | α → β | Turing machine | সীমাহীন tape | ATM, “প্রোগ্রাম কি থামবে?”-এর হ্যাঁ-সেট |
“Context-sensitive” নামটি পুরোনো রূপ γAδ → γβδ থেকে, যেখানে A-কে β দিয়ে বদলানো যায় শুধু γ আর δ-এর “প্রসঙ্গে”; noncontracting রূপ আর এই রূপ একই language-শ্রেণি দেয়। Type 2-এ কোনো প্রসঙ্গ লাগে না, A যেখানেই থাকুক বদলানো যায়। আর Type 3-এ ডান দিকে বড়জোর একটি variable, সেটিও শেষে: derivation-এর প্রতিটি ধাপে বাঁ থেকে একটি করে terminal লেখা হয়, ঠিক যেমন finite automaton একটি করে চিহ্ন পড়ে।
ε-নিয়মের সূক্ষ্মতা: grammar-এর স্তরে type-গুলো পুরোপুরি একটির ভেতরে আরেকটি নয়। A → ε নিয়মটি type 2 আর type 3-এ চলে, কিন্তু type 1-এ নয় (|A| = 1 > 0 = |ε|)। তাই S → aS | ε একটি type 3 grammar, কিন্তু type 1 grammar নয়, কারণ S ডান দিকেও আছে। Language-এর স্তরে অবশ্য শিকল ঠিক থাকে: ε-নিয়ম সরানোর কৌশলে (পর্ব ২৮) যেকোনো CFG-কে এমন grammar-এ বদলানো যায়, যার একমাত্র ε-নিয়ম S → ε আর S ডান দিকে নেই। Chomsky-র নিজের type 3 রূপে A → ε ছিল না (শুধু S → ε ব্যতিক্রম); সেই রূপ আর এখানকার রূপ একই language-শ্রেণি দেয়।
নিচের stepper পাঁচটি grammar-কে শ্রেণিতে বসায়। প্রতিটির language scratch script-এ দৈর্ঘ্য ৮–৯ পর্যন্ত সব derivation বানিয়ে একটি reference সংজ্ঞার সঙ্গে মিলিয়ে দেখা হয়েছে (একই পরীক্ষা অংশ ৪-এর Python ব্লকে)।
1G1: S → 0S | 1T | ε2 T → 0T | 1S3G2: S → (S)S | ε4G3: S → aT ; T → Sb | b5G4: S → aSBC | aBC6 CB → BC ; aB → ab7 bB → bb ; bC → bc ; cC → cc8G5: G4, কিন্তু S → aSBC | ε
| নিয়মের পরীক্ষা | |
| সবচেয়ে কড়া type | |
| language | |
| language-এর শ্রেণি |
- G1. প্রতিটি নিয়ম “একটি terminal, তারপর একটি variable” বা ε, তাই type 3. S মানে “এ পর্যন্ত 1 জোড়”, T মানে “বিজোড়”; ε শুধু S থেকে আসে, তাই language জোড় সংখ্যক 1. লক্ষ করুন, S → ε থাকলেও S ডান দিকে আছে, তাই grammar-টি type 1 নয়।
- G2. বাঁ দিকে একটি variable, তাই type 2; ডান দিকে variable মাঝখানে, তাই type 3 নয়। এটি সুষম বন্ধনী তৈরি করে, যা regular নয় (পর্ব ১৭-এ প্রমাণ)।
- G3. S → aT right-linear, কিন্তু T → Sb-তে variable বাঁয়ে, terminal ডানে। প্রতিটি নিয়মে একটিই variable, তবু দুই দিকের মিশ্রণে language aⁿbⁿ, regular নয়। “প্রতিটি নিয়ম linear” যথেষ্ট নয়, দিক একই হতে হয়।
- G4. CB → BC আর aB → ab-এর বাঁ দিকে দুটি চিহ্ন, তাই type 2 নয়; কোনো নিয়ম string ছোট করে না, তাই type 1. S থেকে aⁿ(BC)ⁿ আসে, CB → BC দিয়ে সব B বাঁয়ে সরে, আর শেষ চার নিয়ম বাঁ থেকে ডানে ছোট হাতের অক্ষরে বদলায়।
- G5. একমাত্র বদল S → ε, অথচ S নিয়মের ডান দিকে আছে, তাই noncontracting শর্ত ভাঙে: grammar-টি শুধু type 0. কিন্তু language aⁿbⁿcⁿ (n ≥ 0) একটি CSL, কারণ নতুন start symbol S′ → ε | S যোগ করলেই একটি type 1 grammar পাওয়া যায়।
- সারকথা। Grammar-এর type বলে language অন্তত কতটা সরল; language-এর শ্রেণি হলো তাকে তৈরি করতে পারে এমন সবচেয়ে কড়া type. কোনো grammar type 2 নয় দেখে language “context-free নয়” বলা যায় না; তার জন্য pumping lemma-র মতো প্রমাণ লাগে।
নিয়মের আকার যাচাই করা পুরোপুরি যান্ত্রিক কাজ, তাই এটি একটি ছোট program-এ লেখা যায়। নিচের classifier প্রতিটি নিয়ম দেখে কোন কোন type-এর শর্ত মেলে তা বলে, আর সবচেয়ে কড়াটি জানায়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।
# Rule-shape classifier. Uppercase letter = variable, anything else = terminal.
def is_var(c): return c.isupper()
def rule_types(G, S="S"):
on_right = any(S in rhs for _, rhs in G)
t3 = t2 = t1 = t0 = True
for lhs, rhs in G:
t0 &= any(is_var(c) for c in lhs) # lhs must contain a variable
t2 &= len(lhs) == 1 and is_var(lhs)
t3 &= (len(lhs) == 1 and is_var(lhs) and
(rhs == "" or (len(rhs) == 1 and not is_var(rhs)) or
(len(rhs) == 2 and not is_var(rhs[0]) and is_var(rhs[1]))))
t1 &= len(lhs) <= len(rhs) or (lhs == S and rhs == "" and not on_right)
return {3: t3 and t2, 2: t2 and t0, 1: t1 and t0, 0: t0}
def classify(name, G):
ok = rule_types(G)
best = next((t for t in (3, 2, 1, 0) if ok[t]), None)
print(f"{name}: types {[t for t in (3, 2, 1, 0) if ok[t]]} -> most restrictive: type {best}")
def R(text): # "S->0S|1T|" ; empty alternative = epsilon
G = []
for part in text.split(";"):
lhs, rhs = part.split("->")
G += [(lhs.strip(), alt.strip()) for alt in rhs.split("|")]
return G
classify("G1 even 1s ", R("S->0S|1T|; T->0T|1S"))
classify("G2 brackets ", R("S->(S)S|"))
classify("G3 mixed ", R("S->aT; T->Sb|b"))
classify("G4 a^nb^nc^n ", R("S->aSBC|aBC; CB->BC; aB->ab; bB->bb; bC->bc; cC->cc"))
classify("G5 erasing ", R("S->aSBC|; CB->BC; aB->ab; bB->bb; bC->bc; cC->cc"))আসল আউটপুট (ব্রাউজারের Python):
G1 even 1s : types [3, 2, 0] -> most restrictive: type 3
G2 brackets : types [2, 0] -> most restrictive: type 2
G3 mixed : types [2, 1, 0] -> most restrictive: type 2
G4 a^nb^nc^n : types [1, 0] -> most restrictive: type 1
G5 erasing : types [0] -> most restrictive: type 0
প্রতিটি লাইন stepper-এর “সবচেয়ে কড়া type” সারির সঙ্গে মেলে। লক্ষ করার মতো দুটি তালিকা: G1 আর G2-এর তালিকায় 1 নেই, কারণ তাদের ε-নিয়ম noncontracting শর্ত ভাঙে, যা ওপরের সতর্কবার্তা বলে। G3-এর তালিকায় 1 আছে কিন্তু 3 নেই: কোনো নিয়ম string ছোট করে না, কিন্তু T → Sb right-linear নয়। Program শুধু grammar দেখে, language নয়; G5-এর “type 0” মানে তার language CSL নয়, এমন নয়। কোনো grammar-এর language আসলে কোন শ্রেণির, সেই প্রশ্নটি সাধারণভাবে অনেক কঠিন, আর পর্ব ৫৪-এ দেখবেন কিছু ক্ষেত্রে তা undecidable-ও।
৩ · প্রতিটি স্তরের machine আর তার স্মৃতি
Grammar তৈরি করে, machine চেনে। Hierarchy-র আসল সৌন্দর্য হলো, প্রতিটি grammar-শ্রেণির জন্য ঠিক একটি স্বাভাবিক machine-শ্রেণি আছে, আর দুটির পার্থক্য শুধু স্মৃতির ধরনে। রেলের টিকিট কাউন্টারের কর্মী যদি শুধু একটি সবুজ বা লাল বাতি মনে রাখতে পারেন, তিনি “লাইনে জোড় না বিজোড় মানুষ” বলতে পারবেন, কিন্তু “যতজন ঢুকেছেন ততজন বেরিয়েছেন কি না” পারবেন না। একটি খাতা (stack) পেলে পারবেন। আর পুরো লাইনের ওপর চক দিয়ে দাগ দিতে পারলে আরও কঠিন হিসাব করতে পারবেন।
Finite automaton
DFA (Q, Σ, δ, q0, F) বা NFA. স্মৃতি শুধু বর্তমান state, সংখ্যায় সসীম। ইনপুট একবার বাঁ থেকে ডানে পড়ে। পর্ব ০৭–১১।
Type 3Pushdown automaton
PDA (Q, Σ, Γ, δ, q0, F): finite automaton আর একটি সীমাহীন stack, যার শুধু ওপরের চিহ্ন দেখা যায়। পর্ব ৩২–৩৫।
Type 2Linear bounded automaton
এমন nondeterministic Turing machine, যার head ইনপুটের দুই প্রান্তচিহ্নের বাইরে যায় না: tape-এর মাপ ইনপুটের সমান। এই কোর্সে বিস্তারিত নয়।
Type 1- L right-linear grammar দিয়ে তৈরি ⇔ L কোনো finite automaton চেনে। (প্রমাণ নিচে; Chomsky আর Miller ১৯৫৮)
- L context-free ⇔ L কোনো PDA চেনে। (প্রমাণ পর্ব ৩৪-এ)
- L context-sensitive ⇔ L কোনো LBA চেনে। (Kuroda ১৯৬৪; প্রমাণ এই কোর্সে বাদ, Hopcroft ও Ullman-এর ১৯৭৯ সালের বইয়ের Chomsky hierarchy অধ্যায়ে আছে)
- L type 0 ⇔ L কোনো Turing machine চেনে, অর্থাৎ L Turing-recognizable. (প্রমাণের রূপরেখা অংশ ৫-এ)
প্রথম অংশের একটি দিক এখনই প্রমাণ করা যায়, আর এটি একটি পরিষ্কার “given G, build M” construction proof. Grammar G = (V, Σ, R, S) right-linear হলে NFA N = (V ∪ {f}, Σ, δ, S, F) বানান, যেখানে f একটি নতুন state:
| Grammar-এর নিয়ম | NFA-তে যা যোগ হয় | উদাহরণ (string 01 দিয়ে শেষ) |
|---|---|---|
| A → aB | B ∈ δ(A, a) | S → 0S, S → 1S, S → 0A |
| A → a | f ∈ δ(A, a) | A → 1 |
| A → ε | A ∈ F | (নেই) |
| সবসময় | f ∈ F, শুরু S | δ(S, 0) = {S, A}, δ(S, 1) = {S}, δ(A, 1) = {f} |
সঠিকতার প্রমাণ:
- দাবি: যেকোনো w ∈ Σ∗ আর B ∈ V-এর জন্য, S ⇒∗ wB ⇔ w পড়ে N, S থেকে B-তে পৌঁছাতে পারে। — |w|-এর ওপর induction (পর্ব ০৪)
- ভিত্তি |w| = 0: S ⇒∗ S শূন্য ধাপে, আর N শূন্য চিহ্নে S-এই থাকে। অন্য B-তে শূন্য ধাপে যাওয়া যায় না, দুই দিকেই। — right-linear derivation-এ variable সবসময় শেষে একটি
- ধাপ w = xa: S ⇒∗ xaB মানে শেষ নিয়মটি C → aB আর আগে S ⇒∗ xC; induction অনুমানে N, x পড়ে C-তে পৌঁছায়, আর B ∈ δ(C, a). উল্টো দিকও একই ধাপগুলো উল্টে। — নিয়ম আর transition-এর এক-এক মিল
- S ⇒∗ w (শুধু terminal) ঘটে ঠিক দুইভাবে: S ⇒∗ wB আর B → ε, অথবা S ⇒∗ xB, B → a আর w = xa. প্রথমটি মানে N w পড়ে B ∈ F-এ; দ্বিতীয়টি মানে x পড়ে B, তারপর a পড়ে f ∈ F-এ। — ধাপ ১ আর টেবিলের শেষ দুই সারি
- অতএব L(N) = L(G). ∎
উল্টো দিকটি আরও সহজ: একটি DFA-র প্রতিটি δ(A, a) = B থেকে নিয়ম A → aB, আর প্রতিটি accept state A থেকে A → ε. Scratch script-এ উদাহরণের NFA দৈর্ঘ্য ১০ পর্যন্ত সব ২০৪৭টি string-এ “01 দিয়ে শেষ” সংজ্ঞার সঙ্গে হুবহু মিলেছে। NFA-র পূর্ণ তত্ত্ব পর্ব ০৯-এ।
কেন প্রতিটি স্তরে স্মৃতি বাড়াতে হয়, তা একই ধাঁচের ইনপুট aabbcc চার machine-কে দিয়ে দেখা যাক।
1DFA : k-টি state মাত্র2PDA a: push A3PDA a: push A4PDA b: pop5PDA b: pop6PDA c: stack ফাঁকা7LBA 1: [aabbcc] → [xaybzc]8LBA 2: [xaybzc] → [xxyyzz]9TM : tape সীমাহীন
| machine | |
| স্মৃতি | |
| এখনকার অবস্থা |
- DFA. k-টি state-এর DFA a0, a1, …, ak এই k + 1টি prefix পড়লে pigeonhole-এ দুটি prefix ai আর aj (i ≠ j) একই state-এ পৌঁছায়। তখন aibi গৃহীত হলে ajbi-ও গৃহীত হয়। তাই কোনো DFA aⁿbⁿ চেনে না; পূর্ণ প্রমাণ পর্ব ১৭-এ।
- PDA, প্রথম a. Stack-এ একটি A রাখা হলো। Stack সীমাহীন, তাই যত a-ই আসুক, গোনা চলে।
- দ্বিতীয় a. Stack [A A]: দুটি a-এর হিসাব জমা।
- প্রথম b. প্রতিটি b-তে একটি A তোলা হয় (pop). Stack [A].
- দ্বিতীয় b. Stack ফাঁকা: a আর b-এর সংখ্যা মিলেছে। aabb পর্যন্ত PDA সফল, তাই aⁿbⁿ context-free.
- c এলো। b মেলাতে গিয়ে a-এর হিসাব খরচ হয়ে গেছে, c-এর সংখ্যা যাচাইয়ের তথ্য নেই। অন্য কোনো চালাকিতেও কোনো PDA aⁿbⁿcⁿ চেনে না; প্রমাণ পর্ব ৩৬-এর CFL pumping lemma দিয়ে।
- LBA, প্রথম পাস। Tape [aabbcc], দুই পাশে প্রান্তচিহ্ন, মোট ৮ ঘর। বাঁ থেকে প্রথম a-কে x, প্রথম b-কে y, প্রথম c-কে z করা হলো: [xaybzc].
- দ্বিতীয় পাস। আবার একটি করে কাটা: [xxyyzz]. আর কোনো a নেই, b বা c-ও বাকি নেই, তাই ACCEPT. পুরো সময় tape ৮ ঘরেরই ছিল।
- Turing machine. নতুন ঘর যত খুশি ব্যবহার করতে পারে, যেমন আরেকটি program-কে ধাপে ধাপে simulate করতে। এই স্বাধীনতার দাম: machine না-ও থামতে পারে।
নিচের JavaScript ব্লক LBA-র এই কৌশলটি চালায় আর প্রতিটি পাসের পর tape দেখায়। ভেতরে একটি পরীক্ষা আছে যে tape-এর দৈর্ঘ্য কখনো বদলায় না।
// LBA-style decider for { a^n b^n c^n : n >= 1 }.
// The tape is only the input between end markers [ and ]; it never grows.
function lba(w) {
const tape = ["[", ...w, "]"], size = tape.length;
const log = [tape.join("")];
if (!/^a+b+c+$/.test(w)) return [false, log, "pass 0: not of the form a+b+c+"];
for (let pass = 1; ; pass++) {
const i = tape.indexOf("a");
if (i === -1) { // no a left: b or c must not remain
const ok = !tape.includes("b") && !tape.includes("c");
return [ok, log, ok ? "all crossed off" : "extra b or c"];
}
tape[i] = "x"; // cross off one a ...
const j = tape.indexOf("b", i);
if (j === -1) return [false, log, "pass " + pass + ": no b to match"];
tape[j] = "y"; // ... one b ...
const k = tape.indexOf("c", j);
if (k === -1) return [false, log, "pass " + pass + ": no c to match"];
tape[k] = "z"; // ... and one c
log.push(tape.join(""));
if (tape.length !== size) throw new Error("tape grew");
}
}
for (const w of ["aabbcc", "aabbc", "aaabbbccc", "abcabc"]) {
const [ok, log, why] = lba(w);
console.log(w.padEnd(10), ok ? "ACCEPT" : "reject", "|", why);
console.log(" " + log.join(" -> "));
}আসল আউটপুট (ব্রাউজারের JavaScript):
aabbcc ACCEPT | all crossed off
[aabbcc] -> [xaybzc] -> [xxyyzz]
aabbc reject | pass 2: no c to match
[aabbc] -> [xaybz]
aaabbbccc ACCEPT | all crossed off
[aaabbbccc] -> [xaaybbzcc] -> [xxayybzzc] -> [xxxyyyzzz]
abcabc reject | pass 0: not of the form a+b+c+
[abcabc]
প্রথম দুই লাইন stepper-এর ধাপ ৭–৮. aabbc-তে দ্বিতীয় পাসে মেলানোর মতো c নেই, তাই reject. abcabc-তে সংখ্যা সমান হলেও ক্রম ভুল; পাস ০-এর একটি বাঁ-থেকে-ডানে পরীক্ষা (নিজেই একটি regular language-এর পরীক্ষা) তা ধরে ফেলে। “tape grew” error কখনো আসেনি: সব কাজ ইনপুটের জায়গাতেই হয়েছে, LBA-র সংজ্ঞা ঠিক এটাই চায়। Scratch script-এ এই function দৈর্ঘ্য ৯ পর্যন্ত {a, b, c}-এর সব string-এ aⁿbⁿcⁿ সংজ্ঞার সঙ্গে মিলিয়ে দেখা হয়েছে, কোনো অমিল পাওয়া যায়নি। প্রতিটি পাস একটি করে a কাটে, তাই সর্বোচ্চ n + 1টি পাস: এটি সবসময় থামে।
৪ · সিঁড়ি বেয়ে ওঠা: কঠোর অন্তর্ভুক্তির শিকল
এখন পুরো মানচিত্রটি এক ছবিতে দেখা যাক। ছবিতে Chomsky-র চার স্তরের বাইরে আরও দুটি সীমানা আছে: decidable language (কোনো Chomsky type নয়) আর “সব language”.
Language-শ্রেণিগুলো একটির ভেতরে আরেকটি
প্রতিটি বাক্সে তার machine আর এমন একটি উদাহরণ, যা ঠিক ভেতরের বাক্সে নেই। হলুদ ডটেড বাক্সটি Chomsky type নয়।
1Type 3 : জোড় সংখ্যক 1, BG-00422Type 2 : aⁿbⁿ, সুষম বন্ধনী3Type 1 : aⁿbⁿcⁿ4Decid. : D (diagonal)5Type 0 : A_TM, HALT_TM6বাইরে : A_TM-এর complement
| নতুন language | |
| machine | |
| নিচের স্তরে নয় কেন |
- Type 3. বাজারঘরের সেন্সর লাইনের parity check (জোড় সংখ্যক 1) চিনতে ২ state-এর DFA যথেষ্ট। অর্ডার কোড “BG-” আর ৪টি অঙ্ক একটি সসীম language, আর প্রতিটি সসীম language regular.
- Type 2. অর্ডার-query-তে বন্ধনী সুষম কি না, বা aⁿbⁿ: সীমাহীন গোনা লাগে, তাই regular নয় (পর্ব ১৭-এর pumping lemma, পর্ব ১৮-এর Myhill–Nerode). একটি stack-ই যথেষ্ট।
- Type 1. aⁿbⁿcⁿ-এ তিনটি সংখ্যা একসঙ্গে মেলাতে হয়। এক stack পারে না (পর্ব ৩৬), কিন্তু ইনপুটের জায়গায় দাগ কেটে LBA পারে।
- Decidable. এমন language আছে, যা একটি সব-সময়-থামা program চেনে, কিন্তু কোনো CSG তৈরি করে না। উদাহরণ D, অংশ ৫-এর diagonal; পর্ব ৬৭-এর space hierarchy theorem আরেক পথে একই কথা দেয়।
- Type 0. ATM = {⟨M, w⟩ : M, w গ্রহণ করে}: M-কে w-এ চালিয়ে দেখলে “হ্যাঁ” একসময় আসে, কিন্তু “না” না-ও আসতে পারে। পর্ব ৫১-এ প্রমাণ হবে এটি decidable নয়; বাজারঘরের “এই program কি থামবে?” প্রশ্ন, অর্থাৎ halting problem, এখানেই।
- বাইরে। ATM-এর complement কোনো TM চেনে না: L আর তার complement দুটিই recognizable হলে L decidable (পর্ব ৫০), কিন্তু ATM decidable নয়। পর্ব ০২-এর গণনাও বলে, বেশিরভাগ language এই বাইরের অংশে।
REG ⊊ CFL ⊊ CSL ⊊ DECIDABLE ⊊ RECOGNIZABLE ⊊ P(Σ∗)
যেখানে প্রতিটি শ্রেণি একটি নির্দিষ্ট alphabet-এর ওপর (অন্তত দুটি চিহ্ন ধরে নিন; শেষ দুটি “⊊”-এর জন্য encoding লাগে, পর্ব ০৫)।
“⊆” অংশের প্রমাণ (“⊊”-এর জন্য ওপরের উদাহরণ আর তাদের পর্ব):
- REG ⊆ CFL: প্রতিটি right-linear নিয়ম A → aB, a বা ε একটি context-free নিয়মও। — সংজ্ঞা ২.১
- CFL ⊆ CSL: CFG-এর ε-নিয়ম সরিয়ে (পর্ব ২৮) এমন grammar পাই, যার প্রতিটি নিয়ম A → β-তে |β| ≥ 1 = |A|, শুধু S → ε ব্যতিক্রম আর S ডানে নেই। এটি type 1. — ε-removal
- CSL ⊆ DECIDABLE: অংশ ৫-এর উপপাদ্য ৫.১. — সসীম খোঁজ
- DECIDABLE ⊆ RECOGNIZABLE: প্রতিটি decider একটি recognizer-ও। — সংজ্ঞা (পর্ব ৫০)
- RECOGNIZABLE ⊆ P(Σ∗): প্রতিটি language Σ∗-এর একটি subset. ∎
প্রশ্ন: L = {aibj : i ≥ j ≥ 0} hierarchy-র কোন সবচেয়ে নিচের স্তরে? পূর্ণ উত্তরে তিনটি অংশ লাগে: একটি ওপরের সীমা, একটি নিচের সীমা, আর একটি যাচাই।
- ওপরের সীমা: G: S → aS | aSb | ε. S → aSb একটি a আর একটি b একসঙ্গে যোগ করে, S → aS শুধু একটি a, আর নতুন চিহ্ন সবসময় S-এর দুই পাশে বসে; তাই প্রতিটি তৈরি string-এ সব a সব b-এর আগে, আর b-এর সংখ্যা a-এর চেয়ে বেশি নয়। উল্টো দিকে aibj (j ≤ i) পেতে S → aS নিয়ম i − j বার, S → aSb নিয়ম j বার, শেষে S → ε. G type 2, তাই L context-free.
- নিচের সীমা: L regular নয়। Myhill–Nerode-এর ভাষায় (পর্ব ১৮) a0, a1, a2, … পরস্পর আলাদা: i < k হলে suffix bk জুড়লে akbk ∈ L কিন্তু aibk ∉ L. অসীম সংখ্যক আলাদা class থাকলে কোনো DFA যথেষ্ট নয়।
- যাচাই: নিচের generator-এ
R("S->aS|aSb|")বসালে দৈর্ঘ্য ≤ 8-এ ২৫টি string আসে, যা reference সংজ্ঞার সঙ্গে হুবহু মেলে (scratch-এ চালিয়ে দেখা)। সিদ্ধান্ত: L CFL, কিন্তু regular নয়; অর্থাৎ এর স্তর ঠিক Type 2.
শিকলের প্রথম তিন স্তর brute force দিয়ে হাতে-কলমে যাচাই করা যায়। নিচের generator সংজ্ঞা ১.১ হুবহু মেনে চলে: প্রতিটি sentential form-এ প্রতিটি জায়গায় প্রতিটি নিয়ম খাটায়, দৈর্ঘ্যের একটি সীমা পর্যন্ত। তারপর তৈরি হওয়া string-এর set-কে reference সংজ্ঞায় বাছাই করা string-এর set-এর সঙ্গে মেলায়।
from itertools import product
def R(text): # "S->aSb|" ; empty alternative = epsilon
return [(l.strip(), a.strip()) for p in text.split(";")
for l, r in [p.split("->")] for a in r.split("|")]
def generate(G, maxlen, slack=2, S="S"): # every rule, every position
seen, frontier = {S}, [S]
while frontier:
nxt = []
for form in frontier:
for lhs, rhs in G:
i = form.find(lhs)
while i != -1:
new = form[:i] + rhs + form[i + len(lhs):]
if len(new) <= maxlen + slack and new not in seen:
seen.add(new); nxt.append(new)
i = form.find(lhs, i + 1)
frontier = nxt
return {f for f in seen if len(f) <= maxlen and not any(c.isupper() for c in f)}, len(seen)
def anbn(w, k): # a^n b^n (k=2) or a^n b^n c^n (k=3)
return len(w) % k == 0 and w == "".join(ch * (len(w) // k) for ch in "abc"[:k])
def balanced(w): # depth never negative, ends at 0
d = [0]
for ch in w: d.append(d[-1] + (1 if ch == "(" else -1))
return min(d) == 0 and d[-1] == 0
tests = [("G1", "S->0S|1T|; T->0T|1S", "01", 8, lambda w: w.count("1") % 2 == 0),
("G2", "S->(S)S|", "()", 8, balanced),
("G3", "S->aT; T->Sb|b", "ab", 8, lambda w: w != "" and anbn(w, 2)),
("G4", "S->aSBC|aBC; CB->BC; aB->ab; bB->bb; bC->bc; cC->cc", "abc", 9,
lambda w: w != "" and anbn(w, 3))]
for name, rules, sigma, n, ref in tests:
words, forms = generate(R(rules), n)
expect = {w for m in range(n + 1) for t in product(sigma, repeat=m)
for w in ["".join(t)] if ref(w)}
short = [w or "ε" for w in sorted(words, key=lambda w: (len(w), w))[:4]]
print(f"{name} len<={n}: {len(words):3} words, {forms:4} forms, match: {words == expect}", short)আসল আউটপুট (ব্রাউজারের Python):
G1 len<=8: 256 words, 1535 forms, match: True ['ε', '0', '00', '11']
G2 len<=8: 23 words, 176 forms, match: True ['ε', '()', '(())', '()()']
G3 len<=8: 4 words, 15 forms, match: True ['ab', 'aabb', 'aaabbb', 'aaaabbbb']
G4 len<=9: 3 words, 42 forms, match: True ['abc', 'aabbcc', 'aaabbbccc']
চারটি grammar-ই reference সংজ্ঞার সঙ্গে হুবহু মিলেছে। G1-এ দৈর্ঘ্য ≤ 8-এর ৫১১টি binary string-এর ঠিক ২৫৬টিতে জোড় সংখ্যক 1. G2-এর ২৩ = 1 + 1 + 2 + 5 + 14, অর্থাৎ ০, ২, ৪, ৬, ৮ দৈর্ঘ্যের সুষম বন্ধনীর সংখ্যা (Catalan সংখ্যা)। G3 আর G4 খুব কম string তৈরি করে, কিন্তু ঠিক সঠিকগুলো। slack=2 মানে sentential form সর্বোচ্চ ২টি চিহ্ন বেশি লম্বা হতে পারে, কারণ G1 আর G2-এর ε-নিয়ম পরে form ছোট করে। Brute force এখানে একটি সসীম পরীক্ষা, প্রমাণ নয়: “G4 ঠিক aⁿbⁿcⁿ তৈরি করে” সব n-এর জন্য প্রমাণ করতে invariant লাগে (পর্ব ০৪)।
৫ · Decidable কোথায় বসে, আর Type 0 কেন Turing machine
একটি কথা জোর দিয়ে বলা দরকার: decidable language-এর শ্রেণি কোনো Chomsky type নয়। এটি কোনো নিয়মের আকার দিয়ে সংজ্ঞায়িত নয়, বরং machine-এর একটি আচরণ দিয়ে: “সব ইনপুটে থামে”। তবু শ্রেণিটি hierarchy-র ঠিক মাঝখানে বসে, কারণ নিচের দুটি উপপাদ্য।
G একটি type 1 grammar হলে এমন algorithm আছে, যা যেকোনো w ∈ Σ∗-এ থামে এবং w ∈ L(G) কি না সঠিক বলে।
- w = ε হলে উত্তর “হ্যাঁ” ঠিক তখন, যখন S → ε নিয়মটি আছে। — অন্য কোনো নিয়ম form ছোট করে না
- w ≠ ε হলে: S → ε বাদে প্রতিটি নিয়মে |α| ≤ |β|, তাই একটি derivation-এ sentential form-এর দৈর্ঘ্য কখনো কমে না। — noncontracting
- অতএব S ⇒∗ w-এর যেকোনো derivation-এর প্রতিটি form-এর দৈর্ঘ্য ≤ |w|। — ধাপ ২
- দৈর্ঘ্য ≤ |w|-এর form সসীম সংখ্যক: m = |V ∪ Σ| হলে বড়জোর (m + 1)|w|টি। — গুণের নিয়ম
- S থেকে এই সসীম graph-এ BFS চালান (পর্ব ০২-এর reachability). BFS থামে, আর w পাওয়া গেলে “হ্যাঁ”, না গেলে “না”। ∎
from collections import deque
# Noncontracting (type 1) grammar for { a^n b^n c^n : n >= 1 }
G = [("S", "aSBC"), ("S", "aBC"), ("CB", "BC"), ("aB", "ab"),
("bB", "bb"), ("bC", "bc"), ("cC", "cc")]
def member(G, w, S="S"):
# |lhs| <= |rhs| in every rule, so a form longer than w can never
# shrink back to w: searching forms of length <= |w| is enough.
seen, queue = {S}, deque([S])
while queue:
form = queue.popleft()
if form == w:
return True, len(seen)
for lhs, rhs in G:
i = form.find(lhs)
while i != -1:
new = form[:i] + rhs + form[i + len(lhs):]
if len(new) <= len(w) and new not in seen:
seen.add(new); queue.append(new)
i = form.find(lhs, i + 1)
return False, len(seen) # finite search space: always halts
for w in ["abc", "aabbcc", "aabbc", "abcabc", "aabcbc", "aaabbbccc"]:
ok, n = member(G, w)
print(f"{w:10} {'YES' if ok else 'no ':3} forms explored: {n}")
symbols = 6 + 1 # S, B, C, a, b, c plus "no symbol"
print("upper bound for |w| = 9:", symbols ** 9, "forms")আসল আউটপুট (ব্রাউজারের Python):
abc YES forms explored: 4
aabbcc YES forms explored: 13
aabbc no forms explored: 5
abcabc no forms explored: 13
aabcbc no forms explored: 13
aaabbbccc YES forms explored: 37
upper bound for |w| = 9: 40353607 forms
তিনটি “no” উত্তরই গুরুত্বপূর্ণ: program খোঁজ শেষ করে নিশ্চিতভাবে “না” বলেছে, অসীম অপেক্ষা করেনি। এটিই decider আর recognizer-এর পার্থক্য। aabcbc-এ a, b, c সমান সংখ্যায় থাকলেও ক্রম ভুল, আর ১৩টি form দেখার পর আর কোনো নতুন form নেই। শেষ লাইন ধাপ ৪-এর সীমা: দৈর্ঘ্য ৯-এর জন্য তাত্ত্বিক সীমা চার কোটির বেশি, কিন্তু বাস্তবে মাত্র ৩৭টি form তৈরি হয়েছে। এই সীমা সূচকীয়; সাধারণ CSL-এর membership PSPACE-complete হতে পারে, তাই দ্রুত সাধারণ algorithm আশা করা হয় না (পর্ব ৬৫)।
এমন একটি decidable language D ⊆ {0, 1}∗ আছে, যা কোনো context-sensitive grammar তৈরি করে না।
প্রমাণের রূপরেখা (diagonalization, পর্ব ০২ আর ০৪-এর কৌশল):
- Terminal {0, 1} আর variable-এর নাম একটি নির্দিষ্ট ক্রমে রেখে প্রতিটি type 1 grammar-কে একটি string ⟨G⟩ হিসেবে লেখা যায় (পর্ব ০৫)। বৈধ encoding-গুলো shortlex ক্রমে সাজালে তালিকা G1, G2, …; প্রতিটি CSL এই তালিকার কোনো grammar-এর language. — encoding
- w1, w2, … হলো {0, 1}∗-এর shortlex তালিকা। D = {wi : wi ∉ L(Gi)} সংজ্ঞায়িত করি। — কর্ণ উল্টানো
- D decidable: w দিলে তার অবস্থান i বের করুন, Gi বানান, উপপাদ্য ৫.১-এর algorithm দিয়ে w ∈ L(Gi) যাচাই করুন, উত্তর উল্টে দিন। প্রতিটি ধাপ থামে। — উপপাদ্য ৫.১ এক algorithm-এ সব G-তে খাটে
- D কোনো CSL নয়: যদি D = L(Gj) হয়, তবে wj ∈ D ⇔ wj ∉ L(Gj) = D, স্ববিরোধ। ∎
এই যুক্তি একটি সাধারণ সত্য দেখায়: যে শ্রেণির সদস্যপদ একটিমাত্র algorithm সব সদস্যের জন্য decide করে, সেই শ্রেণি সব decidable language ধরতে পারে না। একই যুক্তি decider-এর ওপর চালালে আটকে যায়, কারণ “এই TM কি decider?” নিজেই decidable নয়; এটাই পর্ব ৫১-এর গল্প।
Type 0 = Turing-recognizable
প্রমাণের রূপরেখা. (⇒) একটি TM সব derivation BFS-এ তৈরি করে, w পেলে accept করে। Type 0-এ form ছোট-বড় দুটোই হয়, তাই খোঁজের কোনো সীমা নেই: w ∉ L(G) হলে machine চিরকাল চলতে পারে। এটি recognizer, decider নয়। (⇐) উল্টো দিকে grammar একটি TM-কে নকল করে: প্রথমে ইনপুটের দুটি কপি সহ শুরুর configuration তৈরি করে, তারপর TM-এর প্রতিটি transition-কে একটি প্রতিস্থাপনের নিয়ম হিসেবে লেখে (configuration ⊢ পরের configuration), আর qaccept এলে সব কাজের চিহ্ন মুছে শুধু ইনপুটের কপি রাখে। বিস্তারিত এই কোর্সে বাদ; Hopcroft ও Ullman-এর ১৯৭৯ সালের বইয়ের Chomsky hierarchy অধ্যায়ে আছে। Type 0 grammar হলো Post-এর পুরোনো “rewriting system” ধারণার আত্মীয়, আর পর্ব ৪৯-এ এমন আরও কয়েকটি সমতুল্য মডেল দেখবেন।
৬ · Complexity class-এর পাশে hierarchy
Chomsky hierarchy প্রশ্ন করে “কোন যন্ত্রে করা যায়”, আর complexity তত্ত্ব (মডিউল ১০–১১) প্রশ্ন করে “কত সময় বা কত জায়গায়”। P, NP, PSPACE মূল hierarchy-র অংশ নয়, কিন্তু তাদের অবস্থান জানা থাকলে পরের মডিউলগুলো পরিষ্কার হয়।
কোন শ্রেণি কোনটির ভেতরে: প্রমাণিত আর অজানা
নিচ থেকে ওপরে বড় হয়। কালো রেখা: প্রমাণিত কঠোর অন্তর্ভুক্তি। কমলা ড্যাশ: অন্তর্ভুক্তি প্রমাণিত, কঠোর কি না অজানা। লাল ডট: কোনো দিকের অন্তর্ভুক্তি জানা নেই।
- Regular: ঠিক সেই language, যা কোনো TM ধ্রুবক পরিমাণ বাড়তি জায়গায় decide করে (একটি জানা ফল), আর DFA দিয়ে O(n) সময়ে।
- CFL ⊊ P: যেকোনো CFG-এর membership CYK algorithm-এ O(n3) সময়ে (পর্ব ৩১), আর aⁿbⁿcⁿ P-তে আছে কিন্তু CFL নয়।
- CSL = NSPACE(n): LBA মানে linear জায়গার nondeterministic machine, তাই Kuroda-র ফলটিকে এভাবেও পড়া যায়। Savitch-এর theorem (পর্ব ৬৪) দিয়ে NSPACE(n) ⊆ SPACE(n2), আর space hierarchy theorem (পর্ব ৬৭) দিয়ে CSL ⊊ PSPACE.
- P আর CSL: কোনোটি অন্যটির ভেতরে কি না, দুই দিকই অজানা। একটি অংশ সহজে বোঝা যায়: কিছু CSL PSPACE-complete, তাই CSL ⊆ P প্রমাণ করলে P = PSPACE হতো, যা একটি খোলা প্রশ্ন।
- P বনাম NP: P ⊆ NP প্রমাণিত, P = NP কি না অজানা (পর্ব ৬৩)। কেউ “সমাধান হয়েছে” বললে সতর্ক থাকুন।
৭ · Closure আর decision property-র মানচিত্র
একটি শ্রেণি কোনো operation-এ closed মানে, শ্রেণির language-এ operation খাটালে ফলও সেই শ্রেণিতে থাকে। এই টেবিল পুরো কোর্সের একটি সারসংক্ষেপ, যা পরের মডিউলগুলোতে প্রমাণসহ ভরাট হবে; প্রতিটি সারির শেষে লেখা আছে কোন পর্বে। এখনই মুখস্থ করার দরকার নেই, পরে ফিরে এসে মিলিয়ে নিন।
| শ্রেণি | ∪ | ∩ | complement | concatenation | star | ∩ regular | যে পর্বে প্রমাণ |
|---|---|---|---|---|---|---|---|
| Regular | হ্যাঁ | হ্যাঁ | হ্যাঁ | হ্যাঁ | হ্যাঁ | হ্যাঁ | ০৮ (product, complement), ১৬ (সব) |
| CFL | হ্যাঁ | না | না | হ্যাঁ | হ্যাঁ | হ্যাঁ | ৩৭ (উদাহরণ ৩৬-এর aⁿbⁿcⁿ থেকে) |
| CSL | হ্যাঁ | হ্যাঁ | হ্যাঁ | হ্যাঁ | হ্যাঁ | হ্যাঁ | complement: ৬৬ (Immerman–Szelepcsényi); বাকিগুলো LBA দিয়ে, এই কোর্সে শুধু রূপরেখা |
| Decidable | হ্যাঁ | হ্যাঁ | হ্যাঁ | হ্যাঁ | হ্যাঁ | হ্যাঁ | ৫০ |
| Recognizable | হ্যাঁ | হ্যাঁ | না | হ্যাঁ | হ্যাঁ | হ্যাঁ | ৫০ (closure), ৫১ (complement-এর উদাহরণ) |
CFL-এর দুটি “না” এখনই বোঝা যায়। L1 = {anbncm} আর L2 = {ambncn} (n, m ≥ 0) দুটিই context-free, অথচ L1 ∩ L2 = {anbncn}, যা নয়। পূর্ণ যুক্তি অনুশীলন ৪-এ। আরেকটি সূক্ষ্মতা: deterministic CFL (পর্ব ৩৫) complement-এ closed, কিন্তু union-এ নয়; তাই “CFL” আর “DCFL”-এর সারি আলাদা।
Closure property শুধু তথ্য নয়, প্রমাণের একটি অস্ত্রও। ধরুন বাজারঘরের একটি নিয়ম: প্রতিটি combo-প্যাকে চাল (a), ডাল (b) আর তেল (c) সমান সংখ্যায়, যেকোনো ক্রমে। L = {w ∈ {a, b, c}∗ : #a(w) = #b(w) = #c(w)}। L কি CFL? সরাসরি pumping করার আগে একটি regular language দিয়ে কেটে নিন: L ∩ a∗b∗c∗ = {anbncn}। L যদি CFL হতো, তবে “∩ regular” সারির “হ্যাঁ” অনুযায়ী ফলটিও CFL হতো, যা নয় (পর্ব ৩৬)। তাই L context-free নয়। এই কৌশল, “একটি পরিচিত non-member-এ নামিয়ে আনা”, পরে reduction-এর আকারে আরও বড় রূপে ফিরবে (পর্ব ৫২)।
| প্রশ্ন | Regular (DFA) | CFL (CFG) | CSL (CSG) | Type 0 (TM) |
|---|---|---|---|---|
| w ∈ L? | decidable, O(n): ২০ | decidable, O(n3): ৩১ | decidable: এই পর্ব | undecidable: ৫১ |
| L = ∅? | decidable: ২০ | decidable: ৩৭ | undecidable (এই কোর্সে প্রমাণ নেই) | undecidable: ৫৩ |
| L1 = L2? | decidable: ২০ | undecidable: ৩৭, ৫৪ | undecidable | undecidable: ৫২ |
টেবিলের নিয়মটি লক্ষ করুন: ওপরে উঠলে প্রকাশের শক্তি বাড়ে, কিন্তু machine নিয়ে প্রশ্নের উত্তর দেওয়ার ক্ষমতা কমে। Regular-এ প্রায় সব প্রশ্নের উত্তর যান্ত্রিকভাবে মেলে; Type 0-এ প্রায় কোনোটির নয়।
৮ · বাস্তবে: regex, parser আর সাধারণ program
প্রোগ্রামারের জন্য hierarchy-র সবচেয়ে কাজের শিক্ষা: কাজটির জন্য যথেষ্ট, সবচেয়ে দুর্বল যন্ত্রটি বেছে নিন। দুর্বল যন্ত্র দ্রুত, তার আচরণ নিয়ে প্রশ্নের উত্তর দেওয়া যায়, আর ভুল কম হয়। বাজারঘরের তিনটি কাজে দেখা যাক।
| কাজ | স্তর | উপযুক্ত tool | ভুল tool-এর ঝুঁকি |
|---|---|---|---|
| অর্ডার কোড BG-0042, ৬ চিহ্নের কুপন | Type 3 | regular expression বা DFA | পূর্ণ parser লেখা অপ্রয়োজনীয় জটিলতা |
অর্ডার-query: (dal OR (chal AND tel)) | Type 2 | parser (পর্ব ৩৮–৪২) | regex দিয়ে nested বন্ধনী মেলানো যায় না |
| “এই discount script কি সব ইনপুটে থামবে?” | Type 0 | সাধারণ program, সঙ্গে timeout ও পরীক্ষা | সব ক্ষেত্রে সঠিক যাচাইকারী বানানো অসম্ভব (পর্ব ৫১, ৫৩) |
দুটি সতর্কতা। প্রথমত, Python, JavaScript বা PCRE-এর “regex” গণিতের regular expression-এর চেয়ে শক্তিশালী: backreference (a+)b\1 দিয়ে {anban}-এর মতো non-regular language চেনা যায়। এর দাম, backtracking engine-এ কিছু ইনপুটে সূচকীয় সময় লাগতে পারে (ReDoS, পর্ব ২১)। দ্বিতীয়ত, programming language-এর syntax মূলত CFG দিয়ে লেখা হয়, কিন্তু “ব্যবহারের আগে variable ঘোষণা” ধরনের নিয়ম context-free নয়; compiler তা grammar-এ নয়, পরের ধাপে (semantic analysis) যাচাই করে। Python-এর indentation-ও lexer আলাদা token বানিয়ে সামলায় (পর্ব ২২)। Compiler নির্মাণের গভীর আলোচনা পরিকল্পিত “Programming Languages & Compilers” কোর্সে আসবে।
আরও গভীরে: মানুষের ভাষার কিছু গঠন, যেমন Swiss German-এর cross-serial dependency, context-free নয় বলে Stuart Shieber ১৯৮৫ সালে যুক্তি দেন। Aravind Joshi একই বছর “mildly context-sensitive” শ্রেণির ধারণা প্রস্তাব করেন: CFL-এর একটু ওপরে, কিন্তু polynomial সময়ে parse করা যায়; tree-adjoining grammar এর প্রধান উদাহরণ। CSL-এর দিকে “প্রথম LBA সমস্যা” (deterministic LBA কি nondeterministic LBA-র সমান শক্তিশালী, অর্থাৎ SPACE(n) = NSPACE(n)?) Kuroda ১৯৬৪ সালে তোলেন, আর তা আজও খোলা। দ্বিতীয় LBA সমস্যা (CSL কি complement-এ closed?) ১৯৮৭–৮৮ সালে Immerman আর Szelepcsényi স্বাধীনভাবে “হ্যাঁ” প্রমাণ করেন।
পরীক্ষা ও ইন্টারভিউতে:
- চার type আর তাদের machine বলুন। 3: finite automaton, 2: PDA, 1: LBA, 0: Turing machine.
- S → aSb | ε কোন type? Type 2 (variable মাঝখানে, তাই 3 নয়; S → ε আর S ডানে, তাই grammar হিসেবে 1-ও নয়)। Language aⁿbⁿ, regular নয়।
- কোন শ্রেণি complement-এ closed নয়? CFL আর recognizable; regular, CSL আর decidable closed.
- Decidable কি একটি Chomsky type? না; এটি CSL আর type 0-এর মাঝখানে, machine-এর থামার আচরণ দিয়ে সংজ্ঞায়িত।
- প্রতিটি CSL কেন decidable? Noncontracting নিয়মে form ছোট হয় না, তাই |w| পর্যন্ত form-এর সসীম খোঁজই যথেষ্ট।
৯ · AI-এর যুগে: hierarchy নিয়ে AI-এর দাবি যাচাই
AI assistant এই টেবিলগুলো সাবলীলভাবে বলে দেয়, কিন্তু কয়েকটি ভুল বারবার দেখা যায়। ভুলগুলো সাধারণত শর্ত বাদ দেওয়ায়, বা grammar আর language গুলিয়ে ফেলায়।
| AI-এর দাবি | সমস্যা | যাচাইয়ের উপায় |
|---|---|---|
| “এই grammar type 2 নয়, তাই language context-free নয়” | Grammar-এর type শুধু ওপরের সীমা | Language-টির জন্য সরল grammar খুঁজুন, বা pumping প্রমাণ চান |
| “প্রতিটি নিয়ম linear, তাই regular” | Left আর right-linear মেশালে aⁿbⁿ আসে | Generator চালিয়ে ছোট string-গুলো দেখুন |
| “CFL intersection-এ closed” | শুধু regular-এর সঙ্গে intersection-এ closed | aⁿbⁿcᵐ ∩ aᵐbⁿcⁿ উদাহরণে মিলিয়ে দেখুন |
| “Decidable = Type 1” বা “Type 0 = decidable” | CSL ⊊ decidable ⊊ recognizable = Type 0 | উপপাদ্য ৫.২ আর ATM-এর উদাহরণ |
| “CSL ⊆ P” বা “P ≠ NP প্রমাণিত” | খোলা প্রশ্নকে মীমাংসিত বলা | Sipser বা Arora–Barak-এর মতো বিশ্বস্ত বইয়ে মিলিয়ে নিন |
AI-কে grammar-এর শ্রেণি জিজ্ঞেস করলে নিয়ম ধরে ধরে যুক্তি আর একটি যাচাইযোগ্য কোড চেয়ে নিন। একটি কাঠামো:
AI-এর উত্তর হাতে পেলে: যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Chomsky তো ভাষাবিদ ছিলেন, কম্পিউটার বিজ্ঞানী নন। তাঁর hierarchy কীভাবে programming language আর compiler-এর ভিত্তি হয়ে উঠল?
Noam Chomsky-র প্রশ্ন ছিল মানুষের ভাষা নিয়ে: একজন বক্তা কীভাবে সসীম জ্ঞান দিয়ে অসীম সংখ্যক নতুন বাক্য বলতে আর বুঝতে পারেন? ১৯৫৬ সালের প্রবন্ধে তিনি তিনটি মডেল তুলনা করেন: finite-state মডেল, phrase-structure grammar আর transformational grammar. তাঁর একটি বিখ্যাত যুক্তি ছিল, ইংরেজির কিছু গঠন (যেমন “if … then …” এর ভেতরে আরেকটি “if … then …”, যত খুশি গভীরে) কোনো finite-state মডেল ধরতে পারে না, কারণ মেলানোর জন্য সীমাহীন গোনা লাগে। এটি আসলে এই পর্বের aⁿbⁿ যুক্তির ভাষাতাত্ত্বিক রূপ। ১৯৫৭ সালের বই Syntactic Structures-এ এই ধারণাগুলো বৃহত্তর পাঠকের কাছে পৌঁছায়।
প্রায় একই সময়ে কম্পিউটার বিজ্ঞানীরা প্রথম উচ্চস্তরের programming language-এর বর্ণনা লিখছিলেন। John Backus ১৯৫৯ সালে ALGOL-এর syntax লেখার জন্য একটি notation প্রস্তাব করেন, আর Peter Naur ১৯৬০ সালের ALGOL 60 প্রতিবেদনে তা ব্যবহার করেন; পরে এর নাম হয় BNF (Backus–Naur Form). ১৯৬০-এর দশকের শুরুতে Ginsburg আর Rice-এর মতো গবেষকেরা দেখান যে BNF-এ লেখা syntax ঠিক context-free grammar-এর শ্রেণি। ফলে Chomsky-র type 2 হঠাৎ করে programming language-এর মানক ভাষা হয়ে দাঁড়াল।
এর পরের কয়েক দশকে ঘটনাগুলো দ্রুত এগোয়: CFG-এর জন্য দক্ষ parsing algorithm (Knuth ১৯৬৫ সালে LR parsing), lexer-এর জন্য regular expression আর DFA, আর yacc-এর মতো parser generator. আজ প্রায় প্রতিটি compiler দুটি স্তরে কাজ করে: Type 3 দিয়ে lexer (পর্ব ২২), Type 2 দিয়ে parser (পর্ব ৩৮–৪০)।
মজার ব্যাপার, ভাষাতত্ত্বে Chomsky নিজে পরে অন্য দিকে চলে যান, আর মানুষের ভাষা ঠিক কোন শ্রেণির, সেই প্রশ্নটি নিয়ে বিতর্ক চলতে থাকে। কিন্তু তাঁর শ্রেণিবিভাগ কম্পিউটার বিজ্ঞানে টিকে যায়, কারণ এটি একটি পরিষ্কার প্রকৌশল প্রশ্নের উত্তর দেয়: এই syntax চিনতে কত স্মৃতি লাগবে?
মূল উপলব্ধি: একটি গাণিতিক কাঠামো এক ক্ষেত্রের প্রশ্ন থেকে জন্ম নিয়ে অন্য ক্ষেত্রে বেশি কাজে লাগতে পারে। Hierarchy-র শক্তি তার বিমূর্ততায়: এটি বাক্য বা program নয়, শুধু “নিয়মের আকার আর স্মৃতির ধরন” নিয়ে কথা বলে।
প্র ০২Decidable language-এর শ্রেণি hierarchy-র মাঝখানে বসে, অথচ কোনো grammar-type দিয়ে তাকে ধরা যায় না কেন?
Chomsky-র প্রতিটি type একটি বাক্যগঠনগত শর্ত: নিয়মটি দেখে, কোনো কিছু না চালিয়েই, বলা যায় শর্ত মানে কি না। এই পর্বের classifier ঠিক তা-ই করে, এবং সবসময় থামে। তাই প্রতিটি type-এর grammar-গুলোর একটি কার্যকর তালিকা বানানো যায়: সব string ⟨G⟩ shortlex-এ দেখুন, শর্ত মানলে রাখুন।
এবার ধরুন কোনো grammar-শর্ত X ঠিক decidable language-গুলোর grammar দেয়, আর X যাচাই করা যায়। তাহলে সব X-grammar-এর তালিকা G1, G2, … আছে, এবং প্রতিটির language decidable. কিন্তু শুধু এটুকু যথেষ্ট নয়; উপপাদ্য ৫.২-এর diagonal চালাতে লাগে একটিমাত্র algorithm, যা যেকোনো i আর w-এর জন্য w ∈ L(Gi) decide করে। CSL-এর বেলায় সেটি আছে (noncontracting খোঁজ)। যদি X-এর জন্যও এমন একটি সর্বজনীন decider থাকত, তবে diagonal D একটি decidable language হতো, যা কোনো X-grammar তৈরি করে না: স্ববিরোধ। অর্থাৎ decidable language-এর শ্রেণির কোনো “ভালো” বর্ণনা থাকতে পারে না, যার সদস্যপদ একটি algorithm সবার জন্য একসঙ্গে যাচাই করে।
Machine-এর দিক থেকেও একই কথা: “এই TM কি সব ইনপুটে থামে?” প্রশ্নটি decidable নয় (পর্ব ৫১–৫৩-এর পদ্ধতিতে প্রমাণ করা যায়), তাই decider-দের তালিকা কোনো program বানাতে পারে না। Recognizer-দের তালিকা অবশ্য বানানো যায়, কারণ প্রতিটি TM-ই কোনো না কোনো language-এর recognizer. এই অসাম্যই ব্যাখ্যা করে কেন Type 0 একটি grammar-শ্রেণি, কিন্তু decidable নয়।
Complexity তত্ত্বও এই কাঠামো ব্যবহার করে। P-এর মতো শ্রেণিকে আমরা “কোনো polynomial-এর সময়-সীমায় থামানো machine” দিয়ে লিখি, যাতে সীমাটি machine-এর বর্ণনার ভেতরেই থাকে; তখন তালিকা বানানো যায়, আর পর্ব ৬৭-এর hierarchy theorem-এর diagonal কাজ করে।
মূল উপলব্ধি: একটি language-শ্রেণির একটি “যাচাইযোগ্য বর্ণনা” আর “সব সদস্যের জন্য এক decider” একসঙ্গে থাকলে diagonal তার বাইরে একটি decidable language দেয়। Decidable শ্রেণি নিজে তাই কখনো এমন সুন্দর বর্ণনা পায় না।
প্র ০৩LBA-র দুটি পুরোনো সমস্যা: একটি ২০ বছরেরও বেশি পরে সমাধান হলো, আরেকটি আজও খোলা। এর পেছনের গল্প কী?
John Myhill ১৯৬০ সালে linear bounded automaton-এর ধারণা দেন, deterministic রূপে। Peter Landweber ১৯৬৩ সালে দেখান যে deterministic LBA-র language context-sensitive, আর S.-Y. Kuroda ১৯৬৪ সালে প্রমাণ করেন যে nondeterministic LBA ঠিক context-sensitive language চেনে। একই প্রবন্ধে Kuroda দুটি প্রশ্ন রেখে যান, যা “LBA সমস্যা” নামে পরিচিত।
প্রথম প্রশ্ন: deterministic LBA কি nondeterministic LBA-র সমান শক্তিশালী? Complexity-র ভাষায় SPACE(n) = NSPACE(n)? দ্বিতীয় প্রশ্ন: CSL কি complement-এ closed? অর্থাৎ একটি LBA যদি L চেনে, তবে L-এর বাইরের string চেনার কোনো LBA আছে কি? প্রথমটির “হ্যাঁ” উত্তর দ্বিতীয়টির উত্তরও দিত, কারণ deterministic machine-এর accept আর reject অদলবদল করলেই complement পাওয়া যায়।
দ্বিতীয় প্রশ্নটি প্রায় ২৩ বছর খোলা ছিল। ১৯৮৭–৮৮ সালে Neil Immerman আর Róbert Szelepcsényi স্বাধীনভাবে প্রমাণ করেন যে nondeterministic space-এর শ্রেণিগুলো (s(n) ≥ log n হলে) complement-এ closed: NSPACE(s) = coNSPACE(s). কৌশলটি “inductive counting”: একটি nondeterministic machine প্রথমে গুনে নেয় শুরু থেকে ঠিক কয়টি configuration-এ পৌঁছানো যায়, তারপর সেই সংখ্যা ব্যবহার করে নিশ্চিতভাবে দেখায় কোনো accepting configuration তাদের মধ্যে নেই। ফলাফলের একটি বিশেষ রূপ NL = coNL, যা পর্ব ৬৬-এ দেখবেন। এই কাজের জন্য দুজন ১৯৯৫ সালে Gödel Prize পান।
প্রথম প্রশ্নটি আজও খোলা। Savitch-এর theorem (১৯৭০) দেখায় NSPACE(n) ⊆ SPACE(n2), অর্থাৎ nondeterminism সরাতে জায়গা বড়জোর বর্গ হয়, কিন্তু linear-এ রাখা যায় কি না কেউ জানে না। এটি L বনাম NL প্রশ্নের আত্মীয়, যা-ও খোলা।
মূল উপলব্ধি: Hierarchy-র “নিরীহ” স্তরগুলোতেও গভীর খোলা প্রশ্ন লুকিয়ে আছে। আর একটি সমস্যার সমাধান অনেক সময় নতুন কৌশল (এখানে inductive counting) নিয়ে আসে, যা মূল প্রশ্নের চেয়ে বড় হয়ে ওঠে।
প্র ০৪Programming language-কে “context-free” বলা হয়, অথচ compiler grammar-এর বাইরেও অনেক নিয়ম যাচাই করে। তাহলে কোন অংশ আসলে কোন স্তরে?
একটি সাধারণ compiler-এ কাজ কয়েক ধাপে ভাগ হয়। প্রথমে lexer অক্ষরের স্রোতকে token-এ ভাঙে: identifier, সংখ্যা, keyword, operator. প্রতিটি token-এর ফরম্যাট regular, আর lexer generator সেগুলো থেকে একটি DFA বানায় (পর্ব ২২)। তারপর parser token-এর ক্রম একটি CFG দিয়ে যাচাই করে, আর একটি syntax tree বানায় (পর্ব ৩৮–৪২)। এরপর semantic analysis: variable ঘোষিত কি না, type মিলছে কি না, function-এ ঠিক সংখ্যক argument দেওয়া হয়েছে কি না।
শেষ ধাপের নিয়মগুলো সাধারণত context-free নয়। “ব্যবহারের আগে ঘোষণা” মোটামুটি {w x w}-এর মতো একটি গঠন চায়: একটি নাম একবার ঘোষণায়, আবার পরে ব্যবহারে, হুবহু একই। এ ধরনের “কপি” language ({ww}) context-free নয়, যা পর্ব ৩৬-এর pumping lemma দিয়ে প্রমাণ করা যায়। তাই compiler এই নিয়মগুলো grammar-এ রাখে না; symbol table নামের একটি সাধারণ data structure দিয়ে যাচাই করে, যা কার্যত Type 0-এর শক্তির একটি ছোট, নিয়ন্ত্রিত ব্যবহার।
কিছু ভাষায় parsing নিজেই প্রসঙ্গ চায়। C-তে T * x; একটি গুণ, নাকি pointer ঘোষণা, তা নির্ভর করে T আগে typedef হিসেবে ঘোষিত কি না তার ওপর; বাস্তব C compiler তাই lexer আর parser-এর মধ্যে তথ্য আদানপ্রদান করে। Python-এর indentation-ও শুদ্ধ CFG দিয়ে সরাসরি লেখা কঠিন; lexer একটি stack রেখে INDENT আর DEDENT token বানায়, তারপর grammar context-free থাকে।
অর্থাৎ “programming language context-free” কথাটি একটি সুবিধাজনক সরলীকরণ: syntax-এর মূল কাঠামো CFG, আর তার ওপর কিছু বাড়তি নিয়ম অন্য কৌশলে। এই বিভাজনই বাস্তব প্রকৌশল: প্রতিটি নিয়মের জন্য সবচেয়ে দুর্বল যথেষ্ট যন্ত্র।
মূল উপলব্ধি: একটি বাস্তব ভাষা একাধিক স্তর জুড়ে থাকে। Hierarchy আপনাকে বলে কোন অংশ কোন যন্ত্রে সামলানো উচিত, আর কোন অংশ grammar-এ জোর করে ঢোকালে জটিলতা বা ভুল বাড়বে।
প্র ০৫বাস্তবের regex গণিতের regular expression-এর চেয়ে শক্তিশালী। এই বাড়তি শক্তির দাম কী, আর “least power” নীতি কেন গুরুত্বপূর্ণ?
Stephen Kleene ১৯৫০-এর দশকে regular expression-এর ধারণা দেন, আর ১৯৬০-এর দশকের শেষে Ken Thompson text editor-এ regex খোঁজার জন্য একটি automaton-ভিত্তিক পদ্ধতি প্রকাশ করেন (পর্ব ১৪-এর Thompson construction). গাণিতিক regex-এ শুধু union, concatenation আর star; এর language সবসময় regular, আর DFA দিয়ে ইনপুটের দৈর্ঘ্যের রৈখিক সময়ে মেলানো যায়।
পরে Perl-এর মতো ভাষায় regex-এ নতুন সুবিধা যোগ হয়, বিশেষ করে backreference: \1 মানে “আগে প্রথম বন্ধনী যা মিলিয়েছিল, হুবহু তা-ই”। এতে regular-এর বাইরের language চেনা যায়, যেমন একটি শব্দ পরপর দুবার। দাম দুই রকম। তাত্ত্বিক দাম: Alfred Aho-র একটি পরিচিত ফল অনুযায়ী backreference-সহ regex মেলানোর সাধারণ সমস্যা NP-complete, তাই দ্রুত সাধারণ algorithm আশা করা হয় না। ব্যবহারিক দাম: এমন সুবিধা সমর্থন করতে বেশিরভাগ engine backtracking ব্যবহার করে, আর তাতে backreference ছাড়া সাধারণ pattern-এও কিছু ইনপুটে সূচকীয় সময় লাগতে পারে। এটাই ReDoS (পর্ব ২১)। Google-এর RE2-এর মতো engine ইচ্ছা করে backreference বাদ দেয়, যাতে রৈখিক সময়ের নিশ্চয়তা থাকে।
Tim Berners-Lee “rule of least power” নামে একটি নীতির কথা লিখেছেন: কোনো তথ্য প্রকাশের জন্য যথেষ্ট সবচেয়ে কম শক্তিশালী ভাষা বেছে নিন, কারণ দুর্বল ভাষার লেখা বিশ্লেষণ, যাচাই আর পুনর্ব্যবহার সহজ। Chomsky hierarchy এই নীতির গাণিতিক রূপ। একটি ফরম্যাট regular হলে তার জন্য equivalence, emptiness, inclusion সব প্রশ্নের উত্তর যান্ত্রিকভাবে মেলে (পর্ব ২০); একই কাজ একটি সাধারণ program-এ লিখলে সেই প্রশ্নগুলো undecidable হয়ে যায় (পর্ব ৫৩)।
বাজারঘরের অর্ডার কোড যাচাই তাই একটি সাধারণ regex বা DFA দিয়ে করাই ভালো; অর্ডার-query-র nested বন্ধনী একটি parser দিয়ে; আর শুধু যেখানে সত্যিই দরকার, সেখানে সাধারণ program.
মূল উপলব্ধি: প্রকাশের শক্তি আর বিশ্লেষণের সহজতা একে অপরের বিপরীতে টানে। সবচেয়ে দুর্বল যথেষ্ট যন্ত্রটি বেছে নেওয়া শুধু তাত্ত্বিক রুচি নয়, নিরাপত্তা আর গতির নিশ্চয়তা।
অনুশীলন
খাতা-কলমে সমাধান করুন, তারপর উত্তর মেলান। ওপরের Python ব্লকে নিজের grammar বসিয়েও যাচাই করতে পারেন।
-
Grammar থেকে NFA নকশা: {0, 1}-এর ওপর যে string-গুলো 01 দিয়ে শেষ হয়, তাদের জন্য একটি type 3 (right-linear) grammar লিখুন। তারপর অংশ ৩-এর construction দিয়ে NFA বানান, আর ইনপুট 1001-এ প্রতিটি চিহ্নের পর NFA-র state-এর set লিখুন।
Grammar: S → 0S | 1S | 0A, A → 1. S “যেকোনো prefix” পড়ে, শেষে 0A আর A → 1 মিলে 01. NFA: state {S, A, f}, শুরু S, F = {f}; δ(S, 0) = {S, A}, δ(S, 1) = {S}, δ(A, 1) = {f}, বাকি সব ∅।
1001-এ: শুরু {S}; 1 পড়ে {S}; 0 পড়ে {S, A}; 0 পড়ে {S, A} (A থেকে 0-তে কোথাও যাওয়া নেই, S থেকে আবার S আর A); 1 পড়ে {S, f}। শেষ set-এ f আছে, তাই গৃহীত, আর সত্যিই 1001 শেষ হয় 01 দিয়ে। এই NFA scratch script-এ দৈর্ঘ্য ১০ পর্যন্ত সব string-এ “01 দিয়ে শেষ” সংজ্ঞার সঙ্গে মিলেছে।
-
ভুল প্রমাণটি ধরুন: “দাবি: G: S → aT, T → Sb | b-এর language regular. প্রমাণ: right-linear grammar regular language দেয়, left-linear grammar-ও দেয়। G-এর প্রতিটি নিয়মে বড়জোর একটি variable, আর সেটি হয় শেষে, নয় শুরুতে। তাই প্রতিটি নিয়ম right-linear বা left-linear, অতএব language regular. ∎” ভুলটি কোথায়?
উপপাদ্যগুলো বলে একটি grammar-এর সব নিয়ম right-linear হলে, অথবা সব নিয়ম left-linear হলে, language regular. প্রমাণটি “প্রতিটি নিয়ম দুটির কোনো একটি” থেকে “grammar দুটির কোনো একটি” সিদ্ধান্তে লাফ দিয়েছে; quantifier-এর ক্রম বদলে গেছে। G-তে S → aT right-linear আর T → Sb left-linear, আর এই মিশ্রণ S ⇒ aT ⇒ aSb ⇒ aaTb ⇒ aabb-এর মতো derivation দিয়ে দুই দিক থেকে একসঙ্গে বাড়ে। L(G) = {anbn : n ≥ 1}, যা regular নয় (পর্ব ১৭)। অংশ ৪-এর generator দৈর্ঘ্য ৮ পর্যন্ত ঠিক ab, aabb, aaabbb, aaaabbbb দেখায়।
-
Classifier-এর আউটপুট অনুমান করুন: G: S → AB, AB → BA, A → a, B → b. অংশ ২-এর classifier কোন type-এর তালিকা দেবে, আর L(G) কী? Language-টি আসলে কোন শ্রেণির?
AB → BA-এর বাঁ দিকে দুটি চিহ্ন, তাই type 2 বা 3 নয়। প্রতিটি নিয়মে |α| ≤ |β| (1 ≤ 2, 2 ≤ 2, 1 ≤ 1), তাই type 1. আউটপুট:
types [1, 0] -> most restrictive: type 1, যা scratch-এ চালিয়ে মিলেছে।Derivation: S ⇒ AB ⇒ ab, অথবা S ⇒ AB ⇒ BA ⇒ ba. তাই L(G) = {ab, ba}। এটি একটি সসীম language, তাই regular (Type 3). আরেকবার: grammar-এর type 1, কিন্তু language-এর শ্রেণি 3; S → ab | ba-এর মতো type 3 grammar-ও আছে।
-
প্রমাণ করুন: CFL intersection-এ closed নয়, আর তা থেকে দেখান যে complement-এও closed নয়। (ধরে নিন {anbncn : n ≥ 0} context-free নয়, যা পর্ব ৩৬-এ প্রমাণ হবে।)
(১) L1 = {anbncm : n, m ≥ 0} তৈরি করে S → XC, X → aXb | ε, C → cC | ε; L2 = {ambncn : n, m ≥ 0} তৈরি করে S → AY, A → aA | ε, Y → bYc | ε. দুটিই CFG, তাই দুটিই CFL.
(২) w ∈ L1 ∩ L2 হলে w = aibjck আকারের, আর L1 থেকে i = j, L2 থেকে j = k. তাই L1 ∩ L2 = {anbncn}, যা CFL নয়। অতএব CFL intersection-এ closed নয়।
(৩) ধরি CFL complement-এ closed. CFL union-এ closed (নতুন S → S1 | S2), তাই De Morgan-এর সূত্রে L1 ∩ L2 = complement(complement(L1) ∪ complement(L2)) হতো CFL, যা (২)-এর বিপরীত। অতএব complement-এ-ও closed নয়। ∎ দুটি grammar আর intersection-টি scratch-এ দৈর্ঘ্য ৭ পর্যন্ত brute force-এ যাচাই করা হয়েছে।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমনিচের language-শ্রেণিগুলো সবচেয়ে ছোট থেকে সবচেয়ে বড় ক্রমে সাজান (▲▼ চেপে সরান)
- Regular (Type 3)
- Context-free (Type 2)
- Context-sensitive (Type 1)
- Decidable
- Turing-recognizable (Type 0)
Chomsky hierarchy-তে Type 1 (context-sensitive) language ঠিক কোন machine চেনে?
- Pushdown automaton
- Finite automaton
- Linear bounded automaton
- সীমাহীন tape-এর Turing machine
G: S → aSb | ε. এই grammar-এর (language নয়) সবচেয়ে কড়া Chomsky type কোনটি?
- Type 3
- Type 2
- Type 1
- শুধু Type 0
নিচের কোন language-শ্রেণি complement-এ closed নয়?
- Regular language
- Context-sensitive language
- Decidable language
- Context-free language
কোন language context-free শ্রেণিকে context-sensitive শ্রেণি থেকে আলাদা করে, অর্থাৎ CSL কিন্তু CFL নয়?
- {aⁿbⁿcⁿ : n ≥ 1}
- {aⁿbⁿ : n ≥ 1}
- জোড় সংখ্যক 1-এর binary string
- ATM
Decidable language-এর শ্রেণি সম্পর্কে কোন বক্তব্যটি সঠিক?
- এটি Chomsky-র Type 1
- এটি Chomsky-র Type 0-এর সমান
- এটি CSL-এর চেয়ে কঠোরভাবে বড়, recognizable-এর চেয়ে কঠোরভাবে ছোট
- এটি ঠিক context-free language-এর শ্রেণি
G: S → aT, T → Sb | b. L(G) কী, আর তা কোন শ্রেণির?
- a∗b∗, regular
- {aⁿbⁿ : n ≥ 1}, context-free কিন্তু regular নয়
- {aⁿbⁿ : n ≥ 1}, context-sensitive কিন্তু context-free নয়
- {aⁿbⁿ : n ≥ 1}, regular, কারণ প্রতিটি নিয়ম linear
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসঙ্গে:
মনে রাখুন
- Grammar G = (V, Σ, R, S), L(G) = {w ∈ Σ∗ : S ⇒∗ w}; নিয়মের আকারে চার type: 3 A → aB ∣ a ∣ ε, 2 A → β, 1 |α| ≤ |β|, 0 যেকোনো।
- Machine: DFA/NFA, PDA, LBA, TM; পার্থক্য স্মৃতিতে: state, stack, ইনপুটের সমান tape, সীমাহীন tape.
- REG ⊊ CFL ⊊ CSL ⊊ DECIDABLE ⊊ RECOGNIZABLE; আলাদা করে aⁿbⁿ (১৭), aⁿbⁿcⁿ (৩৬), diagonal D (এই পর্ব, ৬৭), ATM (৫১)।
- Decidable কোনো Chomsky type নয়; Type 0 = recognizable. Grammar-এর type language-এর শ্রেণির শুধু ওপরের সীমা।
- CFL ∩ আর complement-এ closed নয়, recognizable complement-এ নয়; ওপরে উঠলে প্রকাশের শক্তি বাড়ে, decidable প্রশ্ন কমে।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্বপুরো কোর্সের মানচিত্র; পরের পর্ব ০৭ “DFA — formal definition, transition আর language গ্রহণ”.
- পর্ব ০৫ · সমস্যাকে language হিসেবে দেখাআগের পর্বEncoding ⟨G⟩, ⟨M, w⟩ আর decision problem, যা diagonal প্রমাণে লাগে।
- Discrete Mathematics · পর্ব ৭৩ · Grammar আর languageভিত্তিPhrase-structure grammar, BNF, derivation tree আর hierarchy-র প্রথম পরিচয়।
- Discrete Mathematics · পর্ব ৭৫ · Turing machine-এর পরিচয়ভিত্তিTape, head আর configuration-এর সহজ পরিচয়।
- DSA · পর্ব ৬৪ · P বনাম NPপাশের ট্র্যাকAlgorithm-এর দিক থেকে NP-hardness আর P বনাম NP প্রশ্ন।