এই পর্বে যা শিখবেন
- CFG-এর formal definition, এক ধাপের ⇒, বহু ধাপের ⇒∗, আর L(G)-এর অর্থ
- BNF আর EBNF পড়া ও লেখা, আর বাজারঘরের order-query ভাষার ছোট grammar
- পাঁচটি মানক উদাহরণ আর বর্ণনা থেকে নিজে CFG নকশা করার তিনটি কৌশল
- একটি grammar ঠিক কোন language তৈরি করে, তার দুই দিকের পূর্ণ প্রমাণ লেখা
- Regular grammar কেন CFG-এর বিশেষ রূপ, আর union, concatenation, star-এর grammar গঠন
১ · কেন grammar — বন্ধনী, নেস্টিং আর recursion
মডিউল ২ থেকে ৪ পর্যন্ত আপনি finite automaton আর regular expression দিয়ে অনেক কিছু চিনেছেন: বাজারঘরের BG-0042 ধাঁচের order code, কুপনের ফরম্যাট, sensor লাইনের parity. কিন্তু পর্ব ১৭-এ একটি দেয়ালে ধাক্কা লেগেছিল। anbn = {ε, ab, aabb, …} আর সুষম বন্ধনীর language BAL, কোনোটিই regular নয়। কারণ একটাই: যন্ত্রের স্মৃতি সসীম, অথচ এই ভাষাগুলোতে কতগুলো a বা কতগুলো খোলা বন্ধনী জমেছে, সেটি যেকোনো বড় সংখ্যা হতে পারে।
স্কুলের গণিত খাতার কথা ভাবুন: [২ × {৩ + (৪ − ১)}]. শিক্ষক শিখিয়েছিলেন, আগে প্রথম বন্ধনী, তারপর দ্বিতীয়, তারপর তৃতীয়। প্রতিটি খোলা বন্ধনীর একটি জোড়া থাকতে হয়, আর জোড়াগুলো একটির ভেতরে আরেকটি বসে, কখনো আড়াআড়ি কাটে না। এই নিয়মটি মুখে বলা খুব সহজ: “একটি সঠিক হিসাব মানে একটি সংখ্যা, অথবা বন্ধনীর ভেতরে একটি সঠিক হিসাব, অথবা দুটি সঠিক হিসাবের মাঝে একটি চিহ্ন।” লক্ষ করুন, সংজ্ঞার ভেতরেই “সঠিক হিসাব” শব্দটি আবার এসেছে। এটিই recursion, আর grammar এই recursion-কে নিয়মে লেখার ভাষা।
Regular expression-এ যা আছে তা হলো union, concatenation আর star. Star “যতবার ইচ্ছা পুনরাবৃত্তি” লেখে, কিন্তু “বাঁ দিকে যতবার, ডান দিকেও ঠিক ততবার” লিখতে পারে না। দুই পাশের গোনা মেলাতে হলে এমন একটি নিয়ম দরকার, যা একসঙ্গে বাঁয়ে একটি a আর ডানে একটি b বসায়, আর মাঝখানে আবার নিজেকেই ডাকে:
S থেকে শুরু করে প্রতিবার S-এর জায়গায় aSb লিখলে বাঁয়ে-ডানে একটি করে চিহ্ন বাড়ে, আর শেষে S-কে ε (ফাঁকা string) দিয়ে মুছে ফেললে পাওয়া যায় anbn. দুই পাশের মিল নিয়মের গঠনেই বাঁধা, কোনো গোনার যন্ত্র লাগে না। এই ধরনের grammar-কেই বলে context-free grammar (CFG), আর এর তৈরি language-গুলোই context-free language (CFL). পর্ব ০৬-এ আপনি Chomsky hierarchy-র Type 2 হিসেবে এদের দেখেছেন; এই মডিউলে সেই স্তরটি ভেতর থেকে খুলে দেখা হবে।
CFG কেন এত গুরুত্বপূর্ণ? কারণ প্রায় প্রতিটি programming language, JSON, HTML-এর কাঠামো, SQL-এর মতো query ভাষা আর গাণিতিক expression-এর syntax একটি CFG দিয়ে লেখা হয়। Compiler বা interpreter-এর যে অংশ code পড়ে তার কাঠামো বোঝে, সেই parser আসলে একটি CFG-এর প্রয়োগ। বাজারঘরের ছোট order-query ভাষাও এর ব্যতিক্রম নয়: শর্তগুলো AND, OR আর বন্ধনী দিয়ে যত গভীরে ইচ্ছা নেস্ট করা যায়, তাই এর syntax কোনো regex দিয়ে পুরোপুরি যাচাই করা যায় না, কিন্তু একটি ছোট CFG দিয়ে যায় (অংশ ৩)।
এই মডিউলের notation: CFG G = (V, Σ, R, S); বড় হাতের অক্ষর (S, A, B, E) variable, ছোট হাতের অক্ষর, অঙ্ক, বন্ধনী আর উদ্ধৃতির ভেতরের শব্দ terminal. একই বাঁ দিকের কয়েকটি নিয়ম একসঙ্গে লেখা হয় A → α ∣ β (“অথবা”)। ⇒ মানে এক ধাপ, ⇒∗ মানে শূন্য বা বেশি ধাপ। ফাঁকা string সবসময় ε; কিছু বইয়ে λ লেখা হয়। এই পর্ব বাকি মডিউলের ভিত্তি; derivation আর parse tree-র বিস্তারিত আসবে পর্ব ২৬-এ।
২ · Formal definition — G = (V, Σ, R, S) আর L(G)
পর্ব ০৬-এ সাধারণ grammar-এর সংজ্ঞা এসেছিল, যেখানে নিয়মের বাঁ দিকে যেকোনো string থাকতে পারত। Context-free grammar সেই সংজ্ঞার একটি সংকীর্ণ রূপ: বাঁ দিকে ঠিক একটি variable.
একটি context-free grammar হলো চারটি জিনিসের একটি tuple G = (V, Σ, R, S), যেখানে
১. V একটি সসীম set, যার উপাদানকে বলে variable (nonterminal);
২. Σ একটি সসীম set, V-এর সঙ্গে কোনো মিল নেই (V ∩ Σ = ∅), যার উপাদানকে বলে terminal;
৩. R হলো নিয়মের (production) সসীম set, প্রতিটি নিয়ম A → α আকারের, যেখানে A ∈ V আর α ∈ (V ∪ Σ)∗;
৪. S ∈ V হলো start symbol.
প্রতিটি অংশ কথায়: V হলো “এখনো বদলাতে হবে” এমন চিহ্নের ভাণ্ডার, Σ হলো আসল language-এর alphabet, R হলো প্রতিস্থাপনের নিয়মের তালিকা, আর S হলো যেখান থেকে সব শুরু। α = ε-ও চলে, যেমন S → ε; এমন নিয়মকে বলে ε-নিয়ম। “Context-free” নামের অর্থ: A-কে α দিয়ে বদলানোর সময় A-এর আশপাশে কী আছে (তার “প্রসঙ্গ”) দেখার দরকার নেই। A যেখানেই থাকুক, যেকোনো সময় বদলানো যায়।
u, v ∈ (V ∪ Σ)∗ হলে u ⇒ v (“u থেকে এক ধাপে v”) মানে u = xAy আর v = xαy, যেখানে A → α ∈ R আর x, y ∈ (V ∪ Σ)∗. u ⇒∗ v মানে একটি ক্রম u = u0 ⇒ u1 ⇒ ⋯ ⇒ uk = v আছে, কোনো k ≥ 0-এর জন্য; k = 0 হলে u = v. G যে language তৈরি করে:
L(G) = { w ∈ Σ∗ : S ⇒∗ w }
একটি language L context-free, যদি কোনো CFG G-এর জন্য L = L(G).
⇒∗ হলো ⇒-এর reflexive-transitive closure: শূন্য ধাপ (reflexive) আর ধাপের পর ধাপ জোড়া (transitive). ক্রমটির প্রতিটি সদস্য একটি sentential form, আর পুরো ক্রমটি একটি derivation. খেয়াল করুন, L(G)-এ শুধু সেই string ঢোকে, যাতে কোনো variable বাকি নেই। aSb একটি sentential form, কিন্তু L(G)-এর সদস্য নয়। আবার এমন variable-ও থাকতে পারে, যা থেকে কোনো terminal string-এ পৌঁছানো যায় না; সেই পথগুলো কোনো string দেয় না (এমন “অকেজো” চিহ্ন সরানোর কৌশল পর্ব ২৮-এ)।
একটি পূর্ণ উদাহরণ লিখি। সুষম বন্ধনীর grammar GBAL = ({S}, {(, )}, R, S), যেখানে R-এ দুটি নিয়ম: S → (S)S আর S → ε. নিয়মটি পড়ার উপায়: “একটি সুষম string হয় ফাঁকা, নয়তো একটি খোলা বন্ধনী, তার ভেতরে একটি সুষম string, একটি বন্ধ বন্ধনী, তারপর আরেকটি সুষম string”. প্রথম “(” যে “)”-এর সঙ্গে জোড়া বাঁধে, সেটিই এই ভাঙনের কেন্দ্র। নিচের stepper “(())()” string-টি derive করে, প্রতিবার সবচেয়ে বাঁয়ের S বদলে। এভাবে প্রতিবার সবচেয়ে বাঁয়ের variable বদলালে তাকে বলে leftmost derivation.
1S → (S)S2S → ε
| sentential form | |
| বদলানো S | |
| terminal / variable |
- প্রথম ধাপ। S → (S)S খাটানো হলো: S ⇒ (S)S. ভেতরের S বাইরের জোড়ার ভেতরের অংশ লিখবে, আর শেষের S জোড়ার পরের অংশ।
- নেস্টিং। সবচেয়ে বাঁয়ের S বন্ধনীর ভেতরে। আবার S → (S)S: ((S)S)S. এখন দুটি জোড়া একটির ভেতরে আরেকটি, ঠিক “(())”-এর শুরু।
- মুছে ফেলা। সবচেয়ে ভেতরের S-কে ε দিয়ে বদলানো হলো: (()S)S. ভেতরের জোড়াটি এখন ফাঁকা, অর্থাৎ “()”।
- প্রথম অংশ শেষ। পরের S-ও ε: (())S. বাইরের জোড়াটির ভেতরের অংশ সম্পূর্ণ; বাকি শুধু শেষের S, যা “(())”-এর পরের অংশ লিখবে।
- দ্বিতীয় জোড়া। শেষের S → (S)S: (())(S)S. লক্ষ করুন, প্রতিটি (S)S একসঙ্গে একটি “(” আর একটি “)” বসায়, তাই terminal-সংখ্যা সবসময় জোড়।
- জোড়াটি ফাঁকা। বাঁয়ের S → ε: (())()S. Variable বাকি একটি।
- শেষ। শেষ S → ε: (())(). কোনো variable নেই, তাই এটি L(GBAL)-এর সদস্য। মোট ৭টি ধাপ: (S)S তিনবার, ε চারবার; প্রতিটি (S)S একটি S-কে দুটি করে, তাই শেষে ৩ + ১ = ৪টি S মুছতে হয়।
একই derivation-কে একটি গাছ হিসেবেও আঁকা যায়: প্রতিটি নিয়ম-প্রয়োগ একটি node, যার সন্তানরা নিয়মের ডান দিকের চিহ্ন। গাছের পাতাগুলো বাঁ থেকে ডানে পড়লে মূল string ফিরে আসে। এই parse tree পর্ব ২৬-এর মূল বিষয়; এখানে শুধু ছবিটি দেখে রাখুন, কারণ নকশার সময় “গাছের আকার কেমন হবে” ভাবলে নিয়ম খুঁজে পাওয়া সহজ হয়।
(())()-এর parse tree
নীল বৃত্ত variable S, সবুজ terminal বন্ধনী, ধূসর ε. প্রতিটি S-এর চারটি সন্তান “( S ) S” অথবা একটি ε. পাতাগুলো বাঁ থেকে ডানে: ( ( ) ) ( ).
৩ · BNF আর EBNF — grammar লেখার প্রচলিত রীতি
গণিতের বইয়ে CFG লেখা হয় A → α দিয়ে, কিন্তু programming language-এর manual, RFC বা parser generator-এর file-এ প্রায়ই অন্য রীতি দেখবেন। সবচেয়ে পরিচিত রীতি BNF (Backus–Naur Form): variable লেখা হয় কোণ-বন্ধনীতে, যেমন <cond>; “→”-এর জায়গায় “::=”; terminal উদ্ধৃতিতে; আর বিকল্প আলাদা হয় একটি খাড়া দাগে। BNF-এর প্রাথমিক পরিচয় ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৭৩-এ আছে; এখানে আমরা দেখব, এটি হুবহু একটি CFG.
EBNF (Extended BNF) তিনটি সুবিধা যোগ করে: { x } মানে x শূন্য বা বেশিবার, [ x ] মানে x থাকতেও পারে, নাও থাকতে পারে, আর ( x ∣ y ) দিয়ে নিয়মের ভেতরে বিকল্প জোড়া। এগুলো regular expression-এর star আর “?”-এর মতো। EBNF CFG-এর চেয়ে বেশি শক্তিশালী নয়: প্রতিটি { x }-এর জায়গায় একটি নতুন variable X আর দুটি নিয়ম X → xX ∣ ε বসালেই সাধারণ CFG পাওয়া যায়। লাভ শুধু লেখার সুবিধা আর পড়ার সহজতা।
এবার বাজারঘরের order-query ভাষা। পর্ব ২২-এর lexer ইনপুট লাইনকে token-এ ভাগ করে: FIND, WHERE, AND-এর মতো keyword, সংখ্যার জন্য NUM, উদ্ধৃতির ভেতরের লেখার জন্য STR. Parser সংখ্যার আসল মান বা জেলার নাম দেখে না, দেখে শুধু token-এর ধরন। তাই grammar-এর terminal হলো token, অক্ষর নয়। একটি নমুনা query:
FIND order WHERE amount >= 1000 AND district = "Dhaka"
token: FIND order WHERE amount >= NUM AND district = STR
একই ভাষার grammar তিন রূপে নিচের ট্যাবে। গণিতের রূপে Q, C, T, F, R variable; Q হলো start symbol.
Q → FIND order WHERE C
C → C OR T ∣ T
T → T AND F ∣ F
F → ( C ) ∣ amount R NUM
∣ district = STR ∣ status = STR
R → = ∣ >= ∣ <
<query> ::= "FIND" "order" "WHERE" <cond>
<cond> ::= <cond> "OR" <term> | <term>
<term> ::= <term> "AND" <fact> | <fact>
<fact> ::= "(" <cond> ")"
| "amount" <rel> NUM
| "district" "=" STR
| "status" "=" STR
<rel> ::= "=" | ">=" | "<"
query = "FIND" "order" "WHERE" cond ;
cond = term { "OR" term } ;
term = fact { "AND" fact } ;
fact = "(" cond ")"
| "amount" ( "=" | ">=" | "<" ) NUM
| ( "district" | "status" ) "=" STR ;
তিনটি রূপ একই language বর্ণনা করে। লক্ষ করুন, AND-এর নিয়ম OR-এর নিয়মের এক স্তর নিচে: এর অর্থ, “a OR b AND c” পড়া হবে “a OR (b AND c)” হিসেবে, ঠিক যেমন গণিতে গুণ যোগের আগে হয়। এই স্তর-ভাগের কৌশল পর্ব ২৭-এ ambiguity দূর করার প্রধান হাতিয়ার হবে। আর F → ( C ) নিয়মটিই নেস্টিং আনে: বন্ধনীর ভেতরে আবার পুরো একটি শর্ত। ঠিক এই নিয়মের কারণে order-query ভাষা regular নয়; বন্ধনীর গভীরতা যেকোনো বড় হতে পারে।
| ধারণা | গণিতের রূপ | BNF | EBNF |
|---|---|---|---|
| variable | C | <cond> | cond |
| নিয়ম | C → … | <cond> ::= … | cond = … ; |
| বিকল্প | ∣ | খাড়া দাগ | খাড়া দাগ |
| শূন্য বা বেশিবার | নতুন variable + recursion | recursion | { x } |
| থাকতেও পারে | X → x ∣ ε | X ::= x ∣ (ফাঁকা) | [ x ] |
৪ · পাঁচটি মানক উদাহরণ — যেগুলো বারবার ফিরে আসবে
এই মডিউল আর পরের দুটি মডিউলে কয়েকটি grammar বারবার আসবে। প্রতিটির পেছনে একটি করে নকশার ধারণা আছে; সেটি বুঝলে নতুন grammar নিজেই বানাতে পারবেন।
১. anbn
S → aSb ∣ ε. প্রতিটি ধাপ বাইরের দিকে একটি a আর একটি b জোড়ে। ধারণা: মিলিয়ে গোনা মানে বাইরে থেকে ভেতরে মোড়ানো।
২. সুষম বন্ধনী BAL
S → (S)S ∣ ε. প্রথম “(”-এর জোড়া খুঁজে string ভাঙা। ধারণা: প্রথম জোড়া ভেতর আর বাইরের দুই অংশ আলাদা করে।
৩. Palindrome
S → aSa ∣ bSb ∣ a ∣ b ∣ ε. দুই প্রান্তে একই চিহ্ন। মাঝখানে একটি চিহ্ন (বিজোড় দৈর্ঘ্য) বা কিছুই না (জোড় দৈর্ঘ্য)।
৪. সমান a আর b
S → aSbS ∣ bSaS ∣ ε. প্রথম চিহ্নের “জোড়া” যেখানে হিসাব শূন্যে ফেরে, সেখানে ভাঙা; BAL-এর ধারণার সাধারণ রূপ।
পঞ্চম উদাহরণটি গাণিতিক expression, id, + , ∗ আর বন্ধনী দিয়ে। দুটি grammar একই language তৈরি করে:
প্রথমটি ছোট আর সহজ, কিন্তু id+id∗id-এর জন্য এতে দুটি আলাদা গাছ আছে, একটিতে যোগ আগে, অন্যটিতে গুণ আগে। এমন grammar-কে বলে ambiguous; এর পূর্ণ আলোচনা পর্ব ২৭-এ। দ্বিতীয়টিতে তিনটি স্তর: E যোগের স্তর, T গুণের স্তর, F একক বা বন্ধনী। এর একটি leftmost derivation:
E ⇒ E+T ⇒ T+T ⇒ F+T ⇒ id+T ⇒ id+T∗F ⇒ id+F∗F ⇒ id+id∗F ⇒ id+id∗id
এখানে গুণটি T-এর ভেতরে, অর্থাৎ যোগের ডান অংশের ভেতরে; তাই অর্থ id + (id ∗ id), যা গণিতের নিয়মের সঙ্গে মেলে। দুটি grammar একই language দেয় কি না, scratch-এ id-এর জায়গায় x বসিয়ে দৈর্ঘ্য ৯ পর্যন্ত সব string তৈরি করে মেলানো হয়েছে: প্রতিটি দৈর্ঘ্যে সংখ্যা সমান (দৈর্ঘ্য ৭-এ ৪৫টি, ৯-এ ১৯৭টি; দৈর্ঘ্য ৯ পর্যন্ত মোট ২৫৭টি) আর set দুটি হুবহু এক।
কোনো grammar ঠিক কোন language তৈরি করে, তা দেখার সবচেয়ে সরাসরি উপায় হলো ছোট দৈর্ঘ্যের সব string বানিয়ে ফেলা। নিচের ব্লক প্রতিটি variable-এর জন্য “দৈর্ঘ্য ≤ n-এর যত string এটি derive করতে পারে” তার set রাখে, আর প্রতিটি নিয়ম বারবার খাটিয়ে set-গুলো বাড়ায়, যতক্ষণ না আর কিছু বাড়ে। একে বলে fixpoint iteration. তারপর ফলাফলটি language-এর গাণিতিক সংজ্ঞার সঙ্গে, Σ-এর ওপর দৈর্ঘ্য ≤ n-এর প্রতিটি string ধরে ধরে, brute force-এ মেলায়। LE হলো অংশ ৫-এর {aibj : i ≤ j}.
from itertools import product
def lang(G, n):
"""All strings of length <= n that each variable derives (fixpoint)."""
L = {A: set() for A in G}
changed = True
while changed:
changed = False
for A, rhss in G.items():
for rhs in rhss:
for c in product(*[L[X] if X in G else {X} for X in rhs]):
w = "".join(c)
if len(w) <= n and w not in L[A]:
L[A].add(w); changed = True
return L["S"]
cnt = lambda w, c: w.count(c)
bal = lambda w: cnt(w, "(") == cnt(w, ")") and all(
cnt(w[:k], "(") >= cnt(w[:k], ")") for k in range(len(w)))
sorted_ab = lambda w: w == "a" * cnt(w, "a") + "b" * cnt(w, "b")
tests = [ # name, grammar (start S), alphabet, the definition of L
("anbn", {"S": ["aSb", ""]}, "ab",
lambda w: sorted_ab(w) and cnt(w, "a") == cnt(w, "b")),
("BAL", {"S": ["(S)S", ""]}, "()", bal),
("PAL", {"S": ["aSa", "bSb", "a", "b", ""]}, "ab", lambda w: w == w[::-1]),
("EQ", {"S": ["aSbS", "bSaS", ""]}, "ab", lambda w: cnt(w, "a") == cnt(w, "b")),
("LE", {"S": ["aSb", "B"], "B": ["bB", ""]}, "ab",
lambda w: sorted_ab(w) and cnt(w, "a") <= cnt(w, "b")),
]
n = 8
for name, G, sigma, inL in tests:
gen = lang(G, n)
want = {w for k in range(n + 1)
for w in map("".join, product(sigma, repeat=k)) if inL(w)}
first = sorted(gen, key=lambda w: (len(w), w))[:5]
print(f"{name:4} n<={n}: {len(gen):3} strings, equal to definition: {gen == want}")
print(" first:", ", ".join(w or "ε" for w in first))আসল আউটপুট (ব্রাউজারের Python):
anbn n<=8: 5 strings, equal to definition: True
first: ε, ab, aabb, aaabbb, aaaabbbb
BAL n<=8: 23 strings, equal to definition: True
first: ε, (), (()), ()(), ((()))
PAL n<=8: 61 strings, equal to definition: True
first: ε, a, b, aa, bb
EQ n<=8: 99 strings, equal to definition: True
first: ε, ab, ba, aabb, abab
LE n<=8: 25 strings, equal to definition: True
first: ε, b, ab, bb, abb
পাঁচটি grammar-ই দৈর্ঘ্য ৮ পর্যন্ত তাদের সংজ্ঞার সঙ্গে হুবহু মিলেছে। সংখ্যাগুলো নিজেও হিসাব করে মেলানো যায়। BAL-এ দৈর্ঘ্য 0, 2, 4, 6, 8-এ 1, 1, 2, 5, 14টি string, যোগফল 23; এগুলো Catalan সংখ্যা। EQ-তে দৈর্ঘ্য 2k-এ C(2k, k)টি: 1 + 2 + 6 + 20 + 70 = 99. PAL-এ দৈর্ঘ্য ℓ-এর palindrome 2⌈ℓ/2⌉টি, যোগফল 61. Program-টি কেন সঠিক: দৈর্ঘ্য ≤ n-এর একটি string-এর derivation-এর প্রতিটি অংশ ওই string-এরই একটি টুকরো derive করে, তাই প্রতিটি টুকরোর দৈর্ঘ্যও ≤ n; ফলে দৈর্ঘ্যের সীমা কোনো string হারায় না, আর set-গুলো সসীম বলে loop থামে। সতর্কতা: “দৈর্ঘ্য ৮ পর্যন্ত মিলেছে” কোনো প্রমাণ নয়, শুধু ভুল ধরার জাল। প্রমাণ আসবে অংশ ৬-এ।
৫ · CFG নকশার কৌশল — বর্ণনা থেকে নিয়ম
বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় সবচেয়ে পরিচিত প্রশ্ন: “এই language-এর জন্য একটি CFG দিন।” কোনো যান্ত্রিক সূত্র নেই, কিন্তু তিনটি কৌশল প্রায় সব ক্ষেত্রে কাজ করে।
- মিলিয়ে গোনার জন্য recursion: দুটি অংশের দৈর্ঘ্য বা চিহ্ন একসঙ্গে বাড়াতে হলে একই নিয়মে দুই পাশে বসান: S → aSb, S → aSa. মিলটি সবসময় “বাইরে থেকে ভেতরে” হয়, তাই যে দুটি অংশ মিলবে সেগুলো string-এর দুই প্রান্তে বা নেস্ট করা অবস্থায় থাকতে হবে।
- অংশে ভাগ: string-টিকে কয়েকটি স্বাধীন অংশের concatenation হিসেবে লিখুন, প্রতিটি অংশের জন্য আলাদা variable নিন, আর S → XY দিয়ে জুড়ুন। যেমন aibi+kck = (aibi)(bkck), তাই S → XY, X → aXb ∣ ε, Y → bYc ∣ ε.
- ক্ষেত্রভিত্তিক union: “i ≠ j” বা “i = j অথবা j = k” ধরনের শর্ত কয়েকটি সহজ ক্ষেত্রের union. প্রতিটি ক্ষেত্রের grammar আলাদা লিখে S → S1 ∣ S2 দিয়ে জুড়ুন (অংশ ৮-এ এর নিয়ম)।
প্রতিটি কৌশলের পরে দুটি যাচাই অবশ্যই করবেন: (ক) grammar কি এমন কোনো string তৈরি করে, যা language-এ নেই? (খ) language-এর কোনো string কি grammar থেকে বাদ পড়ে? প্রথম প্রশ্নের জন্য নিয়মগুলো যে ধর্ম রক্ষা করে সেটি খুঁজুন; দ্বিতীয়টির জন্য ছোট string, বিশেষ করে ε আর একেবারে প্রান্তের ক্ষেত্র, নিজে derive করে দেখুন। নিচের stepper একটি পূর্ণ নকশা দেখায়।
1উদাহরণ আর পাল্টা-উদাহরণ2অংশে ভাগ: aⁱbⁱ · bᵏ3S → aSb4S → B ; B → bB ∣ ε5abbb derive করা6দুই দিক যাচাই
| কাজ | |
| নিয়ম |
- চেনা। L = {aibj : i ≤ j}: আগে সব a, তারপর সব b, আর b অন্তত a-এর সমান। ভেতরে: ε, b, ab, abb, aabb. বাইরে: a (b কম), ba (ক্রম ভুল), aab (b কম)। ε ভেতরে, কারণ i = j = 0.
- ভাগ। j ≥ i, তাই j = i + k কোনো k ≥ 0-এর জন্য। তাহলে aibj = aibkbi: i জোড়া মেলানো a…b, আর তাদের মাঝখানে k-টি বাড়তি b. বাড়তি b-গুলো শুরুতে না রেখে মাঝখানে রাখলে নেস্টিং-এর কাঠামো ভাঙে না।
- নেস্টিং। S → aSb প্রতিবার বাইরের দিকে একটি a আর একটি b জোড়ে, ঠিক anbn-এর মতো। i বার খাটালে aiSbi.
- মাঝের অংশ। মাঝের S এখন bk লিখবে: S → B, আর B → bB ∣ ε যেকোনো সংখ্যক b দেয়। ফলে grammar: S → aSb ∣ B, B → bB ∣ ε.
- একটি derivation. abbb (i = 1, j = 3, k = 2): S ⇒ aSb ⇒ aBb ⇒ abBb ⇒ abbBb ⇒ abbb. প্রথম ধাপ মোড়ানো, দ্বিতীয় ধাপ মাঝের অংশে ঢোকা, তারপর দুটি বাড়তি b আর শেষে ε.
- যাচাই। বাড়তি নয়: প্রতিটি terminal string aibkbi, তাই সব a আগে আর b-এর সংখ্যা i + k ≥ i. বাদ নয়: যেকোনো aibj (i ≤ j)-এ S → aSb i বার, S → B, B → bB (j − i) বার, B → ε. ওপরের Python ব্লকের LE সারিতে দৈর্ঘ্য ৮ পর্যন্ত ২৫টি string সংজ্ঞার সঙ্গে মিলেছে।
একটি সাধারণ ভুল দেখুন: S → aS ∣ Sb ∣ ε. এটি শুনতে ঠিক লাগে (“একবার a যোগ, নয়তো একবার b যোগ”), কিন্তু এর language পুরো a∗b∗, যেখানে aab-ও আছে; a আর b-এর সংখ্যার মধ্যে কোনো সম্পর্ক বাঁধা নেই। আবার S → aSbb ∣ ε শুধু j = 2i দেয়। নিয়ম যখন দুটি গোনা মেলায় না, তখন সে কোনো শর্তও রাখে না; মিল সবসময় একই নিয়মের দুই পাশে বসাতে হয়।
Grammar-কে উল্টো দিক থেকেও দেখা যায়: যন্ত্রের মতো এলোমেলো নিয়ম বেছে বেছে string তৈরি করা। নতুন grammar লেখার পর কয়েকটি এলোমেলো string দেখলে চোখে পড়ে, grammar এমন কিছু বানাচ্ছে কি না যা আপনি চাননি। নিচের JavaScript ব্লক দুটি কাজ করে। প্রথমে BAL-এর একটি এলোমেলো leftmost derivation-এর প্রতিটি ধাপ ছাপে। তারপর order-query grammar থেকে পাঁচটি এলোমেলো query তৈরি করে। গভীরতা ৪ পেরোলে প্রতিটি variable-এর প্রথম নিয়মটি (সাধারণত recursive) বাদ দেওয়া হয়, যাতে তৈরি করা string অসীম না হয়ে যায়। Seed স্থির, তাই প্রতিবার একই ফল।
// Random derivations. A grammar maps each variable to its rules; a rule
// is an array of symbols. Seeded generator: the same output every run.
let seed = 7;
const rnd = k => Math.floor((seed = seed * 16807 % 2147483647) / 2147483647 * k);
function leftmost(G, start, budget) { // prints every step
let form = [start];
for (let step = 0; ; step++) {
const i = form.findIndex(s => s in G); // leftmost variable
if (i < 0) return;
const R = G[form[i]]; // last rule = exit rule
const r = step < budget ? rnd(R.length) : R.length - 1;
form = [...form.slice(0, i), ...R[r], ...form.slice(i + 1)];
console.log(" =>", form.join("") || "ε");
}
}
function gen(G, A, depth = 0) { // a random tree, as text
if (!(A in G)) return [A]; // terminal
const R = G[A]; // deep: skip rule 0
const r = depth > 4 && R.length > 1 ? 1 + rnd(R.length - 1) : rnd(R.length);
return R[r].flatMap(X => gen(G, X, depth + 1));
}
console.log("BAL S -> (S)S | ε, a leftmost derivation:");
leftmost({ S: [["(", "S", ")", "S"], []] }, "S", 4);
const Q = { // order-query grammar
Q: [["FIND", "order", "WHERE", "C"]],
C: [["C", "OR", "T"], ["T"]],
T: [["T", "AND", "F"], ["F"]],
F: [["(", "C", ")"], ["amount", "R", "NUM"],
["status", "=", "STR"], ["district", "=", "STR"]],
R: [["="], [">="], ["<"]],
};
console.log("Five random order queries (as tokens):");
for (let k = 0; k < 5; k++) console.log(" ", gen(Q, "Q").join(" "));আসল আউটপুট (ব্রাউজারের JavaScript):
BAL S -> (S)S | ε, a leftmost derivation:
=> (S)S
=> ()S
=> ()(S)S
=> ()((S)S)S
=> ()(()S)S
=> ()(())S
=> ()(())
Five random order queries (as tokens):
FIND order WHERE district = STR AND status = STR
FIND order WHERE ( amount < NUM OR district = STR )
FIND order WHERE status = STR OR status = STR
FIND order WHERE amount >= NUM AND amount >= NUM AND amount < NUM
FIND order WHERE ( status = STR OR district = STR )
প্রথম অংশে S থেকে ৭ ধাপে ()(()) তৈরি হয়েছে; প্রতিটি লাইনে ঠিক সবচেয়ে বাঁয়ের S বদলেছে (প্রথম লাইনের আগের রূপটি S নিজে)। এখানে প্রথম “(” প্রথম “)”-এর সঙ্গেই জোড়া, আর বাকি অংশ শেষের S থেকে এসেছে। budget ৪ ধাপের পরে প্রতিটি S-এ শুধু ε বেছে নেয়, তাই derivation শেষ হতে বাধ্য। দ্বিতীয় অংশে প্রতিটি query-র token-ক্রম grammar-এর নিয়ম মানে: বন্ধনী সবসময় জোড়ায়, OR আর AND-এর দুই পাশে একটি করে শর্ত, আর NUM শুধু amount-এর পরে। চতুর্থ query-টি দেখায়, grammar অর্থহীন কিন্তু syntax-এ ঠিক জিনিসও মেনে নেয়: একই amount-এ তিনটি শর্ত। কোনো query অর্থপূর্ণ কি না, সেটি syntax-এর পরের ধাপের কাজ; grammar শুধু গঠন দেখে। seed বদলে আরও query দেখুন, আর F-এর নিয়মে একটি নতুন field (যেমন "phone", "=", "STR") যোগ করে দেখুন।
৬ · প্রমাণ: L(G) = L — দুই দিকের inclusion
Brute force দৈর্ঘ্য ৮ বা ১০ পর্যন্ত দেখে, কিন্তু language অসীম। “এই grammar ঠিক এই language তৈরি করে” দাবিটি দুটি set-এর সমতা, তাই প্রমাণেও দুটি দিক লাগে:
- L(G) ⊆ L (soundness, “বাড়তি কিছু নেই”): grammar যা-ই তৈরি করে, তা L-এ আছে। সাধারণ কৌশল: derivation-এর দৈর্ঘ্যের ওপর induction, প্রতিটি sentential form-এর একটি ধর্ম (invariant) প্রমাণ করে।
- L ⊆ L(G) (completeness, “কিছু বাদ নেই”): L-এর প্রতিটি string grammar থেকে আসে। সাধারণ কৌশল: string-এর দৈর্ঘ্যের ওপর induction (induction on length), string-টিকে ছোট টুকরোয় ভেঙে।
G: S → aSb ∣ ε হলে L(G) = {anbn : n ≥ 0}.
প্রমাণ (⊆ দিক):
- দাবি P(k): S ⇒ ⋯ ⇒ α যদি ঠিক k ধাপের একটি derivation হয়, তবে α = akSbk, অথবা k ≥ 1 আর α = ak−1bk−1. — invariant-এর বক্তব্য
- ভিত্তি k = 0: শূন্য ধাপে α = S = a0Sb0. — ⇒∗-এর সংজ্ঞা
- ধাপ: ধরুন P(k) সত্য আর S ⇒k α ⇒ β. α-তে একটি variable থাকতেই হবে, নইলে আর ধাপ নেওয়া যেত না; তাই P(k) থেকে α = akSbk. — induction hypothesis
- α-তে একটিমাত্র S, আর তার দুটি নিয়ম। S → aSb দিলে β = ak+1Sbk+1; S → ε দিলে β = akbk = a(k+1)−1b(k+1)−1. দুটিই P(k + 1)-এর রূপ। — R-এর নিয়ম গুনে দেখা
- তাই প্রতিটি k-তে P(k). L(G)-এর কোনো w-তে variable নেই, তাই w = ak−1bk−1, যা L-এ আছে। ∎ — induction-এর উপসংহার
প্রমাণ (⊇ দিক):
- দাবি Q(n): S ⇒∗ anSbn, প্রতিটি n ≥ 0-এ। ভিত্তি n = 0: শূন্য ধাপ। ধাপ: S ⇒∗ anSbn ⇒ anaSbbn = an+1Sbn+1, মাঝের S-এ S → aSb খাটিয়ে। — n-এর ওপর induction
- যেকোনো anbn-এর জন্য Q(n)-এর derivation-এর পর S → ε: S ⇒∗ anSbn ⇒ anbn. তাই anbn ∈ L(G). ∎ — context-free নিয়ম যেকোনো প্রসঙ্গে খাটে
1লক্ষ্য: L(G) = L2⊆: invariant P(k)3 ভিত্তি k = 04 ধাপ k → k + 15⊇: S ⇒∗ aⁿSbⁿ ⇒ aⁿbⁿ6দুই দিক মিলে সমতা ∎
| উদাহরণ | |
| কোন induction |
- লক্ষ্য। L = {anbn : n ≥ 0}. দুটি দিক আলাদা: grammar-এর প্রতিটি string L-এ (⊆), আর L-এর প্রতিটি string grammar-এ (⊇)। যেকোনো একটি বাদ দিলে প্রমাণ অসম্পূর্ণ।
- Invariant. ⊆-এর জন্য শুধু শেষ string নয়, মাঝপথের প্রতিটি sentential form-এর রূপ বলতে হয়: k ধাপ পরে akSbk, বা (শেষ ধাপে ε দেওয়া হয়ে গেলে) ak−1bk−1. যেমন k = 2-এ aaSbb বা ab.
- ভিত্তি। শূন্য ধাপে sentential form শুধু S, যা a0Sb0. দাবি সত্য।
- ধাপ। k ধাপ পরে আরেকটি ধাপ নেওয়া গেলে form-এ S আছে, তাই সেটি akSbk. S → aSb দিলে ak+1Sbk+1, S → ε দিলে akbk. দুটি নিয়মই রূপটি রক্ষা করে। তাই grammar-এর প্রতিটি terminal string ambm আকারের।
- উল্টো দিক। n-এর ওপর induction-এ S ⇒∗ anSbn; তারপর S → ε. n = 2-এ: S ⇒ aSb ⇒ aaSbb ⇒ aabb. প্রতিটি anbn তাই L(G)-এ।
- উপসংহার। L(G) ⊆ L আর L ⊆ L(G), তাই L(G) = L. ∎ বাড়তি পাওনা: দৈর্ঘ্য 2n-এর সদস্যের derivation-এ ঠিক n + 1টি ধাপ (n বার aSb, একবার ε); invariant থেকেই এটি পড়া যায়।
anbn-এ ⊇ দিক সহজ, কারণ derivation নিজেই স্পষ্ট। কঠিন উদাহরণে ⊇-এর জন্য string-টিকে grammar-এর নিয়মের আকারে ভাঙতে হয়, আর সেখানে strong induction লাগে (দৈর্ঘ্য n-এর আগের সব দৈর্ঘ্যে দাবি সত্য ধরা)। EQ grammar S → aSbS ∣ bSaS ∣ ε-এর জন্য রূপরেখাটি দেখুন; পূর্ণ লেখা অনুশীলন ২-এ।
প্রমাণের রূপরেখা (EQ): ⊆ দিক: প্রতিটি নিয়ম একটি a আর একটি b একসঙ্গে যোগ করে (বা কিছুই না), তাই প্রতিটি sentential form-এ a আর b-এর সংখ্যা সমান; এটি derivation-এর দৈর্ঘ্যের ওপর induction. ⊇ দিক: w-এ a আর b সমান, w ≠ ε, আর ধরুন w শুরু হয় a দিয়ে। বাঁ থেকে পড়তে পড়তে “a-এর সংখ্যা − b-এর সংখ্যা” হিসাব রাখুন; শুরুতে 1, শেষে 0, তাই প্রথম যেখানে এটি 0 হয়, সেখানে একটি b পড়া হয়েছে। এভাবে w = aubv, যেখানে u আর v দুটিতেই a আর b সমান আর দুটিই w-এর চেয়ে ছোট। Induction-এ S ⇒∗ u আর S ⇒∗ v, তাই S ⇒ aSbS ⇒∗ aubv = w. b দিয়ে শুরু হলে একইভাবে bSaS. BAL-এর S → (S)S ঠিক এই যুক্তির বিশেষ রূপ, যেখানে হিসাব কখনো ঋণাত্মক হয় না।
সাধারণ ফাঁদ: শুধু ⊇ দেখিয়ে থেমে যাওয়া (“দেখুন, aabb derive হয়”)। এতে grammar যে বাড়তি string-ও তৈরি করে না, তা প্রমাণ হয় না। S → aSb ∣ SS ∣ ε থেকে aabb আসে, কিন্তু abab-ও আসে, যা anbn-এ নেই। আবার শুধু ⊆ দেখালে grammar হয়তো খুব কম তৈরি করে: S → aaSbb ∣ ε-এর প্রতিটি string anbn-এ আছে, কিন্তু ab বাদ পড়ে।
৭ · Regular grammar — CFG-এর একটি বিশেষ রূপ
পর্ব ০৬-এ Type 3 grammar-কে বলা হয়েছিল right-linear বা regular grammar: প্রতিটি নিয়ম A → aB, A → a বা A → ε. এগুলো স্পষ্টতই context-free (বাঁ দিকে একটি variable), তাই প্রতিটি regular grammar একটি CFG. বিশেষত্ব হলো, ডান দিকে বড়জোর একটি variable, সেটিও একেবারে শেষে। তাই derivation-এর প্রতিটি sentential form “কিছু terminal, তারপর বড়জোর একটি variable” আকারের, ঠিক যেমন একটি DFA কিছু চিহ্ন পড়ে এখন কোনো একটি state-এ আছে।
প্রতিটি regular language context-free. আরও নির্দিষ্টভাবে, DFA M = (Q, Σ, δ, q0, F) দেওয়া থাকলে G = (Q, Σ, R, q0), যেখানে প্রতিটি δ(q, a) = r-এর জন্য নিয়ম q → ar, আর প্রতিটি q ∈ F-এর জন্য q → ε, একটি right-linear grammar, এবং L(G) = L(M).
প্রমাণের রূপরেখা: |w|-এর ওপর induction-এ দেখানো যায়, q0 ⇒∗ wq ঠিক তখনই, যখন DFA-টি q0 থেকে w পড়ে q-তে পৌঁছায় (δ̂(q0, w) = q). Terminal string পেতে শেষে কোনো q → ε খাটাতে হয়, যা শুধু q ∈ F-এ আছে। তাই q0 ⇒∗ w ⇔ δ̂(q0, w) ∈ F. ∎ উল্টো দিকেও সত্য: প্রতিটি right-linear grammar থেকে একটি NFA বানানো যায় (variable = state, A → aB মানে A থেকে a পড়ে B), তাই right-linear grammar ঠিক regular language-গুলোই দেয়।
উদাহরণ: বাজারঘরের sensor লাইনের parity check, “1-এর সংখ্যা জোড়” (পর্ব ০৭)। DFA-র দুটি state: E (জোড়, শুরু ও accepting) আর O (বিজোড়)। উপপাদ্যের গঠনে:
1001-এর derivation: E ⇒ 1O ⇒ 10O ⇒ 100O ⇒ 1001E ⇒ 1001. প্রতিটি ধাপ DFA-র একটি transition: variable-টি দেখায় এখন কোন state. Scratch-এ দৈর্ঘ্য ১০ পর্যন্ত এই grammar-এর language “1-এর সংখ্যা জোড়”-এর সঙ্গে হুবহু মিলেছে।
অন্তর্ভুক্তিটি কঠোর: anbn context-free (উপপাদ্য ৬.১), কিন্তু regular নয় (পর্ব ১৭)। তাই regular ⊊ context-free. লক্ষ করুন, একটি grammar right-linear না হলেও তার language regular হতে পারে: S → aSa ∣ aa ∣ ε-এর language শুধু জোড় দৈর্ঘ্যের a-এর string, যা regular. Grammar-এর আকার language-এর শ্রেণির একটি ঊর্ধ্বসীমা দেয়, নিম্নসীমা নয়।
| DFA-তে | Right-linear grammar-এ |
|---|---|
| state q | variable q |
| শুরুর state q0 | start symbol q0 |
| δ(q, a) = r | q → ar |
| accepting state q ∈ F | q → ε |
| w পড়ে q-তে পৌঁছানো | q0 ⇒∗ wq |
৮ · Closure — union, concatenation আর star-এর grammar
Regular language-এর closure property প্রমাণে (পর্ব ১৬) automaton জোড়া লাগাতে হয়েছিল। CFG-তে তিনটি operation আরও সহজ: শুধু একটি নতুন start symbol আর একটি-দুটি নিয়ম।
ধরুন G1 = (V1, Σ, R1, S1) আর G2 = (V2, Σ, R2, S2), যেখানে V1 ∩ V2 = ∅ (দরকারে variable-এর নাম বদলে), আর S একটি নতুন variable. তাহলে:
১. Union: R1 ∪ R2 ∪ {S → S1 ∣ S2} দেয় L(G1) ∪ L(G2);
২. Concatenation: R1 ∪ R2 ∪ {S → S1S2} দেয় L(G1)L(G2);
৩. Star: R1 ∪ {S → S1S ∣ ε} দেয় L(G1)∗.
তাই CFL-এর শ্রেণি union, concatenation আর Kleene star-এ বদ্ধ।
প্রমাণের রূপরেখা (union): ⊆: S থেকে প্রথম ধাপ S1 বা S2. ধরুন S1. এরপর sentential form-এ শুধু V1-এর variable থাকে, কারণ R1-এর নিয়মের ডান দিকে V2-এর কিছু নেই (variable আলাদা); তাই derivation-টি G1-এর একটি derivation, আর w ∈ L(G1). ⊇: S ⇒ Si-এর পর Gi-এর derivation হুবহু চালানো যায়। Concatenation-এ S1 আর S2 থেকে দুটি স্বাধীন derivation পাশাপাশি চলে, কারণ context-free নিয়ম পাশের অংশ দেখে না। Star-এ S ⇒∗ S1S1⋯S1S ⇒ S1⋯S1, যেকোনো k ≥ 0 সংখ্যক কপি। ∎
“Variable আলাদা” শর্তটি কেন দরকার? দুটি grammar-এ একই নাম S থাকলে, আর নাম না বদলে নিয়মগুলো এক জায়গায় ঢেলে দিলে, এক grammar-এর নিয়ম অন্যটির derivation-এর মাঝখানে ঢুকে পড়ে। নিচের ব্লকটি anbn (G1) আর bnan (G2) নিয়ে তিনটি গঠন যাচাই করে, তারপর নাম না বদলানো “union”-এর বাড়তি string খুঁজে দেখায়। এটি আগের ব্লকের lang function, শুধু start symbol বাছার সুবিধাসহ।
from itertools import product
def lang(G, start, n): # same fixpoint as before
L = {A: set() for A in G}
changed = True
while changed:
changed = False
for A, rhss in G.items():
for rhs in rhss:
for c in product(*[L[X] if X in G else {X} for X in rhs]):
w = "".join(c)
if len(w) <= n and w not in L[A]:
L[A].add(w); changed = True
return L[start]
G1 = {"S": ["aSb", ""]} # a^n b^n
G2 = {"S": ["bSa", ""]} # b^n a^n (same variable name S!)
def rename(G, new): # S -> new, everywhere
return {new if A == "S" else A: [r.replace("S", new) for r in R]
for A, R in G.items()}
A, B = rename(G1, "A"), rename(G2, "B")
n = 6
L1, L2 = lang(A, "A", n), lang(B, "B", n)
cat = lambda X, Y: {u + v for u in X for v in Y if len(u + v) <= n}
star = {""}
for _ in range(n):
star |= cat(star, L1)
union = {"S": ["A", "B"], **A, **B}
concat = {"S": ["AB"], **A, **B}
kstar = {"S": ["AS", ""], **A}
print("union :", lang(union, "S", n) == L1 | L2)
print("concat:", lang(concat, "S", n) == cat(L1, L2))
print("star :", lang(kstar, "S", n) == star)
naive = {"S": G1["S"] + G2["S"]} # merge without renaming
extra = sorted(lang(naive, "S", n) - (L1 | L2), key=lambda w: (len(w), w))
print("naive union extras:", len(extra), extra[:6])আসল আউটপুট (ব্রাউজারের Python):
union : True
concat: True
star : True
naive union extras: 8 ['abab', 'baba', 'aababb', 'ababab', 'abbaab', 'baabba']
প্রথম তিন লাইন বলছে, নাম বদলানোর পর তিনটি গঠনই দৈর্ঘ্য ৬ পর্যন্ত ঠিক প্রত্যাশিত set দেয়। প্রত্যাশিত set-গুলো grammar ছাড়াই, সরাসরি L1 আর L2-এর string জুড়ে (cat) আর বারবার জুড়ে (star) হিসাব করা। শেষ লাইনে ভুলটি ধরা পড়েছে: S → aSb ∣ bSa ∣ ε থেকে abab আসে (S ⇒ aSb ⇒ abSab ⇒ abab), যা anbn-ও নয়, bnan-ও নয়। দৈর্ঘ্য ৬ পর্যন্ত এমন ৮টি বাড়তি string; ছাপা হয়েছে প্রথম ছয়টি। rename ঠিক উপপাদ্যের “V1 ∩ V2 = ∅” শর্তটি কোডে পূরণ করে।
কিন্তু intersection আর complement-এ CFL বদ্ধ নয়। L1 = {anbncm} আর L2 = {ambncn} দুটিই context-free (অংশে ভাগের কৌশলে S → XC, X → aXb ∣ ε, C → cC ∣ ε), কিন্তু তাদের intersection {anbncn}, যা context-free নয়; প্রমাণ আসবে পর্ব ৩৬-এর CFL pumping lemma দিয়ে। Union-এর গঠন কাজ করে কারণ grammar “এটা অথবা ওটা” সহজে বলতে পারে, কিন্তু “এটা এবং একই সঙ্গে ওটা” বলার কোনো নিয়ম নেই। পূর্ণ closure-এর তালিকা, regular language-এর সঙ্গে intersection-সহ, পর্ব ৩৭-এ।
আরও গভীরে: CFL-এর গঠন নিয়ে দুটি গভীর উপপাদ্য আছে। Chomsky–Schützenberger theorem (১৯৬৩) বলে, প্রতিটি CFL একটি Dyck language (কয়েক রকম বন্ধনীর সুষম string) আর একটি regular language-এর intersection-এর একটি homomorphic image; অর্থাৎ “সুষম বন্ধনী + সসীম নিয়ন্ত্রণ” প্রতিটি CFL-এর হৃদয়ে আছে। Parikh-এর theorem (প্রকাশ ১৯৬৬) বলে, শুধু চিহ্নের সংখ্যা গুনলে প্রতিটি CFL কোনো একটি regular language থেকে আলাদা করা যায় না; যেমন anbn-এর গোনার ছাপ (ab)∗-এর মতোই। দুটির বিস্তারিত বিবরণ Hopcroft–Motwani–Ullman বা Kozen-এর বইয়ে পাবেন।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- CFG-এর formal definition দিন। G = (V, Σ, R, S), নিয়ম A → α, A ∈ V, α ∈ (V ∪ Σ)∗; L(G) = {w ∈ Σ∗ : S ⇒∗ w}.
- {aibj : i ≤ j}, palindrome বা সমান a, b-এর CFG দিন। S → aSb ∣ B, B → bB ∣ ε; S → aSa ∣ bSb ∣ a ∣ b ∣ ε; S → aSbS ∣ bSaS ∣ ε.
- প্রমাণ করুন L(S → aSb ∣ ε) = {anbn}. ⊆: sentential form-এর invariant akSbk; ⊇: n-এর ওপর induction.
- দেখান যে প্রতিটি regular language context-free. DFA-র প্রতিটি δ(q, a) = r থেকে q → ar, প্রতিটি accepting q থেকে q → ε.
- CFL কি intersection-এ বদ্ধ? না: {anbncm} ∩ {ambncn} = {anbncn}.
৯ · AI-এর যুগে CFG নকশা
AI assistant-কে “X-এর জন্য একটি CFG দাও” বললে সে দ্রুত একটি পরিচ্ছন্ন grammar দেয়, সাধারণত একটি ব্যাখ্যাসহ। দেখতে ঠিক লাগলেও সেটি প্রায়ই ভুল language তৈরি করে। একটি পরিচিত উদাহরণ: “a আর b সমান সংখ্যক” চাইলে উত্তর আসে S → aSb ∣ bSa ∣ ε. নিচের ব্লক এটি brute force-এ পরীক্ষা করে, আর SS নিয়ম যোগ করা সংশোধিত grammar-টিও।
from itertools import product
def lang(G, n): # fixpoint generator, start = "S"
L = {A: set() for A in G}
changed = True
while changed:
changed = False
for A, rhss in G.items():
for rhs in rhss:
for c in product(*[L[X] if X in G else {X} for X in rhs]):
w = "".join(c)
if len(w) <= n and w not in L[A]:
L[A].add(w); changed = True
return L["S"]
def eq(w): return w.count("a") == w.count("b")
def check(name, G, n=10):
gen = lang(G, n)
want = {"".join(t) for k in range(n + 1)
for t in product("ab", repeat=k) if eq("".join(t))}
key = lambda w: (len(w), w)
missing, extra = sorted(want - gen, key=key), sorted(gen - want, key=key)
print(f"{name}: generated {len(gen)}, should be {len(want)}")
print(" missing:", missing[:4], " extra:", extra[:4])
check("AI grammar S -> aSb | bSa | ε", {"S": ["aSb", "bSa", ""]})
check("fixed grammar S -> aSb | bSa | SS | ε", {"S": ["aSb", "bSa", "SS", ""]})আসল আউটপুট (ব্রাউজারের Python):
AI grammar S -> aSb | bSa | ε: generated 63, should be 351
missing: ['abba', 'baab', 'aabbab', 'aabbba'] extra: []
fixed grammar S -> aSb | bSa | SS | ε: generated 351, should be 351
missing: [] extra: []
প্রথম grammar কোনো বাড়তি string তৈরি করে না (⊆ দিক ঠিক), কিন্তু দৈর্ঘ্য ১০ পর্যন্ত ৩৫১টির মধ্যে মাত্র ৬৩টি দেয়। সবচেয়ে ছোট বাদ পড়া string abba: এর প্রথম আর শেষ চিহ্ন একই, অথচ aSb আর bSa দুটি নিয়মই দুই প্রান্তে আলাদা চিহ্ন বসায়। 63 = 1 + 2 + 4 + 8 + 16 + 32, কারণ প্রতি জোড়া চিহ্নে মাত্র দুটি পছন্দ। SS যোগ করলে abba = (ab)(ba) দুটি টুকরো জুড়ে আসে, আর সংখ্যা মিলে যায়: C(2k, k)-এর যোগফল 1 + 2 + 6 + 20 + 70 + 252 = 351. মিল দেখা মানে প্রমাণ নয়; সংশোধিত grammar-এর ⊇ দিকের প্রমাণ অংশ ৬-এর EQ রূপরেখার মতো, শুধু ভাঙনটি w = (aub)v আকারে।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| Grammar কিছু string বাদ দেয় (যেমন abba), বা বাড়তি string দেয় (S → aS ∣ Sb ∣ ε-তে aab) | ওপরের ব্লকের মতো দৈর্ঘ্য ৮–১০ পর্যন্ত দুই দিকের পার্থক্য (missing আর extra) ছাপুন |
| ε ভুলে যাওয়া: i ≤ j-এর grammar-এ ε নেই, বা ε থাকার কথা নয় এমন জায়গায় ε | সবচেয়ে ছোট তিনটি ক্ষেত্র (ε, দৈর্ঘ্য ১, দৈর্ঘ্য ২) হাতে মিলিয়ে দেখুন |
| “প্রমাণ” মানে শুধু কয়েকটি উদাহরণের derivation দেখানো, বা শুধু এক দিকের inclusion | ⊆ আর ⊇ দুটি আলাদা শিরোনামে আছে কি না, আর ⊆-এ একটি invariant আছে কি না দেখুন |
| দুটি grammar-এর union-এ variable-এর নাম না বদলানো | প্রতিটি অংশের variable আলাদা কি না দেখুন; closure_grammars.py-এর মতো বাড়তি string খুঁজুন |
| “CFL intersection বা complement-এ বদ্ধ” জাতীয় দাবি | {anbncn}-এর পাল্টা-উদাহরণ মনে রাখুন; পর্ব ৩৭ দেখুন |
| বানানো রেফারেন্স বা ভুল ইতিহাস (যেমন BNF-এর সাল বা আবিষ্কারকের নাম) | Sipser বা Hopcroft–Motwani–Ullman-এ নিজে খুঁজে নিশ্চিত হোন |
AI-কে ভালোভাবে কাজে লাগানোর উপায়: grammar-এর সঙ্গে একটি যাচাইযোগ্য দাবি, দুই দিকের প্রমাণ আর একটি ছোট brute-force কোড চাওয়া, যা আপনি নিজে চালাবেন।
(নিজে যাচাই করুন: একটি সঠিক grammar S → aSaSbS ∣ aSbSaS ∣ bSaSaS ∣ ε. দৈর্ঘ্য ৯ পর্যন্ত scratch-এ এটি সংজ্ঞার সঙ্গে মিলেছে। AI অন্য grammar দিলে সেটি ভুল না-ও হতে পারে; কোড চালিয়ে missing আর extra দুটিই ফাঁকা কি না দেখুন।)
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১BNF কোথা থেকে এল, আর একটি ভাষাবিজ্ঞানের ধারণা কীভাবে programming language-এর মানক হাতিয়ার হয়ে উঠল?
Noam Chomsky ১৯৫৬ সালের “Three models for the description of language” প্রবন্ধে মানুষের ভাষার বাক্য-গঠন বর্ণনা করতে phrase-structure grammar-এর ধারণা দেন, আর ১৯৫৯ সালের প্রবন্ধে নিয়মের আকার অনুযায়ী শ্রেণিগুলো আলাদা করেন। প্রায় একই সময়ে, আলাদা পথে, programming language-এর জগতে একটি সমস্যা দেখা দিয়েছিল: নতুন ভাষা ALGOL-এর syntax কাগজে এমনভাবে লিখতে হবে, যাতে বিভিন্ন দেশের compiler লেখকেরা একই জিনিস বোঝেন। ইংরেজি বাক্যে লেখা নিয়ম ছিল দ্ব্যর্থক আর অসম্পূর্ণ।
John Backus ১৯৫৯ সালে প্যারিসের একটি আন্তর্জাতিক সম্মেলনে ALGOL 58-এর syntax লেখার একটি formal রীতি উপস্থাপন করেন বলে পরিচিত। Peter Naur ALGOL 60-এর report (১৯৬০, সংশোধিত রূপ ১৯৬৩) সম্পাদনার সময় রীতিটি সামান্য বদলে ব্যবহার করেন, আর সেই report-ই রীতিটিকে বিখ্যাত করে। “Backus Normal Form” নামটি পরে “Backus–Naur Form” হয়; Donald Knuth ১৯৬৪ সালের একটি চিঠিতে এই নাম প্রস্তাব করেছিলেন বলে উল্লেখ পাওয়া যায়। পরে দেখা গেল, BNF আর Chomsky-র context-free grammar একই জিনিস, শুধু লেখার রীতি আলাদা। প্রাচীন ভারতের পাণিনির সংস্কৃত ব্যাকরণের নিয়ম-ভিত্তিক গঠনের সঙ্গে এর মিল দেখে কেউ কেউ “Panini–Backus Form” নামও প্রস্তাব করেছিলেন; তবে এটি একটি তুলনা, সরাসরি উৎস নয়।
এই মিলনের ফল বিশাল। একবার syntax একটি CFG হলে, grammar থেকে parser স্বয়ংক্রিয়ভাবে বানানো যায় (পর্ব ৪০-এর parser generator), grammar-এর ধর্ম গণিতে প্রমাণ করা যায়, আর ভাষার মানক দলিলে নিয়মগুলো দ্ব্যর্থহীনভাবে লেখা যায়। Niklaus Wirth ১৯৭৭ সালে EBNF-এর একটি রূপ প্রস্তাব করেন, আর পরে ISO এর একটি মানক রূপ প্রকাশ করে। আজকের অনেক RFC বা ভাষার মানক দলিল BNF-এরই কোনো রূপে syntax লেখে।
মূল উপলব্ধি: একটি গাণিতিক ধারণা দুটি ভিন্ন সমস্যার, মানুষের ভাষা আর যন্ত্রের ভাষা, একই উত্তর হয়ে উঠেছিল। CFG জনপ্রিয় হয়েছে কারণ এটি যথেষ্ট শক্তিশালী (নেস্টিং লেখে) আবার যথেষ্ট সরল (দক্ষভাবে parse করা যায়)।
প্র ০২বাস্তবের কিছু “regex” engine সুষম বন্ধনী চিনতে পারে বলে দাবি করা হয়। তাহলে কি regular language-এর সীমার প্রমাণ ভুল?
না, প্রমাণ ঠিক আছে; বদলেছে শুধু “regex” শব্দের অর্থ। গণিতে regular expression মানে শুধু ∅, ε, একটি চিহ্ন, union, concatenation আর star. পর্ব ১৭-এর pumping lemma আর পর্ব ১৮-এর Myhill–Nerode দেখায়, এই কাঠামো দিয়ে সুষম বন্ধনী বা anbn লেখা অসম্ভব, কারণ সমতুল্য যন্ত্রটি সসীম স্মৃতির।
কিন্তু প্রোগ্রামিং-এর regex library-গুলো বহু বছর ধরে নতুন ক্ষমতা যোগ করেছে। Backreference (যেমন একই অংশ আবার মেলানো, ধরুন (a+)\1) দিয়ে ww ধরনের ভাষা চেনা যায়, যা context-free-ও নয়। PCRE আর তার উত্তরসূরি কয়েকটি engine recursive pattern সমর্থন করে, যেখানে একটি pattern নিজেকেই ডাকতে পারে; এটি আসলে একটি grammar-এর নিয়ম, regex-এর ছদ্মবেশে। .NET-এর regex-এ “balancing group” নামে একটি সুবিধা আছে, যা একটি counter-এর মতো কাজ করে। এসব থাকলে “regex” আর regular language-এর শ্রেণির মধ্যে আটকে থাকে না।
এর একটি দাম আছে। পর্ব ২১-এ দেখেছেন, backtracking-ভিত্তিক engine কিছু pattern-এ ইনপুটের দৈর্ঘ্যের সঙ্গে exponential সময় নিতে পারে, আর backreference-সহ মেলানোর সাধারণ সমস্যাটি NP-hard বলে পরিচিত। অন্যদিকে খাঁটি regular expression সবসময় একটি DFA-তে বদলানো যায় আর linear সময়ে চলে; কিছু engine (যেমন RE2-এর ধারা) এই নিশ্চয়তার জন্য ইচ্ছা করে backreference বাদ দেয়। বাস্তব প্রকৌশলের পরামর্শটি সহজ: নেস্টিং থাকলে (JSON, HTML, query ভাষা) একটি grammar আর parser লিখুন; regex দিয়ে কাঠামো পড়ার চেষ্টা প্রায়ই ভঙ্গুর আর ধীর হয়।
মূল উপলব্ধি: তত্ত্বের “regular” আর বাস্তবের “regex” একই নাম, ভিন্ন জিনিস। Recursion যোগ করলেই আপনি grammar-এর জগতে চলে আসেন, তখন grammar-এর সরঞ্জাম, নিশ্চয়তা আর সীমাগুলোও সঙ্গে আসে।
প্র ০৩দুটি CFG একই language তৈরি করে কি না, কম্পিউটার দিয়ে কি সবসময় যাচাই করা যায়? তাহলে হাতে প্রমাণের দরকার কেন?
এই পর্বে আমরা brute force দিয়ে দৈর্ঘ্য ৮ বা ১০ পর্যন্ত দুটি language মিলিয়েছি। প্রশ্নটি স্বাভাবিক: আরও বড় দৈর্ঘ্যে, বা চতুর কোনো algorithm দিয়ে, কি পুরো অসীম language মেলানো যায়? Regular language-এর ক্ষেত্রে উত্তর হ্যাঁ: পর্ব ২০-এ দেখেছেন, দুটি DFA minimize করে বা product construction দিয়ে equivalence decidable.
CFG-এর ক্ষেত্রে উত্তর না। “দুটি CFG কি একই language তৈরি করে?” প্রশ্নটি undecidable, অর্থাৎ এমন কোনো algorithm নেই যা সব grammar-জোড়ায় সঠিক উত্তর দিয়ে থামে। এমনকি “এই CFG কি Σ∗-এর প্রতিটি string তৈরি করে?” প্রশ্নটিও undecidable. এই ফলাফল ১৯৬০-এর দশকের শুরুতে Bar-Hillel, Perles ও Shamir-এর কাজের ধারা থেকে আসে বলে পরিচিত, আর পর্ব ৫৪-এ Post correspondence problem দিয়ে এর প্রমাণ দেখবেন। অন্যদিকে কিছু প্রশ্ন decidable: একটি string L(G)-এ আছে কি না (পর্ব ৩১-এর CYK), আর L(G) ফাঁকা কি না (পর্ব ২৮-এর generating symbol-এর হিসাব)।
তাই brute force-এর ভূমিকা স্পষ্ট: এটি ভুল ধরার জাল, প্রমাণ নয়। দৈর্ঘ্য ১০ পর্যন্ত মিলে গিয়েও দৈর্ঘ্য ৫০-এ পার্থক্য থাকতে পারে, আর কোনো সাধারণ সীমা নেই যার পরে আর দেখার দরকার হয় না (থাকলে প্রশ্নটি decidable হয়ে যেত)। প্রতিটি নির্দিষ্ট grammar-এর জন্য অবশ্য প্রমাণ লেখা যায়, যেমন উপপাদ্য ৬.১; সেই প্রমাণ মানুষের অন্তর্দৃষ্টি থেকে আসে: কোন invariant রক্ষা পায়, string কোথায় ভাঙা যায়। এ কারণেই পরীক্ষায় “প্রমাণ করুন L(G) = L” একটি মূল দক্ষতা, আর কোনো tool এটি পুরোপুরি স্বয়ংক্রিয় করতে পারবে না।
মূল উপলব্ধি: CFG-এর equivalence undecidable, তাই প্রতিটি “এই grammar ঠিক” দাবির পেছনে একটি মানুষের লেখা যুক্তি লাগে। Brute force সেই যুক্তির ভুল দ্রুত ধরে, কিন্তু যুক্তির জায়গা নেয় না।
প্র ০৪মানুষের মুখের ভাষা, যেমন বাংলা বা ইংরেজি, কি context-free? এই প্রশ্নের উত্তর কীভাবে খোঁজা হয়েছে?
Chomsky নিজে ১৯৫০-এর দশকে যুক্তি দিয়েছিলেন যে finite-state মডেল ইংরেজির জন্য যথেষ্ট নয়, কারণ “if … then …”-এর মতো কাঠামো যেকোনো গভীরে নেস্ট হতে পারে, ঠিক বন্ধনীর মতো। কিন্তু context-free grammar কি যথেষ্ট? কয়েক দশক ধরে এ নিয়ে বিতর্ক চলেছে। অনেক প্রস্তাবিত “প্রমাণ” পরে ভুল প্রমাণিত হয়েছিল, কারণ সেগুলো ভাষার একটি স্বাভাবিক অংশকে খুব কঠোরভাবে formal language হিসেবে ধরেছিল।
সবচেয়ে পরিচিত গ্রহণযোগ্য যুক্তিটি Stuart Shieber-এর ১৯৮৫ সালের প্রবন্ধে, সুইজারল্যান্ডের একটি জার্মান উপভাষা নিয়ে। সেখানে কিছু বাক্যে কয়েকটি কর্ম পরপর আসে, তারপর তাদের ক্রিয়া একই ক্রমে পরপর আসে, আর প্রতিটি ক্রিয়ার ব্যাকরণগত রূপ তার জোড়া কর্মের সঙ্গে মিলতে হয়। গঠনটি “আড়াআড়ি নির্ভরতা” (cross-serial dependency), অনেকটা ambncmdn-এর মতো, যেখানে মিল নেস্ট হয় না, কাটাকাটি করে। Shieber regular language-এর সঙ্গে intersection আর homomorphism-এর মতো closure property ব্যবহার করে দেখান, এই উপভাষা context-free হতে পারে না, যদি ধরা হয় সেখানে এমন বাক্য যেকোনো দৈর্ঘ্যে সম্ভব।
এর পর ভাষাবিজ্ঞানে “mildly context-sensitive” শ্রেণির grammar জনপ্রিয় হয়, যেমন tree-adjoining grammar: এগুলো CFG-এর চেয়ে সামান্য বেশি শক্তিশালী, কিন্তু parse করা এখনো polynomial সময়ে সম্ভব। মজার কথা, বাস্তবে বেশিরভাগ বাক্যের গঠন CFG দিয়েই ভালোভাবে ধরা যায়; সমস্যা শুধু কিছু বিশেষ গঠনে। আর আধুনিক ভাষা-মডেল কোনো লেখা grammar ব্যবহার করে না, যদিও তারা আসলে কোন শ্রেণির কাঠামো শেখে, তা নিয়ে গবেষণা চলছে (মডিউল ১৩-এ এর ছোঁয়া পাবেন)।
মূল উপলব্ধি: মানুষের ভাষা প্রায় context-free, কিন্তু পুরোপুরি নয়। নেস্টিং CFG সহজে লেখে; আড়াআড়ি মিল লিখতে পারে না, আর এই পার্থক্যই anbn আর anbncn-এর পার্থক্য।
প্র ০৫C বা Python-এর পুরো syntax কি একটি CFG দিয়ে লেখা যায়? Compiler-এ CFG-এর সীমা কোথায়?
সংক্ষেপে: কাঠামোর বেশিরভাগ যায়, কিন্তু “বৈধ program” পুরোটা নয়। প্রতিটি ভাষার মানক দলিলে একটি grammar থাকে, আর parser সেটি দিয়ে বন্ধনী, block, expression আর statement-এর কাঠামো বোঝে। কিন্তু অনেক নিয়ম grammar-এর বাইরে। “ব্যবহারের আগে variable declare করতে হবে” নিয়মটি ভাবুন। এর formal রূপ অনেকটা {wcw}-এর মতো: একটি নাম আগে একবার, পরে আবার একই নাম; এই ধরনের মিল context-free নয়। তাই compiler কাজটি দুই স্তরে ভাগ করে: grammar দিয়ে কাঠামো, তারপর symbol table আর type checking দিয়ে অর্থের নিয়ম (semantic analysis).
C-তে একটি বিখ্যাত জটিলতা আছে: “A * B;” লাইনটি A যদি একটি typedef-করা type হয় তবে একটি pointer declaration, নইলে একটি গুণের expression. শুধু grammar দেখে বলা যায় না কোনটি; কোন নাম আগে typedef হয়েছে, সেই তথ্য লাগে। প্রচলিত সমাধানে parser symbol table থেকে lexer-কে তথ্য পাঠায়, যাতে lexer typedef-নামকে আলাদা token হিসেবে দেয়; একে প্রায়ই “lexer hack” বলা হয়। Python-এ indentation-ই block বোঝায়, যা সরাসরি CFG-তে লেখা কঠিন। সমাধান আবার lexer-এ: tokenizer একটি stack-এ indentation-এর মাপ রাখে আর INDENT ও DEDENT নামের token তৈরি করে। এরপর grammar-এ এগুলো বন্ধনীর মতো কাজ করে, আর বাকিটা আবার context-free.
এর শিক্ষা হলো একটি পরিচিত প্রকৌশল-নকশা: কঠিন অংশগুলো lexer বা পরের ধাপে ঠেলে দিয়ে মাঝের parser-কে context-free রাখা, কারণ CFG-এর জন্য দক্ষ parsing algorithm আর parser generator আছে (মডিউল ৭)। বাজারঘরের order-query-তেও একই ভাগ: grammar নিশ্চিত করে NUM শুধু amount-এর পরে আসে, কিন্তু “district-এর মান কি সত্যিই একটি জেলার নাম?” প্রশ্নটি parser-এর পরের ধাপের কাজ। Compiler-এর পুরো নির্মাণ একটি ভবিষ্যৎ “Programming Languages & Compilers” কোর্সের বিষয়।
মূল উপলব্ধি: বাস্তবের ভাষা পুরোপুরি context-free নয়, কিন্তু প্রকৌশলীরা ইচ্ছা করে কাঠামোর অংশটিকে context-free রাখেন, আর বাকি নিয়ম lexer ও semantic analysis-এ সামলান। CFG তাই পুরো সমাধান নয়, কিন্তু সমাধানের মেরুদণ্ড।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। cfg_language.py ব্লকের tests তালিকায় নিজের grammar আর সংজ্ঞা বসিয়ে উত্তর যাচাইও করতে পারেন।
-
নকশা: নিচের প্রতিটি language-এর জন্য একটি CFG নকশা করুন। (ক) {aibj : i ≠ j}; (খ) {wcwR : w ∈ {a, b}∗}, যেখানে wR হলো w-এর reversal; (গ) {aibjck : j = i + k}.
(ক) ক্ষেত্রভিত্তিক union: i > j অথবা i < j. মিলিয়ে মোড়ানোর পর মাঝখানে অন্তত একটি বাড়তি a বা অন্তত একটি বাড়তি b: S → aSb ∣ A ∣ B, A → aA ∣ a, B → bB ∣ b. ε নেই (i = j = 0), ab নেই, কিন্তু a, b, aab আছে। ভুল এড়ান: A → aA ∣ ε দিলে i = j-ও ঢুকে পড়ত।
(খ) দুই প্রান্তে একই চিহ্ন, মাঝখানে c: S → aSa ∣ bSb ∣ c. এটি palindrome-এর grammar, শুধু মাঝখানটি নির্দিষ্ট করে চিহ্নিত।
(গ) অংশে ভাগ: aibi+kck = (aibi)(bkck). S → XY, X → aXb ∣ ε, Y → bYc ∣ ε.
তিনটি grammar-ই scratch-এ brute force-এ সংজ্ঞার সঙ্গে মিলেছে: (ক) দৈর্ঘ্য ১০ পর্যন্ত, (খ) আর (গ) দৈর্ঘ্য ৯ পর্যন্ত।
-
প্রমাণ: G: S → aSbS ∣ bSaS ∣ ε. প্রমাণ করুন L(G) = EQ = {w ∈ {a, b}∗ : w-এ a আর b সমান সংখ্যক}. দুটি দিকই পূর্ণ লিখুন।
⊆: দাবি: প্রতিটি sentential form-এ a-এর সংখ্যা = b-এর সংখ্যা. Derivation-এর দৈর্ঘ্যের ওপর induction: শুরুতে S-এ দুটিই 0. প্রতিটি ধাপে একটি S বদলায়; aSbS আর bSaS দুটিই একটি a আর একটি b যোগ করে, ε কিছুই যোগ করে না; তাই সমতা রক্ষা পায়। L(G)-এর প্রতিটি w একটি sentential form, তাই w ∈ EQ.
⊇: |w|-এর ওপর strong induction. |w| = 0 হলে w = ε, আর S ⇒ ε. ধরুন |w| > 0, w ∈ EQ, আর ছোট দৈর্ঘ্যের EQ-এর প্রতিটি string S থেকে আসে। ধরুন w শুরু হয় a দিয়ে (b দিয়ে হলে একই যুক্তি, a আর b অদলবদল করে bSaS). d(t) = w-এর প্রথম t চিহ্নে a-এর সংখ্যা − b-এর সংখ্যা. d(1) = 1, d(|w|) = 0, আর প্রতি ধাপে d এক করে বদলায়; তাই একটি ক্ষুদ্রতম t > 1 আছে যেখানে d(t) = 0, আর t-তম চিহ্ন b (d 1 থেকে 0-তে নেমেছে)। তাহলে w = aubv, যেখানে u = মাঝের t − 2টি চিহ্ন আর v = বাকি অংশ. d(1) = 1 আর d(t − 1) = 1, তাই u-তে a আর b সমান; d(t) = d(|w|) = 0, তাই v-তেও সমান। |u|, |v| < |w|, তাই induction-এ S ⇒∗ u আর S ⇒∗ v. ফলে S ⇒ aSbS ⇒∗ aubv = w. ∎
উদাহরণ: w = abba. d: 1, 0, … তাই t = 2, u = ε, v = ba; S ⇒ aSbS ⇒ abS ⇒ abbSaS ⇒ abbaS ⇒ abba.
-
Output অনুমান: cfg_language.py-এর
langfunction-এ G = {"S": ["aSb", "SS", ""]} আর n = 4 দিলে কোন কোন string আসবে? (খ) a-কে “(” আর b-কে “)” পড়লে এই language কোনটি?(ক) চারটি string: ε, ab, aabb, abab. aSb থেকে ab আর aabb; SS থেকে দুটি ab পাশাপাশি, abab. দৈর্ঘ্য ৩-এর কিছু নেই, কারণ প্রতিটি নিয়ম a আর b জোড়ায় যোগ করে। ba বা abba আসে না, কারণ প্রতিটি টুকরো a দিয়ে শুরু আর b দিয়ে শেষ, আর ভেতরে কোনো prefix-এ b কখনো a-এর বেশি হয় না। Scratch-এ চালিয়ে ঠিক এই চারটি এসেছে।
(খ) এটি সুষম বন্ধনীর language, অর্থাৎ BAL-এর আরেকটি grammar (এক রকম বন্ধনীর Dyck language). Scratch-এ দৈর্ঘ্য ১০ পর্যন্ত BAL-এর সঙ্গে হুবহু মিলেছে। একই language-এর অনেক grammar থাকতে পারে; S → (S)S ∣ ε ছোট, আর S → (S) ∣ SS ∣ ε পড়তে সহজ, কিন্তু দ্বিতীয়টি ambiguous (পর্ব ২৭)।
-
Closure-এর গঠন: L = {anbn : n ≥ 0}∗ ∪ PAL, যেখানে PAL হলো {a, b}-এর ওপর সব palindrome. (ক) উপপাদ্য ৮.১ দিয়ে L-এর একটি CFG লিখুন। (খ) L-এ দৈর্ঘ্য ৪-এর কয়টি string আছে, আর কোনগুলো?
(ক) আগে প্রতিটি অংশের variable আলাদা করুন। anbn: A → aAb ∣ ε. তার star: X → AX ∣ ε. PAL: P → aPa ∣ bPb ∣ a ∣ b ∣ ε. Union: S → X ∣ P. মোট grammar: S → X ∣ P, X → AX ∣ ε, A → aAb ∣ ε, P → aPa ∣ bPb ∣ a ∣ b ∣ ε.
(খ) ছয়টি। Star-অংশ থেকে: aabb (একটি টুকরো) আর abab (দুটি ab). Palindrome থেকে: aaaa, abba, baab, bbbb. কোনোটি দুই অংশে একসঙ্গে নেই, কারণ star-অংশের প্রতিটি অ-ফাঁকা string a দিয়ে শুরু আর b দিয়ে শেষ, তাই palindrome নয়। Scratch-এ grammar থেকে দৈর্ঘ্য ৪-এর ঠিক এই ছয়টি এসেছে।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি language-এর বর্ণনা থেকে CFG নকশা আর যাচাইয়ের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- ছোট উদাহরণ আর পাল্টা-উদাহরণ লেখা, ε আছে কি না ঠিক করা
- string-কে অংশে বা ক্ষেত্রে ভাগ করা (concatenation বা union)
- প্রতিটি অংশের নিয়ম লেখা, মিলিয়ে গোনার জন্য recursion দিয়ে
- নতুন start symbol দিয়ে অংশগুলো জোড়া
- ছোট দৈর্ঘ্যে সব string brute force-এ সংজ্ঞার সঙ্গে মেলানো
- L(G) ⊆ L আর L ⊆ L(G) দুই দিক প্রমাণ করা
V = {S, B} আর Σ = {a, b} হলে নিচের কোন নিয়মটি একটি context-free grammar-এ থাকতে পারে না?
- S → aSb
- B → ε
- aB → b
- S → SS
কোন grammar ঠিক {aibj : 0 ≤ i ≤ j} তৈরি করে?
- S → aSb ∣ B, B → bB ∣ ε
- S → aSb ∣ ε
- S → aS ∣ Sb ∣ ε
- S → aSbb ∣ ε
একটি CFG G আর একটি language L-এর জন্য L(G) = L প্রমাণ করতে ঠিক কী দেখাতে হয়?
- L-এর প্রতিটি string G থেকে derive করা যায়
- G-এর প্রতিটি terminal string L-এ আছে
- দৈর্ঘ্য ১০ পর্যন্ত সব string-এ দুটি মেলে
- L(G) ⊆ L এবং L ⊆ L(G), দুটিই
কেউ দাবি করলেন, S → aSb ∣ bSa ∣ ε grammar-টি {w ∈ {a, b}∗ : a আর b সমান সংখ্যক} তৈরি করে। কোন string দাবিটি খণ্ডন করে?
- ab
- abab
- abba
- bbaa
L1 আর L2 দুটি context-free language. নিচের কোনটি সবসময় context-free হবে, এমন নিশ্চয়তা নেই?
- L1 ∪ L2
- L1 ∩ L2
- L1L2
- L1∗
“1-এর সংখ্যা জোড়” DFA-র state E (শুরু, accepting) আর O থেকে বানানো right-linear grammar E → 0E ∣ 1O ∣ ε, O → 0O ∣ 1E. এতে 101-এর derivation কোনটি?
- E ⇒ 1O ⇒ 10O ⇒ 101E ⇒ 101
- E ⇒ 1O ⇒ 10O ⇒ 10
- E ⇒ 1E ⇒ 10E ⇒ 101E ⇒ 101
- E ⇒ 1O ⇒ 10E ⇒ 101O
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- CFG G = (V, Σ, R, S): প্রতিটি নিয়ম A → α, বাঁ দিকে ঠিক একটি variable; L(G) = {w ∈ Σ∗ : S ⇒∗ w}.
- নিজের ভেতরে নিজেকে বসানো নিয়ম (S → aSb, S → (S)S) নেস্টিং আর মিলিয়ে গোনা লেখে, যা কোনো DFA পারে না।
- নকশা: মিলের জন্য দুই পাশে recursion, জটিল ভাষা অংশে ভাগ (S → XY), শর্তের ক্ষেত্রগুলো union (S → S1 ∣ S2); ε আর প্রান্তের ক্ষেত্র আলাদা করে দেখা।
- L(G) = L মানে দুই দিক: ⊆ invariant দিয়ে (derivation-এর দৈর্ঘ্যে induction), ⊇ string ভেঙে (দৈর্ঘ্যে induction). Brute force শুধু ভুল ধরে।
- Regular ⊊ context-free (DFA → right-linear grammar; anbn); CFL union, concatenation, star-এ বদ্ধ, intersection-এ নয়।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ০৬ · Chomsky hierarchy-র মানচিত্র — চার শ্রেণির language আর machineফিরে দেখুনGrammar-এর সাধারণ সংজ্ঞা, চার type আর context-free স্তরের অবস্থান।
- পর্ব ১৭ · Regular language-এর pumping lemma — non-regular প্রমাণপটভূমিanbn আর সুষম বন্ধনী কেন regular নয়, যার উত্তর এই পর্বের grammar.
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ২৬ derivation আর parse tree.
- পর্ব ১৬ · Regular language-এর closure propertyতুলনাAutomaton দিয়ে closure-এর গঠন, যার পাশে এই পর্বের grammar-গঠন রাখুন।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৩ — Grammar আর formal languageপাশের ট্র্যাকBNF আর grammar-এর প্রথম পরিচয়, গণিতের দিক থেকে।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ১০ — Mathematical inductionপটভূমিL(G) = L প্রমাণে লাগা সাধারণ আর strong induction.