এই পর্বে যা শিখবেন
- Finite automaton-এর সীমা থেকে stack-এর প্রয়োজন, আর PDA-র formal 6-tuple সংজ্ঞা
- Transition “a, x → y” পড়া, state diagram আঁকা, configuration আর ⊢ দিয়ে computation লেখা
- PDA-তে nondeterminism: wwR-এর জন্য মাঝখান অনুমান, আর কেন এখানে subset construction কাজ করে না
- anbn, সুষম বন্ধনী, wwR আর সমান a ও b-এর PDA নকশা, আর stack invariant দিয়ে সঠিকতার প্রমাণ
- Python-এ configuration-এর ওপর BFS দিয়ে PDA চালানো, আর PDA, DFA ও Turing machine-এর তুলনা
১ · কেন stack — সসীম স্মৃতির বাইরে গোনা আর নেস্টিং
পর্ব ১৭-এ প্রমাণ হয়েছে, anbn = {ε, ab, aabb, …} regular নয়. কারণ কোনো finite automaton-এর state সংখ্যা সসীম, অথচ কতগুলো a পড়া হয়েছে তা মনে রাখতে যেকোনো বড় সংখ্যা লাগতে পারে। আবার পর্ব ২৫-এ দেখেছেন, এই ভাষাটি একটি ছোট grammar S → aSb ∣ ε দিয়ে সহজেই লেখা যায়। Grammar ভাষা তৈরি করে; এখন প্রশ্ন, কোন যন্ত্র এমন ভাষা চেনে? উত্তর: finite automaton-এর সঙ্গে একটি stack.
বিয়েবাড়ির থালার স্তূপের কথা ভাবুন। ধোয়া থালা আসে আর স্তূপের ওপরে রাখা হয়; পরিবেশন করার সময় তোলা হয় ওপর থেকেই। যে থালা সবার শেষে রাখা হয়েছে, সেটিই সবার আগে বের হয় (last in, first out). স্তূপটি যত উঁচু ইচ্ছা হতে পারে, কিন্তু আপনি দেখতে পান শুধু সবচেয়ে ওপরের থালা। পরিবেশক কাউন্টার থেকে প্রতিটি অতিথিকে একটি থালা দেন; শেষে স্তূপ ফাঁকা হলে বোঝা যায়, অতিথি আর থালার সংখ্যা সমান ছিল। পুরো হিসাব হলো, অথচ পরিবেশককে কোনো সংখ্যা মনে রাখতে হয়নি।
anbn চেনার কৌশল ঠিক এটাই। প্রতিটি a পড়ার সময় stack-এ একটি চিহ্ন push করুন (ওপরে রাখুন)। a শেষ হয়ে b শুরু হলে প্রতিটি b-এর জন্য একটি চিহ্ন pop করুন (ওপর থেকে তুলুন)। Input শেষে stack ঠিক ফাঁকা হলে, আর কোথাও a-এর পরে আবার a আসেনি, তবেই string-টি গ্রহণযোগ্য। যন্ত্রের সসীম অংশ (state) মনে রাখে শুধু “এখন a-এর পর্যায়ে না b-এর পর্যায়ে”; গোনার কাজটি করে stack.
সুষম বন্ধনী আরও স্বাভাবিক উদাহরণ। বাজারঘরের order-query ভাষায় শর্তগুলো বন্ধনী দিয়ে যত গভীরে ইচ্ছা নেস্ট করা যায়, যেমন “( amount >= 1000 AND ( district = "Dhaka" OR status = "paid" ) )”. প্রতিটি “(” stack-এ রাখুন, প্রতিটি “)” এলে ওপরের “(” তুলুন। “)” এল অথচ stack ফাঁকা, বা শেষে stack-এ কিছু রয়ে গেল, দুটিই ভুল। Compiler, browser-এর HTML parser আর JSON parser প্রতিদিন ঠিক এই কাজ করে। Stack data structure-এর বিস্তারিত (push, pop, call stack) DSA কোর্সের পর্ব ১৩-এ আছে; এখানে stack একটি গাণিতিক যন্ত্রের অংশ।
PDA-র তিনটি অংশ: (১) একটি input tape, যা বাঁ থেকে ডানে একবার পড়া হয়, পেছনে ফেরা যায় না; (২) সসীম state-এর একটি নিয়ন্ত্রণ, DFA বা NFA-র মতো; (৩) একটি stack, যার আকারের কোনো সীমা নেই, কিন্তু প্রতিটি ধাপে শুধু সবচেয়ে ওপরের চিহ্নটি দেখা যায় বা বদলানো যায়। Stack-এর মাঝখানের কিছু সরাসরি পড়া যায় না; সেটি দেখতে হলে ওপরের সবকিছু তুলে ফেলতে হয়, আর তোলা তথ্য হারিয়ে যায়।
২ · Formal definition — P = (Q, Σ, Γ, δ, q0, F)
সংজ্ঞার আগে একটি ছোট notation. যেকোনো set A-এর জন্য Aε = A ∪ {ε}. Σε-এর একটি উপাদান মানে “একটি input চিহ্ন, অথবা কিছুই না”; Γε-এর একটি উপাদান মানে “একটি stack চিহ্ন, অথবা কিছুই না”। এই কোর্স Sipser-এর রীতি মানে।
একটি pushdown automaton হলো ছয়টি জিনিসের tuple P = (Q, Σ, Γ, δ, q0, F), যেখানে
১. Q একটি সসীম set, এর উপাদান state;
২. Σ একটি সসীম input alphabet;
৩. Γ একটি সসীম stack alphabet (Σ থেকে আলাদা হতে পারে, মিলও থাকতে পারে);
৪. δ: Q × Σε × Γε → P(Q × Γε) হলো transition function;
৫. q0 ∈ Q হলো start state;
৬. F ⊆ Q হলো accept state-এর set.
δ-এর অর্থ কথায়: বর্তমান state q, input থেকে পড়া চিহ্ন a (বা ε, কিছু না পড়ে), আর stack-এর ওপর থেকে তোলা চিহ্ন x (বা ε, কিছু না তুলে), এই তিনটি দিলে δ(q, a, x) হলো সম্ভাব্য পরের পদক্ষেপের একটি set: প্রতিটি জোড় (r, y) মানে “state r-এ যান আর stack-এ y রাখুন”। P(Q × Γε) হলো Q × Γε-এর power set, তাই একই অবস্থায় শূন্য, এক বা একাধিক পদক্ষেপ থাকতে পারে। অর্থাৎ সংজ্ঞাতেই PDA nondeterministic, যেমন পর্ব ০৯-এর NFA.
(r, y) ∈ δ(q, a, x)-কে ছবিতে আর লেখায় সংক্ষেপে লেখা হয়
পড়ুন: “a পড়ে, x তুলে, y রেখে, q থেকে r-এ যান”। চারটি বিশেষ রূপ প্রায়ই আসবে: a, ε → x (a পড়ে x push), a, x → ε (a পড়ে x pop), ε, ε → $ (কিছু না পড়ে, কিছু না তুলে $ push), আর ε, x → ε (কিছু না পড়ে x pop). x ≠ ε হলে move-টি শুধু তখনই খাটে, যখন stack-এর ওপরে ঠিক x আছে; x = ε হলে stack-এর অবস্থা যা-ই হোক, খাটে। a = ε হলে move-টি একটি ε-move: input-এর কিছু খরচ হয় না।
Stack ফাঁকা কি না, PDA সরাসরি জানে না। সংজ্ঞায় “stack ফাঁকা হলে” পরীক্ষার কোনো নিয়ম নেই। তাই প্রথম move-এই একটি বিশেষ তলার চিহ্ন $ push করা হয়: ε, ε → $. পরে ওপরে $ দেখা মানেই “আমার রাখা সব চিহ্ন উঠে গেছে”। এই পর্বের প্রতিটি PDA এভাবে শুরু হয়। $ ∈ Γ, কিন্তু $ ∉ Σ.
এবার প্রথম পূর্ণ PDA. P1 = ({q1, q2, q3, q4}, {a, b}, {a, $}, δ, q1, {q1, q4}), যার transition নিচের সারণিতে। যে ঘর লেখা নেই, সেখানে δ-এর মান ∅.
| state | পড়া | তোলা | পরের state, রাখা | অর্থ |
|---|---|---|---|---|
| q1 | ε | ε | (q2, $) | তলার চিহ্ন বসানো |
| q2 | a | ε | (q2, a) | প্রতিটি a জমা |
| q2 | b | a | (q3, ε) | প্রথম b: মেলানো শুরু |
| q3 | b | a | (q3, ε) | প্রতিটি পরের b-তে একটি a তোলা |
| q3 | ε | $ | (q4, ε) | সব a মিলেছে, গ্রহণে যাওয়া |
q1 নিজেও accept state, যাতে ε গৃহীত হয় (n = 0). q3-এ আর a পড়ার কোনো নিয়ম নেই, তাই b-এর পরে a এলে সেই পথ আটকে যায়: aba-র মতো string এভাবেই বাদ পড়ে। নিচের state diagram-এ একই যন্ত্র।
P1: anbn-এর PDA
প্রতিটি তীরে “পড়া, তোলা → রাখা”. দুই দাগের বৃত্ত accept state; বাঁ দিকের খোলা তীর start state q1-এ।
অন্য বইয়ের রীতি: Hopcroft–Motwani–Ullman (HMU) PDA-কে 7-tuple (Q, Σ, Γ, δ, q0, Z0, F) হিসেবে লেখেন। সেখানে stack শুরুতেই একটি start symbol Z0 নিয়ে থাকে, তাই আলাদা করে $ push করতে হয় না; আর প্রতিটি move ঠিক একটি চিহ্ন তোলে আর একটি string (Γ∗) রাখে, যেমন δ(q, a, Z0) ∋ (q, aZ0). দুই রীতির ক্ষমতা সমান: একটি থেকে অন্যটিতে কয়েকটি বাড়তি state দিয়ে যাওয়া যায়। অংশ ৫-এর সত্যিকারের run-এ ব্যবহৃত library HMU রীতি মানে। ফাঁকা string-এর জন্য কিছু বইয়ে λ লেখা হয়; এই কোর্সে সবসময় ε.
৩ · Configuration আর ⊢ — একটি computation ধাপে ধাপে
DFA-র অবস্থা বোঝাতে শুধু state যথেষ্ট ছিল। PDA-র ভবিষ্যৎ নির্ভর করে তিনটি জিনিসের ওপর: এখন কোন state, input-এর কতটা বাকি, আর stack-এ কী আছে। এই তিনটি মিলে একটি configuration (HMU-তে বলে instantaneous description). পর্ব ২৪-এ বাড়তি variable-সহ state machine-এর configuration দেখেছেন; এখানে বাড়তি স্মৃতি হলো stack.
P-এর একটি configuration হলো (q, w, γ), যেখানে q ∈ Q, w ∈ Σ∗ হলো এখনো না-পড়া input, আর γ ∈ Γ∗ হলো stack-এর পুরো বিষয়বস্তু, সবচেয়ে ওপরের চিহ্ন বাঁয়ে। এক ধাপের yields সম্পর্ক:
(q, aw, xβ) ⊢ (r, w, yβ) যদি (r, y) ∈ δ(q, a, x)
যেখানে a ∈ Σε, x, y ∈ Γε, β ∈ Γ∗. ⊢∗ হলো ⊢-এর reflexive-transitive closure (শূন্য বা বেশি ধাপ)। P যে language গ্রহণ করে:
L(P) = { w ∈ Σ∗ : কোনো f ∈ F আর γ ∈ Γ∗-এর জন্য (q0, w, ε) ⊢∗ (f, ε, γ) }
সংজ্ঞাটি খুঁটিয়ে পড়ুন। শুরুতে stack ফাঁকা (ε)। a = ε হলে aw = w, অর্থাৎ input অপরিবর্তিত; x = ε হলে কিছু তোলা হয় না। গ্রহণের শর্ত দুটি একসঙ্গে: input পুরো পড়া হয়েছে (মাঝের অংশ ε), আর তখন state F-এ। Stack-এ কী রয়ে গেল (γ), তাতে কিছু আসে যায় না; একে বলে final state দিয়ে গ্রহণ, এই কোর্সের মূল রীতি। আরেকটি রীতি, “stack ফাঁকা হলে গ্রহণ”, আর দুটির রূপান্তর আসবে পর্ব ৩৩-এ। Input শেষ হওয়ার পরও ε-move চলতে পারে; P1-এর শেষ ধাপ ε, $ → ε ঠিক এমন। আর যেহেতু nondeterministic, w গৃহীত হতে অন্তত একটি পথ লাগে; অন্য পথগুলো আটকে গেলেও ক্ষতি নেই।
নিচের stepper P1-কে aaabbb দেয়। প্রতিটি ধাপে একটি configuration; বাঁ পাশে যে transition খাটল সেটি উজ্জ্বল।
1q1 → q2 : ε, ε → $2q2 → q2 : a, ε → a3q2 → q3 : b, a → ε4q3 → q3 : b, a → ε5q3 → q4 : ε, $ → ε
| (state, বাকি, stack) | |
| পড়া হয়েছে | |
| stack-এর উচ্চতা |
- শুরু। (q1, aaabbb, ε): state q1, পুরো input বাকি, stack ফাঁকা। q1 ∈ F হলেও এখন গ্রহণ নয়, কারণ input পড়া বাকি।
- তলার চিহ্ন। ε, ε → $: কিছু না পড়ে, কিছু না তুলে $ রাখা হলো। (q1, aaabbb, ε) ⊢ (q2, aaabbb, $).
- প্রথম a. a, ε → a: একটি a পড়া হলো আর stack-এ একটি a উঠল। Stack এখন a$, ওপরে a.
- দ্বিতীয় a. একই নিয়ম আবার। Stack aa$. লক্ষ করুন, q2 একটি মাত্র state, অথচ যন্ত্রটি গুনছে; গোনাটি stack-এর উচ্চতায়।
- তৃতীয় a. Stack aaa$, উচ্চতা ৪. বাকি input bbb.
- প্রথম b. b, a → ε: b পড়া হলো, ওপর থেকে একটি a উঠল, যন্ত্র q3-তে। এখন থেকে আর a নেওয়ার নিয়ম নেই।
- দ্বিতীয় b. q3-এর নিজের নিয়ম b, a → ε. Stack a$.
- তৃতীয় b. আবার pop. Input শেষ, stack-এ শুধু $. তিনটি a তিনটি b-এর সঙ্গে মিলেছে।
- গ্রহণ। ε, $ → ε: $ দেখে q4-এ যাওয়া। (q4, ε, ε)-তে input শেষ আর q4 ∈ F, তাই aaabbb ∈ L(P1). মোট ৮টি move: ১ + ৩ + ৩ + ১; সাধারণভাবে anbn-এ (n ≥ 1) ঠিক 2n + 2টি।
পুরো computation এক লাইনে: (q1, aaabbb, ε) ⊢ (q2, aaabbb, $) ⊢ (q2, aabbb, a$) ⊢ ⋯ ⊢ (q4, ε, ε), অর্থাৎ (q1, aaabbb, ε) ⊢∗ (q4, ε, ε). এবার একটি বাতিল string. P1 যে aabbb গ্রহণ করে না, তা দেখাতে প্রমাণ করতে হয় যে কোনো পথই গ্রহণে শেষ হয় না। P1-এ প্রতিটি configuration থেকে বড়জোর একটি move খাটে, তাই এখানে পথ একটিই।
1q1 → q2 : ε, ε → $2q2 → q2 : a, ε → a3q2 → q3 : b, a → ε4q3 → q3 : b, a → ε5q3 → q4 : ε, $ → ε
| (state, বাকি, stack) | |
| পরের b পড়া যায়? |
- শুরু। (q1, aabbb, ε). q1 accept state হলেও input বাকি, তাই এটি গ্রহণ নয়। শুধু ε-ই q1-এ গৃহীত হয়।
- $ বসানো। একমাত্র সম্ভাব্য move ε, ε → $.
- a জমা। Stack a$.
- আরও a. Stack aa$. বাকি bbb, কিন্তু জমা মাত্র দুটি a.
- প্রথম b. b, a → ε, q3-তে। Stack a$.
- দ্বিতীয় b. Stack শুধু $. এখন তৃতীয় b পড়তে হলে ওপরে a লাগবে, কিন্তু ওপরে $; তাই b, a → ε খাটে না।
- আটকে যাওয়া। একমাত্র যে move খাটে তা ε, $ → ε, যা যন্ত্রকে q4-এ নেয়। কিন্তু একটি b এখনো বাকি আর q4 থেকে কোনো transition নেই। এখানে থেমে যাওয়া configuration (q4, b, ε)-এ input শেষ হয়নি, তাই এটি গ্রহণ নয়। আর কোনো পথ নেই, তাই aabbb ∉ L(P1). PDA “ভুল” বলে চিৎকার করে না; গ্রহণের কোনো পথ না থাকাই বাতিল।
একইভাবে aab-তে computation থামে (q3, ε, a$)-এ: input শেষ, কিন্তু q3 ∉ F, আর $ ওপরে নেই বলে q4-এ যাওয়াও যায় না। ba-তে প্রথম b-এর সময় ওপরে $, তাই q2-তেই আটকে যায়। তিনটি ব্যর্থতা তিন রকম: বেশি b, বেশি a, ভুল ক্রম।
৪ · PDA-তে nondeterminism — মাঝখান অনুমান করা
এবার wwR = {wwR : w ∈ {a, b}∗}, অর্থাৎ জোড় দৈর্ঘ্যের palindrome: ε, aa, abba, baab, … (wR মানে w-এর reversal). কৌশলটি আগের মতোই: প্রথম অর্ধেক stack-এ push, দ্বিতীয় অর্ধেক পড়ার সময় pop করে মেলানো। Stack-এর LIFO স্বভাব এখানে আশীর্বাদ: শেষে রাখা চিহ্ন আগে ওঠে, তাই তোলা চিহ্নগুলো ঠিক উল্টো ক্রমে আসে, যা wR-এর সঙ্গে মেলানোর জন্য দরকার।
সমস্যা একটি: যন্ত্র বাঁ থেকে পড়ছে, কোথায় মাঝখান তা জানবে কীভাবে? abba-তে মাঝখান দুটি চিহ্নের পরে, aabbaa-তে তিনটির পরে, আর input-এর শেষ না দেখে এটি জানার উপায় নেই। সমাধান nondeterminism: প্রতিটি অবস্থানে যন্ত্র একটি ε-move দিয়ে “মাঝখান এখানে” অনুমান করতে পারে। এটি পর্ব ০৯-এর guess and verify ছক: অনুমান করুন, তারপর deterministic ধাপে যাচাই করুন। ভুল অনুমানের পথ আপনা থেকেই মরে যায়।
P2: wwR-এর PDA
q2-তে push, q2 → q3 তীরটি অনুমান (কিছু পড়ে না, কিছু তোলে না), q3-তে মিলিয়ে pop. শুধু q4 accept state.
abba-তে মোট পাঁচটি জায়গায় অনুমান করা যায়: কোনো চিহ্ন পড়ার আগে, ১টি, ২টি, ৩টি বা ৪টি চিহ্নের পরে। নিচের stepper প্রতিটি শাখা আলাদা করে দেখায়।
1q1 → q2 : ε, ε → $2q2 : a, ε → a ; b, ε → b3q2 → q3 : ε, ε → ε (অনুমান)4q3 : a, a → ε ; b, b → ε5q3 → q4 : ε, $ → ε
| অনুমান | |
| q3-এ ঢোকার সময় | |
| শেষ configuration |
- শুরু। ε, ε → $ দিয়ে (q2, abba, $). এখন থেকে প্রতিটি অবস্থানে দুটি পছন্দ: পরের চিহ্ন push করা, অথবা ε-move দিয়ে q3-তে যাওয়া।
- অনুমান: ০টির পরে। (q3, abba, $). q3-তে a পড়তে ওপরে a লাগবে, কিন্তু ওপরে $. একমাত্র move ε, $ → ε দেয় (q4, abba, ε): q4 ∈ F, কিন্তু input বাকি আর q4-এ কোনো নিয়ম নেই। শাখা মরে গেল।
- অনুমান: a-এর পরে। a push করে (q3, bba, a$). পরের চিহ্ন b, ওপরে a: মিল নেই। শাখা মরে গেল।
- অনুমান: ab-এর পরে। (q3, ba, ba$). b পড়ে ওপরের b তোলা, a পড়ে ওপরের a তোলা, ওপরে $: ε, $ → ε দিয়ে (q4, ε, ε). Input শেষ, q4 ∈ F: এই শাখা গ্রহণ করে।
- অনুমান: abb-এর পরে। Stack-এ ওপর থেকে b, b, a, $, অর্থাৎ (q3, a, bba$). পরের চিহ্ন a, ওপরে b: মরে গেল।
- অনুমান: abba-র পরে। সব চিহ্ন push হয়ে (q3, ε, abba$). Input শেষ, কিন্তু q3 ∉ F আর ওপরে a, তাই ε, $ → ε-ও খাটে না। মরে গেল।
- সিদ্ধান্ত। পাঁচটি শাখার একটিতে গ্রহণ, তাই abba ∈ L(P2). বাকি চারটির ব্যর্থতায় কিছু আসে যায় না। অংশ ৫-এর simulator এই input-এ মোট ১৫টি আলাদা configuration ছুঁয়েছে, এই পাঁচ শাখারই সব অবস্থা।
এখানে একটি বড় পার্থক্য চোখে পড়ে। পর্ব ১০-এ subset construction দিয়ে প্রতিটি NFA-কে DFA বানানো গিয়েছিল, কারণ NFA-র “সব সম্ভাব্য অবস্থা” একটি সসীম set-এর subset, আর সেগুলোর সংখ্যাও সসীম। PDA-র configuration-এ stack আছে, যা যেকোনো লম্বা হতে পারে; সব সম্ভাব্য stack-এর set আর সসীম নয়। তাই কৌশলটি ভেঙে পড়ে, আর ফলটিও সত্যিই আলাদা: কোনো deterministic PDA wwR চেনে না। এর প্রমাণ সহজ নয়; ধারণা আর উৎস পর্ব ৩৫-এ। মাঝখানে একটি চিহ্নিত c থাকলে (wcwR) অনুমানের দরকার নেই, c দেখেই q3-তে যাওয়া যায়; তাই wcwR deterministic.
৫ · Python-এ PDA simulator — configuration-এর ওপর BFS
PDA চালানো মানে configuration-এর একটি graph ঘোরা: প্রতিটি configuration একটি vertex, প্রতিটি ⊢ একটি তীর। শুরুর configuration থেকে BFS চালিয়ে দেখুন, এমন কোনো configuration-এ পৌঁছানো যায় কি না যেখানে input শেষ আর state F-এ। একটি সমস্যা: ε-move দিয়ে কোনো PDA অবিরাম push করতে পারে (যেমন ε, ε → a নিজের কাছে ফেরা), তখন graph অসীম। তাই ব্লকটি stack-এর উচ্চতায় একটি সীমা রাখে, 2|w| + 2. এই পর্বের যন্ত্রগুলোতে stack কখনো |w| + 1-এর বেশি ওঠে না, তাই সীমাটি এদের কোনো গ্রহণযোগ্য পথ কাটে না; সাধারণ PDA-র জন্য এমন সীমা নিরাপদ কি না, তা আলাদা যুক্তির বিষয় (পর্ব ৩৪-এর grammar-রূপান্তরের পরে membership-এর সঠিক algorithm হলো CYK). প্রতিটি configuration-এর “আগের configuration” মনে রাখা হয়, যাতে গৃহীত হলে পুরো পথ ছাপা যায়।
from collections import deque
def run(P, w): # BFS over configurations (state, rest, stack), top = st[0]
start = (P["q0"], w, "")
parent, todo = {start: None}, deque([start])
while todo:
c = todo.popleft(); q, rest, st = c
if rest == "" and q in P["F"]: # accept: input read, q in F
path = []
while c: path.append(c); c = parent[c]
return path[::-1], len(parent)
for (p, a, x), moves in P["d"].items():
if p == q and rest.startswith(a) and st.startswith(x):
for r, y in moves: # read a, pop x, push y
n = (r, rest[len(a):], y + st[len(x):])
if len(n[2]) <= 2 * len(w) + 2 and n not in parent:
parent[n] = c; todo.append(n)
return None, len(parent) # every branch died
def show(P, w):
path, seen = run(P, w)
print(f"{w}: {'ACCEPT' if path else 'REJECT'} ({seen} configurations seen)")
for q, rest, st in path or []: print(f" ({q}, {rest or 'ε'}, {st or 'ε'})")
# key (state, read, pop) -> [(next state, push)]; "" means ε
ANBN = {"q0": "q1", "F": {"q1", "q4"}, "d": {
("q1", "", ""): [("q2", "$")], ("q2", "a", ""): [("q2", "a")],
("q2", "b", "a"): [("q3", "")], ("q3", "b", "a"): [("q3", "")],
("q3", "", "$"): [("q4", "")]}}
WWR = {"q0": "q1", "F": {"q4"}, "d": { # push half, GUESS the middle
("q1", "", ""): [("q2", "$")],
("q2", "a", ""): [("q2", "a")], ("q2", "b", ""): [("q2", "b")],
("q2", "", ""): [("q3", "")], # the guess: a free ε-move
("q3", "a", "a"): [("q3", "")], ("q3", "b", "b"): [("q3", "")],
("q3", "", "$"): [("q4", "")]}}
show(ANBN, "aaabbb"); show(ANBN, "aabbb"); show(WWR, "abba")আসল আউটপুট (ব্রাউজারের Python):
aaabbb: ACCEPT (9 configurations seen)
(q1, aaabbb, ε)
(q2, aaabbb, $)
(q2, aabbb, a$)
(q2, abbb, aa$)
(q2, bbb, aaa$)
(q3, bb, aa$)
(q3, b, a$)
(q3, ε, $)
(q4, ε, ε)
aabbb: REJECT (7 configurations seen)
abba: ACCEPT (15 configurations seen)
(q1, abba, ε)
(q2, abba, $)
(q2, bba, a$)
(q2, ba, ba$)
(q3, ba, ba$)
(q3, a, a$)
(q3, ε, $)
(q4, ε, ε)
প্রথম পথটি অংশ ৩-এর stepper-এর নয়টি configuration-এর সঙ্গে হুবহু মেলে। aabbb-তে মাত্র ৭টি configuration তৈরি হয়ে BFS ফুরিয়ে গেছে, ঠিক দ্বিতীয় stepper-এর সাতটি ধাপ; কোনোটিতে input শেষ আর state F-এ নয়, তাই REJECT. abba-র পথে চতুর্থ লাইন থেকে পঞ্চম লাইনে input একই (ba), শুধু state q2 থেকে q3: এটিই “ab-এর পরে মাঝখান” অনুমান। ১৫টি configuration-এর মধ্যে বাকিগুলো চারটি মরা শাখার। transition-এর key হলো (state, পড়া, তোলা), আর "" মানে ε; st.startswith(x) পরীক্ষা করে ওপরে x আছে কি না, আর x = "" হলে সেটি সবসময় সত্য। নিজের PDA লিখে show দিয়ে চালিয়ে দেখুন।
একটি বা দুটি string-এ চালানো যথেষ্ট নয়। পরের ব্লক আগের ব্লকের run ব্যবহার করে (একই namespace) আরও দুটি PDA যোগ করে, তারপর চারটি যন্ত্রকে দৈর্ঘ্য ৮ পর্যন্ত প্রতিটি string-এ language-এর গাণিতিক সংজ্ঞার সঙ্গে brute force-এ মেলায়। BAL হলো সুষম বন্ধনী, EQ হলো “a আর b সমান সংখ্যক”; দুটির নকশা অংশ ৬-এ।
from itertools import product
# balanced brackets: push "(" , pop it on ")"
BAL = {"q0": "q1", "F": {"q3"}, "d": {
("q1", "", ""): [("q2", "$")],
("q2", "(", ""): [("q2", "(")], ("q2", ")", "("): [("q2", "")],
("q2", "", "$"): [("q3", "")]}}
# equal a's and b's: the stack holds the surplus (push a string = shorthand)
EQ = {"q0": "q1", "F": {"q3"}, "d": {
("q1", "", ""): [("q2", "$")],
("q2", "a", "$"): [("q2", "a$")], ("q2", "a", "a"): [("q2", "aa")],
("q2", "a", "b"): [("q2", "")],
("q2", "b", "$"): [("q2", "b$")], ("q2", "b", "b"): [("q2", "bb")],
("q2", "b", "a"): [("q2", "")],
("q2", "", "$"): [("q3", "")]}}
def bal(w):
d = 0
for c in w:
d += 1 if c == "(" else -1
if d < 0: return False
return d == 0
tests = [("anbn", ANBN, "ab", lambda w: w == "a" * (len(w) // 2) + "b" * (len(w) // 2)),
("wwR", WWR, "ab", lambda w: len(w) % 2 == 0 and w == w[::-1]),
("BAL", BAL, "()", bal),
("EQ", EQ, "ab", lambda w: w.count("a") == w.count("b"))]
n = 8
for name, P, sigma, inL in tests:
words = ["".join(t) for k in range(n + 1) for t in product(sigma, repeat=k)]
acc = [w for w in words if run(P, w)[0]]
bad = [w for w in words if bool(run(P, w)[0]) != inL(w)]
print(f"{name:4}: {len(words)} strings, {len(acc):3} accepted, "
f"disagreements: {len(bad)} e.g. {', '.join(w or 'ε' for w in acc[:4])}")আসল আউটপুট (ব্রাউজারের Python):
anbn: 511 strings, 5 accepted, disagreements: 0 e.g. ε, ab, aabb, aaabbb
wwR : 511 strings, 31 accepted, disagreements: 0 e.g. ε, aa, bb, aaaa
BAL : 511 strings, 23 accepted, disagreements: 0 e.g. ε, (), (()), ()()
EQ : 511 strings, 99 accepted, disagreements: 0 e.g. ε, ab, ba, aabb
দুই চিহ্নের alphabet-এ দৈর্ঘ্য ০ থেকে ৮ পর্যন্ত 29 − 1 = 511টি string, আর চারটি যন্ত্রই প্রতিটিতে সংজ্ঞার সঙ্গে একমত। সংখ্যাগুলো হাতেও মেলে: anbn-এ দৈর্ঘ্য 0, 2, 4, 6, 8-এ একটি করে, মোট ৫; জোড় palindrome দৈর্ঘ্য 2k-এ 2kটি, 1 + 2 + 4 + 8 + 16 = 31; BAL-এ Catalan সংখ্যা 1 + 1 + 2 + 5 + 14 = 23; EQ-তে C(2k, k)-এর যোগফল 1 + 2 + 6 + 20 + 70 = 99. পর্ব ২৫-এর grammar-গুলোর সংখ্যাও ঠিক এগুলোই ছিল: একই language, একবার grammar দিয়ে তৈরি, একবার যন্ত্র দিয়ে চেনা। এই মিল কাকতালীয় নয়; প্রতিটি CFG-এর একটি সমতুল্য PDA আছে আর উল্টোটিও, যার প্রমাণ পর্ব ৩৪-এ। তবু মনে রাখুন, দৈর্ঘ্য ৮ পর্যন্ত মিল প্রমাণ নয়; প্রমাণের কৌশল অংশ ৭-এ।
একটি সত্যিকারের library দিয়ে যাচাই। নিজের লেখা simulator-এ ভুল থাকতে পারে, তাই একই যন্ত্র একটি স্বাধীন library-তে চালানো হলো। automata-lib একটি Python library (MIT licence), যাতে DFA, NFA, PDA আর Turing machine-এর class আছে; এর NPDA class HMU রীতি মানে: stack শুরুতে initial_stack_symbol (এখানে Z) নিয়ে থাকে, আর প্রতিটি move ঠিক একটি চিহ্ন তোলে। তাই P1-এর $ এখানে Z-এর ভূমিকা নেয়। Library-টিতে কোনো network বা usage-reporting কোড নেই। ডেস্কটপে uv দিয়ে বানানো একটি ছোট প্রকল্পে script-টির মূল অংশ:
from automata.pda.npda import NPDA
anbn = NPDA(
states={"q1", "q2", "q3", "q4"}, input_symbols={"a", "b"},
stack_symbols={"Z", "a"}, initial_state="q1",
initial_stack_symbol="Z", final_states={"q4"},
acceptance_mode="final_state",
transitions={ # {state: {read: {pop: {(next, push)}}}}
"q1": {"": {"Z": {("q2", ("Z",))}}},
"q2": {"a": {"Z": {("q2", ("a", "Z"))}, "a": {("q2", ("a", "a"))}},
"b": {"a": {("q3", "")}},
"": {"Z": {("q4", ("Z",))}}}, # n = 0
"q3": {"b": {"a": {("q3", "")}}, "": {"Z": {("q4", ("Z",))}}}})
# wwr = NPDA(...) is built the same way: push in q1, guess, pop in q2
for w in ["", "ab", "aaabbb", "aab", "abb", "ba"]:
print(repr(w), anbn.accepts_input(w))
for i, S in enumerate(wwr.read_input_stepwise("abba")):
print(i, sorted((c.state, c.remaining_input, "".join(c.stack.stack))
for c in S))সত্যিকারের run (ডেস্কটপ, automata-lib 9.2.0, Python 3.12.13; গ্রহণের ফল একটি লাইনে গুছিয়ে ছাপা):
~/bazarghar-toc$ uv run python run_npda.py
automata-lib 9.2.0
anbn {'ε': True, 'ab': True, 'aaabbb': True, 'aab': False, 'abb': False, 'ba': False}
wwR {'ε': True, 'abba': True, 'aabbaa': True, 'aba': False, 'abab': False}
anbn: 511 strings checked, 5 accepted, agree: True
wwR: 511 strings checked, 31 accepted, agree: True
…
--- every round for abba on wwR ---
0 [('q1', 'abba', 'Z')]
1 [('q1', 'bba', 'Za'), ('q2', 'abba', 'Z')]
2 [('q1', 'ba', 'Zab'), ('q2', 'bba', 'Za'), ('q3', 'abba', 'Z')]
3 [('q1', 'a', 'Zabb'), ('q2', 'ba', 'Zab')]
4 [('q1', '', 'Zabba'), ('q2', 'a', 'Za'), ('q2', 'a', 'Zabb')]
5 [('q2', '', 'Z'), ('q2', '', 'Zabba')]
6 [('q3', '', 'Z')]
Library-ও দৈর্ঘ্য ৮ পর্যন্ত ৫১১টি string-এ সংজ্ঞার সঙ্গে একমত, আর গৃহীত string-এর সংখ্যা (৫ আর ৩১) আমাদের simulator-এর সঙ্গে মেলে। শেষ অংশে library প্রতিটি “round”-এ সব জীবিত configuration-এর set দেখায়, ঠিক NFA-র “একসঙ্গে অনেক পথ” ছবির মতো। একটি সতর্কতা: library stack লেখে তলা বাঁয়ে, ওপর ডানে ('Zab'-এ ওপরে b), আমাদের রীতির উল্টো। এই wwr যন্ত্রে state তিনটি: q1-এ push, q2-তে pop, q3 গ্রহণ। Round 2-এ ('q3', 'abba', 'Z') হলো “০টির পরে অনুমান” শাখা, যা input বাকি রেখে q3-তে পৌঁছে পরের round-এ মরে যায়। Round 5-এ ('q2', '', 'Zabba') সব push করে দেরিতে অনুমানের শাখা, যা আর এগোয় না। শেষে টিকে থাকে শুধু ('q3', '', 'Z'): input শেষ, accept state, তাই abba গৃহীত।
৬ · PDA নকশার কৌশল — push-তারপর-pop, অনুমান, গোনার চিহ্ন
“এই language-এর জন্য একটি PDA নকশা করুন” বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় খুব পরিচিত প্রশ্ন। প্রথমে ঠিক করুন, stack-এ কী জমবে আর প্রতিটি চিহ্ন কী বোঝায়; state-এর কাজ শুধু “এখন কোন পর্যায়”। তিনটি কৌশল প্রায় সব প্রশ্নে কাজ করে।
১. Push, তারপর pop
প্রথম অংশ জমা, দ্বিতীয় অংশে মেলানো: anbn, সুষম বন্ধনী, wcwR. State-গুলো পর্যায় আলাদা করে, তাই b-এর পরে a এলে পথ আটকে যায়।
২. অনুমান করুন
কোথায় অংশ বদলায় না জানলে ε-move দিয়ে অনুমান: wwR-এর মাঝখান। দুটি শর্তের যেকোনো একটি হলে শুরুতেই অনুমান করুন কোন শাখা।
৩. গোনার চিহ্ন
অনুপাত মেলাতে প্রতি a-তে একাধিক চিহ্ন: anb2n-এ প্রতি a-তে দুটি। “কে বেশি” জানতে চিহ্নের ধরন: EQ-তে stack শুধু বাড়তি a বা বাড়তি b রাখে।
৪. সবসময় $
প্রথম move ε, ε → $; গ্রহণের আগে ε, $ → ε. এতে “সব জমা মিলেছে” পরীক্ষা করা যায়। $ ভুলে যাওয়া AI আর নতুন শিক্ষার্থী দুজনেরই সবচেয়ে সাধারণ ভুল।
সুষম বন্ধনী (BAL). stack alphabet {(, $}. q1 থেকে ε, ε → $ দিয়ে q2; q2-তে দুটি নিজস্ব নিয়ম “(, ε → (” আর “), ( → ε”; আর q2 থেকে ε, $ → ε দিয়ে accept state q3. এখানে push আর pop একই state-এ মেশানো, কারণ বন্ধনী যেকোনো ক্রমে খুলতে-বন্ধ হতে পারে। মূল ধারণা: stack-এর উচ্চতা − ১ = এখন কতগুলো বন্ধনী খোলা আছে। “)” এল অথচ ওপরে $, মানে খোলা বন্ধনী নেই: পথ আটকে যায়। বাজারঘরের order-query-র বন্ধনী-যাচাই ঠিক এই যন্ত্র; token-এর ক্রম (FIND, WHERE, শর্ত) সসীম state দেখে, বন্ধনীর গভীরতা দেখে stack.
সমান a আর b (EQ). a আর b যেকোনো ক্রমে আসতে পারে, তাই “আগে push, পরে pop” চলে না। কৌশল: stack-এ সবসময় শুধু এক ধরনের চিহ্ন থাকে, যা এখন পর্যন্ত বাড়তি। ওপরে $ বা a থাকলে a পড়ে আরেকটি a রাখুন; ওপরে b থাকলে a পড়ে একটি b তুলুন (একটি বাড়তি b বাতিল হলো)। b-এর জন্য উল্টোটা। শেষে ওপরে $ মানে কেউ বাড়তি নেই। এখানে একটি সংক্ষিপ্ত লেখা ব্যবহার হয়েছে: “a, $ → a$” মানে $ তুলে a$ রাখা, অর্থাৎ দুটি চিহ্ন push. সংজ্ঞায় প্রতি move-এ বড়জোর একটি চিহ্ন রাখা যায়, তাই আসলে এটি একটি বাড়তি state দিয়ে দুই move: প্রথমে $ রেখে, তারপর ε-move-এ a. Simulator-এ push হিসেবে একটি string দেওয়া এই সংক্ষেপেরই রূপ। মজার ব্যাপার, EQ-এর এই PDA প্রায় deterministic: একমাত্র পছন্দ আসে ওপরে $ থাকলে, পড়া চালিয়ে যাওয়া অথবা ε, $ → ε দিয়ে q3-তে যাওয়া। q3 থেকে কোনো move নেই, তাই দ্বিতীয় পছন্দটি শুধু input শেষ হলেই কাজে আসে।
গোনার চিহ্ন। {anb2n}-এ প্রতিটি a-তে দুটি চিহ্ন রাখুন (a, ε → aa, সংক্ষেপে), আর প্রতিটি b-তে একটি তুলুন। {aibj : i ≤ j ≤ 2i}-এ nondeterminism আর গোনা একসঙ্গে: প্রতিটি a-তে অনুমান করুন একটি রাখবেন না দুটি (অনুশীলন ৪)।
নিচের JavaScript ব্লক P1 আর BAL-এর প্রতিটি move ছাপে: কোন নিয়ম খাটল, নতুন state, input-এ কোথায় আছি (^ চিহ্ন হলো পড়ার head), আর stack (ওপর বাঁয়ে)। Runner প্রতিবার আগে একটি পড়ার move খোঁজে, না পেলে ε-move. এই দুটি যন্ত্রের জন্য এটি যথেষ্ট, কারণ এদের ε-move শুধু $ বসানো আর $ তোলা; অন্য PDA-তে সব শাখা দেখতে Python simulator ব্যবহার করুন।
// Step-by-step stack trace. A move is [state, read, pop, next, push];
// "" means ε. The runner tries a reading move first, else an ε-move:
// enough for these two machines (their only ε-moves are the $ steps).
const ANBN = { start: "q1", accept: ["q1", "q4"], moves: [
["q1", "", "", "q2", "$"], ["q2", "a", "", "q2", "a"],
["q2", "b", "a", "q3", ""], ["q3", "b", "a", "q3", ""],
["q3", "", "$", "q4", ""]] };
const BAL = { start: "q1", accept: ["q3"], moves: [
["q1", "", "", "q2", "$"], ["q2", "(", "", "q2", "("],
["q2", ")", "(", "q2", ""], ["q2", "", "$", "q3", ""]] };
function trace(P, w) {
let q = P.start, i = 0, stack = []; // stack[0] is the top
console.log(`input ${w || "ε"}`);
for (let step = 1; ; step++) {
const ok = m => m[0] === q && (m[1] === "" || m[1] === w[i]) &&
(m[2] === "" || m[2] === stack[0]);
const m = P.moves.find(m => m[1] !== "" && ok(m)) ||
P.moves.find(m => m[1] === "" && ok(m));
if (!m) break;
if (m[2]) stack.shift(); // pop
if (m[4]) stack.unshift(m[4]); // push
q = m[3]; i += m[1].length;
const tape = w.slice(0, i) + "^" + w.slice(i);
console.log(` ${step}. ${m[1] || "ε"},${m[2] || "ε"}->${m[4] || "ε"} ` +
`${q} ${tape.padEnd(w.length + 1)} [${stack.join(" ")}]`);
}
const acc = i === w.length && P.accept.includes(q);
console.log(acc ? " ACCEPT" : ` REJECT: stuck in ${q}, ${w.length - i} symbol(s) unread`);
}
trace(ANBN, "aabb"); trace(ANBN, "aab"); trace(BAL, "(()())"); trace(BAL, "())(");আসল আউটপুট (ব্রাউজারের JavaScript):
input aabb
1. ε,ε->$ q2 ^aabb [$]
2. a,ε->a q2 a^abb [a $]
3. a,ε->a q2 aa^bb [a a $]
4. b,a->ε q3 aab^b [a $]
5. b,a->ε q3 aabb^ [$]
6. ε,$->ε q4 aabb^ []
ACCEPT
input aab
1. ε,ε->$ q2 ^aab [$]
2. a,ε->a q2 a^ab [a $]
3. a,ε->a q2 aa^b [a a $]
4. b,a->ε q3 aab^ [a $]
REJECT: stuck in q3, 0 symbol(s) unread
input (()())
1. ε,ε->$ q2 ^(()()) [$]
2. (,ε->( q2 (^()()) [( $]
3. (,ε->( q2 ((^)()) [( ( $]
4. ),(->ε q2 (()^()) [( $]
5. (,ε->( q2 (()(^)) [( ( $]
6. ),(->ε q2 (()()^) [( $]
7. ),(->ε q2 (()())^ [$]
8. ε,$->ε q3 (()())^ []
ACCEPT
input ())(
1. ε,ε->$ q2 ^())( [$]
2. (,ε->( q2 (^))( [( $]
3. ),(->ε q2 ()^)( [$]
4. ε,$->ε q3 ()^)( []
REJECT: stuck in q3, 2 symbol(s) unread
aabb-তে ৬টি move, সূত্র 2n + 2-এ n = 2. aab-তে input শেষ হয়েছে, কিন্তু stack-এ একটি a রয়ে গেছে, তাই q4-এ যাওয়ার নিয়মটি খাটেনি আর q3 accept state নয়। (()())-এ stack-এর উচ্চতা ১, ২, ৩, ২, ৩, ২, ১, ০: সর্বোচ্চ গভীরতা ২ (উচ্চতা ৩ থেকে $ বাদ দিয়ে)। ())(-এ তৃতীয় চিহ্ন “)” পড়ার সময় ওপরে $, অর্থাৎ বন্ধ করার মতো খোলা বন্ধনী নেই। Runner তখন ε-move-এ q3-তে যায়, যেখানে দুটি চিহ্ন বাকি থাকতে আটকে যায়। এই ব্লকে trace(BAL, "((())") বা বাজারঘরের query-র মতো লম্বা বন্ধনী দিয়ে চালিয়ে দেখুন।
৭ · PDA সঠিক, তার প্রমাণ — stack-এর invariant
Brute force দৈর্ঘ্য ৮ পর্যন্ত দেখে; language অসীম। L(P) = L প্রমাণ মানে দুটি set-এর সমতা, তাই দুটি দিক: P যা গ্রহণ করে তা L-এ আছে (⊆), আর L-এর প্রতিটি string-এর একটি গ্রহণযোগ্য computation আছে (⊇)। ⊆ দিকের মূল হাতিয়ার invariant: প্রতিটি state-এর জন্য একটি দাবি, “এই state-এ পৌঁছালে এ পর্যন্ত পড়া input আর stack-এর মধ্যে এই সম্পর্ক থাকে”। দাবিটি শুরুতে সত্য আর প্রতিটি transition তা রক্ষা করে, এটি move-সংখ্যার ওপর induction দিয়ে দেখানো হয়।
অংশ ২-এর P1-এর জন্য L(P1) = {anbn : n ≥ 0}.
প্রমাণ (⊆ দিক): ধরুন (q1, xy, ε) ⊢∗ (q, y, γ), অর্থাৎ x পড়া হয়েছে আর γ এখনকার stack.
- দাবি I(q): q = q1 হলে x = ε আর γ = ε; q = q2 হলে x = ak আর γ = ak$, কোনো k ≥ 0-এর জন্য; q = q3 হলে x = akbj আর γ = ak−j$, যেখানে 1 ≤ j ≤ k; q = q4 হলে x = akbk আর γ = ε, কোনো k ≥ 1-এর জন্য। — প্রতিটি state-এর invariant
- ভিত্তি: শূন্য move-এ configuration (q1, xy, ε), x = ε, γ = ε. — ⊢∗-এর সংজ্ঞা
- ধাপ, ε, ε → $ (q1 → q2): q1-এ x = ε, γ = ε; পরে x = a0, γ = $ = a0$. — q2-এর দাবি, k = 0
- ধাপ, a, ε → a (q2 → q2): x = ak থেকে ak+1, γ = ak$ থেকে ak+1$. — q2-এর দাবি, k + 1
- ধাপ, b, a → ε (q2 → q3): ওপরে a থাকতে হবে, তাই k ≥ 1; x = akb, γ = ak−1$. j = 1 ≤ k. — q3-এর দাবি
- ধাপ, b, a → ε (q3 → q3): ওপরে a মানে k − j ≥ 1; x = akbj+1, γ = ak−(j+1)$, আর j + 1 ≤ k. — q3-এর দাবি
- ধাপ, ε, $ → ε (q3 → q4): ওপরে $ মানে ak−j ফাঁকা, অর্থাৎ j = k ≥ 1; x = akbk, γ = ε. q4 থেকে কোনো move নেই। — q4-এর দাবি
- অন্য কোনো transition নেই, তাই প্রতিটি computation-এ দাবি সত্য। গ্রহণ মানে y = ε আর q ∈ F = {q1, q4}: q1 হলে w = x = ε = a0b0, q4 হলে w = akbk. দুই ক্ষেত্রেই w ∈ L. ∎ — move-সংখ্যার ওপর induction-এর উপসংহার
প্রমাণ (⊇ দিক): n = 0 হলে (q1, ε, ε)-এ শূন্য move-এই input শেষ আর q1 ∈ F. n ≥ 1 হলে একটি স্পষ্ট computation লিখে দিন: (q1, anbn, ε) ⊢ (q2, anbn, $) ⊢n (q2, bn, an$) ⊢ (q3, bn−1, an−1$) ⊢n−1 (q3, ε, $) ⊢ (q4, ε, ε). প্রতিটি ধাপ সারণির একটি নিয়ম, মোট 1 + n + 1 + (n − 1) + 1 = 2n + 2টি move. ∎
লক্ষ করুন, ⊆ দিকটি সব computation নিয়ে, কারণ PDA nondeterministic হলে একটি অপ্রত্যাশিত পথ বাড়তি কিছু গ্রহণ করতে পারে। ⊇ দিকে একটি পথ দেখানোই যথেষ্ট। P2 (wwR)-এর জন্য একই ছক খাটে। q2-তে invariant: পড়া অংশ x হলে stack = xR$. q3-তে: পড়া অংশ uz, যেখানে u হলো অনুমানের আগে পড়া অংশ, আর u = vzR কোনো v-এর জন্য, আর stack = vR$; অর্থাৎ প্রতিটি পড়া চিহ্ন stack থেকে u-এর একটি করে শেষ চিহ্ন মিলিয়ে তুলেছে। q4-এ যেতে ওপরে $ লাগে, মানে v = ε, তাই u = zR আর w = uuR.
1d(x) = #a(x) − #b(x)2invariant: stack = a^d$ বা b^(−d)$3 একই চিহ্ন: push4 উল্টো চিহ্ন: pop5⊆: গ্রহণ ⇒ ওপরে $ ⇒ d = 06⊇: deterministic পথ সবসময় আছে
| পড়া x, d(x) | |
| stack |
- মাপকাঠি। পড়া অংশ x-এর জন্য d(x) = x-এ a-এর সংখ্যা − b-এর সংখ্যা. EQ = {w : d(w) = 0}. শুরুতে d(ε) = 0, stack $ (প্রথম move-এর পরে)।
- Invariant. q2-তে stack = ad$ যদি d ≥ 0, আর b−d$ যদি d < 0. অর্থাৎ stack-এ একই ধরনের চিহ্ন, সংখ্যায় ঠিক |d|. abba-তে ab পড়ার পরে d = 0, stack $.
- একই চিহ্নের ধাপ। d ≥ 0 আর a পড়া হলো: নিয়ম “a, $ → a$” বা “a, a → aa” একটি a যোগ করে, d এক বাড়ে। d < 0 আর b-এর ক্ষেত্রে একইভাবে b যোগ হয়। abba-র প্রথম a: d = +1, stack a$; তারপর b: d = 0, stack $.
- উল্টো চিহ্নের ধাপ। d < 0 মানে ওপরে b; a পড়লে “a, b → ε” একটি b তোলে, d এক বাড়ে, |d| এক কমে। d > 0 আর b পড়লে “b, a → ε”. abb-তে d = −1, stack b$; শেষ a সেটি তুলে d = 0.
- ⊆ দিক। গ্রহণ হয় শুধু q3-তে, আর q3-তে ঢোকার একমাত্র পথ ε, $ → ε, যা ওপরে $ চায়। Invariant অনুযায়ী ওপরে $ মানে |d| = 0. তাই গৃহীত প্রতিটি w-এ a আর b সমান।
- ⊇ দিক। q2-তে যেকোনো ওপরের চিহ্ন আর যেকোনো input চিহ্নের জন্য ঠিক একটি পড়ার নিয়ম আছে, তাই পুরো w পড়া যায়। d(w) = 0 হলে শেষে stack $, ε, $ → ε দিয়ে q3: গৃহীত। ∎ abba-র ক্ষেত্রে মোট ৬টি move.
সাধারণ ফাঁদ: কয়েকটি string-এর গ্রহণযোগ্য trace দেখিয়ে থেমে যাওয়া। এটি শুধু ⊇-এর কিছু উদাহরণ। nondeterministic PDA-র একটি ভুলে-যাওয়া ε-move হয়তো এমন পথ খোলে, যা বাড়তি string গ্রহণ করে; ⊆ দিক সেটি ধরে। আবার invariant লিখে শুধু “শুরুতে সত্য” দেখালেই হয় না, প্রতিটি transition-এর জন্য রক্ষা দেখাতে হয়।
৮ · PDA বনাম DFA বনাম Turing machine
তিনটি যন্ত্রের পার্থক্য আসলে স্মৃতির পার্থক্য। DFA-র স্মৃতি শুধু state. PDA-র বাড়তি স্মৃতি সীমাহীন, কিন্তু শুধু ওপর থেকে ব্যবহারযোগ্য। Turing machine-এর tape-ও সীমাহীন, আর head যেকোনো দিকে গিয়ে যেকোনো ঘর পড়তে ও লিখতে পারে (পর্ব ৪৩)।
| বিষয় | DFA / NFA | PDA | Turing machine |
|---|---|---|---|
| বাড়তি স্মৃতি | নেই | একটি stack | অসীম tape |
| স্মৃতি ব্যবহার | — | শুধু ওপরের চিহ্ন | যেকোনো ঘর, দুই দিকে |
| Input পড়া | বাঁ থেকে ডানে একবার | বাঁ থেকে ডানে একবার | যতবার ইচ্ছা, লিখতেও পারে |
| Nondeterminism ক্ষমতা বাড়ায়? | না (subset construction) | হ্যাঁ (DPDA দুর্বল) | না (deterministic simulation, পর্ব ৪৬) |
| চেনে | regular language | context-free language | Turing-recognizable language |
| উদাহরণ যা পারে না | anbn | anbncn, ww | halting problem-এর decider |
| Membership (w ∈ L?) | decidable, রৈখিক সময় | decidable (CYK, পর্ব ৩১) | সাধারণভাবে undecidable |
| দুটি যন্ত্রের সমতা | decidable (পর্ব ২০) | undecidable (পর্ব ৩৭) | undecidable |
তিনটি সম্পর্ক সংক্ষেপে প্রমাণ করা যায়। (১) প্রতিটি regular language একটি PDA গ্রহণ করে: একটি DFA নিন আর প্রতিটি δ(q, a) = r-কে “a, ε → ε” transition বানান; stack কখনো ছোঁয়া হয় না, তাই PDA-টি DFA-র মতোই চলে। anbn PDA-তে চেনা যায় কিন্তু regular নয়, তাই অন্তর্ভুক্তিটি কঠোর। (২) PDA-র ক্ষমতা সীমিত: anbncn-এ a গুনতে stack ভরে, b-এর সঙ্গে মেলাতে খালি করে, c-এর জন্য আর কিছু থাকে না। এই অনুভূতির কঠোর প্রমাণ পর্ব ৩৬-এর CFL pumping lemma. (৩) দুটি stack-এ ক্ষমতা লাফিয়ে বাড়ে: একটি দুই-stack PDA একটি Turing machine-এর tape অনুকরণ করে।
প্রমাণের রূপরেখা (দুই stack ⇒ Turing machine-এর ক্ষমতা): TM-এর tape-কে head-এর জায়গায় দুই ভাগ করুন। Head-এর বাঁ দিকের অংশ stack L-এ (head-এর ঠিক বাঁয়ের ঘর ওপরে), head-এর ঘর আর ডান দিকের অংশ stack R-এ (head-এর ঘর ওপরে)। শুরুতে পুরো input R-এ ঢোকানো হয়। Head ডানে সরলে R থেকে pop করে L-এ push; বাঁয়ে সরলে L থেকে pop করে R-এ push. Head-এর ঘরে লেখা মানে R-এর ওপরের চিহ্ন বদলানো। R ফাঁকা হলে একটি blank ␣ push করুন, কারণ tape ডানে অসীম। প্রতিটি TM ধাপ সসীম কয়েকটি stack-move, তাই দুই-stack যন্ত্র TM-এর প্রতিটি computation অনুকরণ করে; উল্টো দিকে একটি TM সহজেই দুটি stack রাখতে পারে। ∎ ফলে ক্রমটি দাঁড়ায়: সসীম স্মৃতি < একটি stack < দুটি stack = Turing machine.
আরও গভীরে: Stack-এর ওপর বিধিনিষেধ দিলে মাঝামাঝি শ্রেণি তৈরি হয়। Stack-এ শুধু একটি চিহ্ন (আর তলার চিহ্ন) থাকলে তা একটি counter; এমন one-counter automaton anbn আর এক রকম বন্ধনী চেনে, কিন্তু দুই রকম বন্ধনীর সুষম ভাষা চেনে না বলে জানা আছে। বিপরীতে Marvin Minsky ১৯৬০-এর দশকে দেখান যে দুটি counter-ই যেকোনো Turing machine অনুকরণে যথেষ্ট (ধীর হলেও)। আরেক দিকে, visibly pushdown language-এ input চিহ্ন নিজেই বলে দেয় push না pop (যেমন XML-এর খোলা আর বন্ধ tag); Alur আর Madhusudan ২০০৪ সালে দেখান, এই শ্রেণি complement আর intersection-এ বদ্ধ, যা সাধারণ CFL নয়, তাই program verification-এ এটি জনপ্রিয়।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- PDA-র formal definition দিন। P = (Q, Σ, Γ, δ, q0, F), δ: Q × Σε × Γε → P(Q × Γε); গ্রহণ: (q0, w, ε) ⊢∗ (f, ε, γ), f ∈ F.
- anbn-এর PDA আঁকুন আর aabb-এর configuration-ক্রম লিখুন। ε, ε → $; a, ε → a; b, a → ε; ε, $ → ε; ৬টি move.
- wwR-এর PDA কেন nondeterministic? মাঝখান কোথায় তা input-এর শেষ না দেখে জানা যায় না; ε-move দিয়ে অনুমান করতে হয়।
- DFA আর PDA-র ক্ষমতার পার্থক্য কী? PDA-তে stack আছে; regular ⊊ CFL, উদাহরণ anbn.
- দুই stack-এর PDA কতটা শক্তিশালী? Turing machine-এর সমান: দুই stack মিলে head-এর দুই পাশের tape.
৯ · AI-এর যুগে PDA নকশা
AI assistant-কে “anbn-এর PDA দাও” বললে দ্রুত একটি পরিচ্ছন্ন transition-তালিকা আসে। দেখতে ঠিক লাগলেও এতে প্রায়ই একটি বা দুটি গোপন ভুল থাকে: তলার চিহ্ন $ নেই বলে শেষে stack-এ জিনিস রয়ে গেলেও গ্রহণ, ε-এর জন্য start state-কে accept বানিয়ে ফেলা যাতে শুধু a-ও গৃহীত হয়, বা “সমান a আর b”-এ শুধু a আগে আসার ক্ষেত্র ধরা। নিচের ব্লকে দুটি এমন খসড়া (AI-এর উত্তরের ধাঁচে বানানো উদাহরণ) দৈর্ঘ্য ৮ পর্যন্ত সংজ্ঞার সঙ্গে মেলানো হয়েছে; ব্লকটি নিজের ছোট simulator নিয়ে স্বয়ংসম্পূর্ণ।
from itertools import product
def accepts(P, w): # DFS over (state, rest, stack)
seen, todo = set(), [(P["q0"], w, "")]
while todo:
q, rest, st = c = todo.pop()
if c in seen or len(st) > 2 * len(w) + 2: continue
seen.add(c)
if rest == "" and q in P["F"]: return True
for (p, a, x), moves in P["d"].items():
if p == q and rest.startswith(a) and st.startswith(x):
todo += [(r, rest[len(a):], y + st[len(x):]) for r, y in moves]
return False
def compare(name, P, inL, n=8):
words = ["".join(t) for k in range(n + 1) for t in product("ab", repeat=k)]
key = lambda w: (len(w), w)
extra = sorted((w for w in words if accepts(P, w) and not inL(w)), key=key)
missing = sorted((w for w in words if inL(w) and not accepts(P, w)), key=key)
print(f"{name}: extra {len(extra)} {extra[:4]} missing {len(missing)} {missing[:4]}")
anbn = lambda w: w == "a" * (len(w) // 2) + "b" * (len(w) // 2)
# AI draft 1 for a^n b^n: no bottom marker, "accept in q2 after the b's"
ai1 = {"q0": "q1", "F": {"q1", "q2"}, "d": {
("q1", "a", ""): [("q1", "a")], ("q1", "b", "a"): [("q2", "")],
("q2", "b", "a"): [("q2", "")]}}
# AI draft 2 for "equal a's and b's": push on a, pop on b, nothing else
ai2 = {"q0": "q1", "F": {"q3"}, "d": {
("q1", "", ""): [("q2", "$")],
("q2", "a", ""): [("q2", "a")], ("q2", "b", "a"): [("q2", "")],
("q2", "", "$"): [("q3", "")]}}
compare("AI draft 1 (a^n b^n)", ai1, anbn)
compare("AI draft 2 (#a = #b)", ai2, lambda w: w.count("a") == w.count("b"))
fix = {"q0": "q0", "F": {"q0", "q3"}, "d": {**ai1["d"], # add $ and a check
("q0", "", ""): [("q1", "$")], ("q2", "", "$"): [("q3", "")]}}
compare("fixed draft 1 with $ ", fix, anbn)আসল আউটপুট (ব্রাউজারের Python):
AI draft 1 (a^n b^n): extra 20 ['a', 'aa', 'aaa', 'aab'] missing 0 []
AI draft 2 (#a = #b): extra 0 [] missing 76 ['ba', 'abba', 'baab', 'baba']
fixed draft 1 with $ : extra 0 [] missing 0 []
প্রথম খসড়া কোনো anbn বাদ দেয় না, কিন্তু ২০টি বাড়তি string নেয়। দুটি ভুল একসঙ্গে: q1-কে ε-এর জন্য accept বানানো হয়েছে, অথচ q1-এ a-ও জমা হয়, তাই a, aa, … (৮টি) গৃহীত; আর q2-তে গ্রহণের সময় stack-এ a বাকি থাকলেও কেউ দেখে না, তাই aab-এর মতো b কম এমন ১২টি string-ও (j < i). দ্বিতীয় খসড়া কোনো বাড়তি নেয় না, কিন্তু ৯৯টির মধ্যে ৭৬টি বাদ দেয়: ওপরে $ থাকা অবস্থায় b পড়ার নিয়ম নেই, তাই যে string-এর কোনো prefix-এ b বেশি, সেটিই আটকে যায়। যা টিকে থাকে তা ঠিক সুষম বন্ধনীর ধাঁচের ২৩টি string (99 − 76 = 23). তৃতীয় লাইনে প্রথম খসড়া সারানো: নতুন start state q0 (ε-এর জন্য accept), প্রথম move-এ $, আর $ দেখেই কেবল accept state q3-তে যাওয়া। এটি অংশ ২-এর P1-এর মতোই।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| তলার চিহ্ন নেই: stack-এ জিনিস রয়ে গেলেও গ্রহণ (aab), বা stack খালি কি না পরীক্ষাই নেই | দৈর্ঘ্য ৮ পর্যন্ত extra আর missing দুটি তালিকা ছাপুন; extra-তে “একটি চিহ্ন বেশি” string খুঁজুন |
| ε বা প্রান্তের ক্ষেত্র ভুল: ε বাদ, বা ε-এর জন্য বানানো accept state থেকে আরও কিছু গৃহীত | ε, দৈর্ঘ্য ১ আর শুধু এক ধরনের চিহ্নের string হাতে trace করুন |
| এক দিকের ক্ষেত্র ভুলে যাওয়া (EQ-তে শুধু a আগে) | ba, abba-র মতো “উল্টো দিক থেকে শুরু” string পরীক্ষা করুন |
| wwR-এর জন্য “deterministic PDA” দাবি, বা nondeterministic PDA-কে DFA-র মতো subset construction-এ deterministic বানানোর দাবি | মনে রাখুন DPDA wwR চেনে না (পর্ব ৩৫); দাবির উৎস চান |
| “PDA anbncn চেনে” বা “দুটি PDA-র সমতা যাচাই করা যায়” | প্রথমটি মিথ্যা (পর্ব ৩৬), দ্বিতীয়টি undecidable (পর্ব ৩৭); Sipser বা HMU-তে মিলিয়ে নিন |
| সঠিকতার “প্রমাণ” মানে শুধু একটি গ্রহণযোগ্য trace | প্রতিটি state-এর invariant আর প্রতিটি transition-এর রক্ষা আছে কি না দেখুন |
AI-কে কাজে লাগানোর ভালো উপায়: PDA-র সঙ্গে প্রতিটি state-এর invariant, ছোট input-এর trace আর একটি brute-force কোড চাওয়া, যা আপনি নিজে চালাবেন।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Stack-এর ধারণা কোথা থেকে এল, আর একটি প্রকৌশলের কৌশল কীভাবে গণনার তত্ত্বের একটি যন্ত্র হয়ে উঠল?
Stack-এর ধারণা গণিতের বইয়ের আগে প্রকৌশলের কাজে দেখা দেয়। প্রায়ই বলা হয়, Alan Turing ১৯৪৬ সালের ACE কম্পিউটারের নকশা-প্রতিবেদনে subroutine থেকে ফেরার ঠিকানা রাখার জন্য “bury” আর “unbury” নামের দুটি কাজের কথা লেখেন, যা আজকের push আর pop-এর মতো। ১৯৫০-এর দশকের শেষে জার্মানির Friedrich L. Bauer আর Klaus Samelson গাণিতিক সূত্র অনুবাদের জন্য “Kellerprinzip” (ভাঁড়ার-নীতি) নামে একটি পদ্ধতি দেন, আর এর জন্য একটি patent-এর আবেদনও করেন বলে উল্লেখ পাওয়া যায়। সূত্রের বন্ধনী আর operator-এর ক্রম সামলাতে “শেষে রাখা জিনিস আগে বের” নীতিটি স্বাভাবিকভাবেই আসে, কারণ নেস্ট করা গঠনে সবচেয়ে ভেতরের অংশ আগে শেষ হয়।
তাত্ত্বিক যন্ত্র হিসেবে pushdown store-এর ধারণা ১৯৬০-এর দশকের শুরুতে স্পষ্ট হয়। Anthony Oettinger ১৯৬১ সালের একটি প্রবন্ধে বাক্য-গঠন বিশ্লেষণের (syntactic analysis) জন্য pushdown store-কে আলোচনা করেন বলে পরিচিত। তারপর ১৯৬২–৬৩ সালের দিকে Noam Chomsky, Marcel-Paul Schützenberger আর R. J. Evey আলাদাভাবে দেখান যে context-free grammar আর pushdown যন্ত্র ঠিক একই language-শ্রেণি বর্ণনা করে। ঠিক কে কবে প্রথম, তা নিয়ে উৎসভেদে বর্ণনা একটু আলাদা; Hopcroft–Motwani–Ullman-এর অধ্যায়-শেষের টীকায় এই ইতিহাসের সংক্ষিপ্ত রূপ আছে।
এই মিলন গুরুত্বপূর্ণ ছিল দুই কারণে। Compiler লেখকেরা পেলেন একটি গাণিতিক নিশ্চয়তা: grammar থেকে একটি stack-ভিত্তিক parser বানানো সবসময় সম্ভব (পর্ব ৩৪)। আর তাত্ত্বিকেরা পেলেন Chomsky hierarchy-র Type 2 স্তরের একটি যন্ত্র-রূপ, যা DFA আর Turing machine-এর মাঝখানে বসে। আজ প্রতিটি programming language-এর call stack, browser-এর HTML parser আর calculator-এর expression মূল্যায়নে একই নীতি কাজ করে।
মূল উপলব্ধি: Stack কোনো কৃত্রিম গাণিতিক কৌশল নয়; নেস্ট করা গঠন সামলানোর প্রয়োজন থেকে প্রকৌশলীরা এটি আবিষ্কার করেছিলেন, আর তত্ত্ব পরে দেখাল যে নেস্টিং-এর জন্য ঠিক এটুকু স্মৃতিই লাগে, এর বেশিও নয়, কমও নয়।
প্র ০২NFA আর DFA-র ক্ষমতা সমান, অথচ nondeterministic PDA deterministic PDA-র চেয়ে শক্তিশালী। এই অসমতা কেন, আর বাস্তবে এর দাম কী?
NFA-র ক্ষেত্রে subset construction কাজ করে, কারণ যেকোনো মুহূর্তে NFA-র “সব সম্ভাব্য অবস্থা” Q-এর একটি subset, আর Q সসীম বলে subset-এর সংখ্যাও সসীম (বড়জোর 2|Q|)। তাই একটি DFA সব subset-কে নিজের state বানিয়ে NFA-কে একসঙ্গে সব পথে অনুকরণ করতে পারে। PDA-তে এক মুহূর্তের অবস্থা হলো state আর stack-এর জোড়, আর আলাদা আলাদা পথে stack আলাদা হতে পারে। abba-র ক্ষেত্রে অংশ ৪-এ একসঙ্গে a$, ba$, bba$-এর মতো ভিন্ন stack দেখেছেন। একটি মাত্র stack দিয়ে এই সব stack একসঙ্গে রাখার উপায় নেই, কারণ প্রতিটি পথ নিজের stack-এর ওপরটা দেখতে চায়।
ফলটি শুধু কৌশলের ব্যর্থতা নয়, একটি সত্যিকারের সীমা: deterministic CFL-এর শ্রেণি (DCFL) context-free language-এর একটি কঠোর অংশ, আর wwR তার বাইরে। স্বজ্ঞাটি হলো, deterministic যন্ত্র মাঝখান অনুমান করতে পারে না, আর “এখন পর্যন্ত পড়া অংশ নিজেই কি একটি palindrome-এর প্রথম অর্ধেক?” প্রশ্নের উত্তর না জেনে সে stack মুছে ফেললে পরে ভুল প্রমাণ হলে তা আর ফিরিয়ে আনতে পারে না। কঠোর প্রমাণে আরও যত্ন লাগে; পর্ব ৩৫-এ উৎসসহ আসবে। আরেকটি পার্থক্য: DCFL complement-এ বদ্ধ, কিন্তু সাধারণ CFL নয়।
বাস্তবে এর দাম গুরুতর। Programming language-এর parser প্রতিটি input-এ দ্রুত, রৈখিক সময়ে চলতে চায়, তাই প্রায় সব প্রচলিত parser deterministic: LL আর LR পরিবার (পর্ব ৩৮–৩৯)। Donald Knuth ১৯৬৫ সালে LR(k) parsing-এর প্রবন্ধে দেখান যে LR(k) grammar-গুলো ঠিক deterministic CFL-গুলোই বর্ণনা করে, এমন বর্ণনাই প্রচলিত। তাই language-নকশাকারীরা syntax এমনভাবে বানান যাতে কোনো “মাঝখান অনুমান” লাগে না: খোলা আর বন্ধ চিহ্ন আলাদা, keyword দিয়ে অংশ চিহ্নিত। যেখানে সাধারণ CFG লাগে, সেখানে Earley বা GLR (পর্ব ৪১) সব পথ একসঙ্গে চালায়, কিন্তু সবচেয়ে খারাপ ক্ষেত্রে ঘন সময় লাগে।
মূল উপলব্ধি: সসীম স্মৃতিতে nondeterminism বিনা খরচে মুছে ফেলা যায়, কিন্তু সীমাহীন অথচ সীমিত-প্রবেশের স্মৃতিতে যায় না; এই কারণেই parser-এর জগতে grammar-কে deterministic রাখার এত চেষ্টা।
প্র ০৩একটি stack-এর বদলে একটি counter, একটি queue বা দুটি stack দিলে যন্ত্রের ক্ষমতা কীভাবে বদলায়?
সবচেয়ে দুর্বল সংযোজন হলো একটি counter: একটি অঋণাত্মক সংখ্যা, যা বাড়ানো, কমানো আর শূন্য কি না দেখা যায়। এটি আসলে এমন একটি stack, যার alphabet-এ তলার চিহ্ন ছাড়া একটিই চিহ্ন। এমন one-counter automaton anbn চেনে, এক রকম বন্ধনীর সুষম ভাষাও চেনে, কারণ সেখানে শুধু “কতগুলো খোলা” জানলেই চলে। কিন্তু দুই রকম বন্ধনী, যেমন “( [ ] )” বৈধ আর “( [ ) ]” অবৈধ, চিনতে শুধু সংখ্যা যথেষ্ট নয়, খোলাগুলোর ক্রম মনে রাখতে হয়; one-counter ভাষার শ্রেণি এটি ধরে না বলে জানা আছে। তাই counter < stack.
উল্টো দিকে বড় লাফ। অংশ ৮-এ দেখেছেন, দুটি stack মিলে একটি Turing machine-এর tape: head-এর বাঁয়ের অংশ এক stack-এ, ডানের অংশ অন্যটিতে। একটি queue (প্রথমে ঢোকা জিনিস প্রথমে বের) দিলেও Turing machine-এর ক্ষমতা আসে, কারণ queue-এর শেষে লিখে সামনে থেকে পড়লে পুরো tape-টি বারবার ঘুরিয়ে যেকোনো ঘরে পৌঁছানো যায়। আরও অবাক করা ফল: Marvin Minsky ১৯৬০-এর দশকে দেখান, দুটি counter-ই যথেষ্ট; একটি সংখ্যার মধ্যে 2i3j-এর মতো সংকেতে পুরো stack লুকিয়ে রাখা যায়, যদিও অনুকরণ খুব ধীর। তাই দুই-counter যন্ত্রের halting প্রশ্নও undecidable.
এই সিঁড়ি থেকে একটি গভীর শিক্ষা আসে: ক্ষমতা নির্ভর করে স্মৃতির পরিমাণের চেয়ে বেশি স্মৃতিতে প্রবেশের নিয়মের ওপর। একটি stack-এ অসীম জায়গা, তবু শুধু ওপর থেকে প্রবেশের কারণে এটি anbncn পারে না। দুটি stack-এ একই অসীম জায়গা, কিন্তু একটি থেকে অন্যটিতে জিনিস সরিয়ে যেকোনো জায়গায় পৌঁছানো যায়, তাই সব গণনাযোগ্য সমস্যা ধরা দেয়। বাস্তবের সফটওয়্যারে এর প্রতিফলন: শুধু recursion (একটি call stack) দিয়ে নেস্ট করা গঠন সামলানো যায়, কিন্তু একটি সাধারণ heap বা array পেলেই program সব কিছু গণনা করতে পারে।
মূল উপলব্ধি: সসীম স্মৃতি < একটি counter < একটি stack < দুটি stack = একটি queue = দুটি counter = Turing machine; সিঁড়ির প্রতিটি ধাপ ঠিক করে স্মৃতিতে কীভাবে পৌঁছানো যায়, কতটা আছে তা নয়।
প্র ০৪বাস্তবের কম্পিউটারের স্মৃতি সসীম, তাহলে আসলে সব যন্ত্রই finite automaton. তবু PDA মডেলটি কেন কাজের, আর parser-এ nesting-এর সীমা কেন রাখা হয়?
কথাটি আক্ষরিকভাবে সত্য: একটি কম্পিউটারের RAM আর disk মিলে সসীম সংখ্যক bit, তাই সম্ভাব্য অবস্থার সংখ্যাও সসীম, আর তত্ত্বের দিক থেকে এটি একটি বিশাল DFA. কিন্তু সেই DFA-র state সংখ্যা 2-এর ঘাত কয়েক শত কোটি, যা কোনো বিশ্লেষণে কাজে আসে না। মডেলের কাজ হলো সঠিক বিমূর্ততা দেওয়া: “stack যত দরকার তত বড়” ধরে নিলে আমরা বুঝি, বন্ধনী মেলানোর algorithm-টি কোনো নির্দিষ্ট গভীরতার ওপর নির্ভর করে না। সসীম স্মৃতি তখন একটি প্রকৌশলের সীমা, algorithm-এর নকশার অংশ নয়।
তবু বাস্তবে সেই সীমা গুরুত্বপূর্ণ, বিশেষ করে নিরাপত্তায়। একটি recursive-descent parser প্রতিটি নেস্ট করা বন্ধনীর জন্য একটি function call করে, অর্থাৎ call stack-এ একটি frame. কেউ যদি “[[[[…” দিয়ে লাখো স্তরের একটি JSON পাঠায়, parser-এর call stack উপচে পড়ে program বন্ধ হয়ে যেতে পারে। তাই অনেক JSON আর XML parser-এ সর্বোচ্চ nesting গভীরতার একটি সীমা রাখা হয়, আর গভীরতা পেরোলে input বাতিল করা হয়। বাজারঘরের order-query engine-এ এমন একটি সীমা, যেমন বন্ধনীর গভীরতা ৩২, রাখা বুদ্ধিমানের কাজ। নিজের কোডে এটি পরীক্ষা করুন, কারো সার্ভারে নয়।
তত্ত্বের দিক থেকে এই সীমার একটি সুন্দর অর্থ আছে। গভীরতা সর্বোচ্চ k হলে stack-এর সম্ভাব্য অবস্থা সসীম (বড়জোর |Γ|k-এর মতো), তাই সেই PDA আসলে একটি DFA, যার state হলো (PDA-র state, stack-এর পুরো বিষয়বস্তু)। অর্থাৎ “গভীরতা ≤ k-এর সুষম বন্ধনী” একটি regular language, যদিও তার DFA k-এর সঙ্গে বড় হয়। পর্ব ১৭-এর pumping lemma এর বিরুদ্ধে যায় না, কারণ সেখানে প্রশ্ন ছিল সব গভীরতার সুষম বন্ধনী নিয়ে।
মূল উপলব্ধি: PDA মডেল বলে কোন algorithm নীতিগতভাবে কাজ করে; বাস্তবের সীমা বলে কতটুকু পর্যন্ত তা নিরাপদে চালাবেন। দুটিই দরকার: প্রথমটি নকশার জন্য, দ্বিতীয়টি নিরাপত্তার জন্য।
প্র ০৫দৈর্ঘ্য ১০ পর্যন্ত সব string-এ একটি PDA সংজ্ঞার সঙ্গে মিলে গেলে কি সেটি সঠিক ধরে নেওয়া যায়? কম্পিউটার কি PDA-র সঠিকতা নিজে যাচাই করতে পারে?
না, আর একটি সহজ উদাহরণে কারণটি দেখা যায়। একটি “ফাঁকি দেওয়া” PDA ভাবুন, যা anbn চেনার ভান করে কিন্তু stack-এ ৬টি বা তার বেশি a জমলে একটি বাড়তি b-ও মেনে নেয়। দৈর্ঘ্য ১০ পর্যন্ত (n ≤ 5) এটি নিখুঁত, ভুলটি প্রথম ধরা পড়ে দৈর্ঘ্য ১৩-এ। Brute force তাই একটি জাল: যে ভুল ছোট string-এ দেখা দেয়, সেগুলো ধরে, যা বাস্তবে বেশিরভাগ ভুল। কিন্তু অসীম language সম্পর্কে দাবি প্রমাণ করতে লাগে অংশ ৭-এর মতো invariant-ভিত্তিক যুক্তি।
দ্বিতীয় প্রশ্নের উত্তর মিশ্র। কিছু প্রশ্ন কম্পিউটার নিশ্চিতভাবে পারে: একটি নির্দিষ্ট string w একটি PDA গ্রহণ করে কি না (membership), আর PDA আদৌ কিছু গ্রহণ করে কি না (emptiness), দুটিই decidable; পর্ব ৩৪-এর রূপান্তরে PDA থেকে grammar বানিয়ে পর্ব ৩১-এর CYK আর পর্ব ৩৭-এর emptiness algorithm চালালেই হয়। একটি PDA আর একটি DFA-র language-এর intersection ফাঁকা কি না, তাও decidable, কারণ PDA × DFA আবার একটি PDA (পর্ব ৩৭)। কিন্তু “দুটি PDA কি একই language গ্রহণ করে?” বা “এই PDA কি সব string গ্রহণ করে?” প্রশ্ন সাধারণভাবে undecidable; প্রমাণ আসবে পর্ব ৫৪-এর Post correspondence problem দিয়ে। DFA-র ক্ষেত্রে এগুলো decidable ছিল (পর্ব ২০), তাই এখানেও একটি সিঁড়ির ধাপ পেরিয়ে প্রশ্ন কঠিন হয়ে যায়।
এর অর্থ: “PDA-টি ঠিক এই সংজ্ঞার language গ্রহণ করে” দাবি যাচাইয়ের কোনো সার্বজনীন স্বয়ংক্রিয় যন্ত্র নেই। ব্যবহারিক পথ তিনটির মিশ্রণ: ছোট দৈর্ঘ্যের brute force আর এলোমেলো লম্বা string-এ পরীক্ষা (ভুল ধরার জন্য), invariant-ভিত্তিক প্রমাণ (নিশ্চয়তার জন্য), আর যেখানে সম্ভব যন্ত্রকে deterministic বা আরও সংকীর্ণ শ্রেণিতে রাখা, যেখানে বেশি প্রশ্ন decidable. Deterministic PDA-র সমতা আসলে decidable বলে প্রমাণিত, যদিও প্রমাণটি খুব জটিল; পর্ব ৩৫-এ এর ইতিহাস।
মূল উপলব্ধি: Membership আর emptiness-এর মতো “একটি যন্ত্র নিয়ে” প্রশ্ন decidable, কিন্তু “দুটি যন্ত্র কি একই” প্রশ্ন undecidable; তাই PDA-র সঠিকতার নিশ্চয়তা আসে প্রমাণ থেকে, পরীক্ষা থেকে আসে শুধু আস্থা।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। pda_sim.py ব্লকে নিজের PDA লিখে show দিয়ে, আর pda_bruteforce.py-এর tests তালিকায় যোগ করে উত্তর যাচাইও করতে পারেন।
-
নকশা: L = {aibjck : i = j অথবা j = k}, যেখানে i, j, k ≥ 0. এই language-এর জন্য একটি PDA নকশা করুন আর প্রতিটি state-এর ভূমিকা বলুন। কেন এখানে nondeterminism স্বাভাবিক?
শুরুতেই অনুমান করুন কোন শর্তটি যাচাই হবে। q0 থেকে দুটি ε-move: ε, ε → $ দিয়ে q1 (শাখা ক: i = j) অথবা ε, ε → $ দিয়ে q4 (শাখা খ: j = k).
শাখা ক: q1-এ a, ε → a (a জমা); q1 → q2 ε, ε → ε; q2-তে b, a → ε (b দিয়ে মেলানো); q2 → q3 ε, $ → ε; q3-তে c, ε → ε (c যত ইচ্ছা, stack না ছুঁয়ে)। শাখা খ: q4-এ a, ε → ε (a উপেক্ষা); q4 → q5 ε, ε → ε; q5-এ b, ε → b; q5 → q6 ε, ε → ε; q6-এ c, b → ε; q6 → q7 ε, $ → ε. F = {q3, q7}.
পর্যায়-বদলগুলো ε-move হওয়ায় ক্রম ভাঙা (যেমন b-এর পরে a) কোনো শাখায় পড়া যায় না। Nondeterminism স্বাভাবিক, কারণ কোন শর্ত সত্য তা c পর্যন্ত না পড়ে জানা যায় না। এই language inherently ambiguous বলে পরিচিত (পর্ব ২৭), অর্থাৎ এর প্রতিটি grammar ambiguous; PDA-টির দুই শাখাও abc-এর মতো string-এ (i = j = k) দুটিই গ্রহণ করে। Scratch-এ দৈর্ঘ্য ৭ পর্যন্ত ৩২৮০টি string-এ PDA আর সংজ্ঞা হুবহু মিলেছে (৩৭টি গৃহীত)।
-
প্রমাণ: অংশ ৬-এর BAL-এর PDA (q1 → q2: ε, ε → $; q2: “(, ε → (” আর “), ( → ε”; q2 → q3: ε, $ → ε; F = {q3}) নিন। প্রমাণ করুন, এটি যে string গ্রহণ করে তা সুষম, অর্থাৎ L(P) ⊆ BAL. কোন invariant লাগবে?
Invariant: q2-তে পড়া অংশ x হলে stack = (h(x)$, যেখানে h(x) = x-এ “(”-এর সংখ্যা − “)”-এর সংখ্যা, আর x-এর প্রতিটি prefix-এ h ≥ 0. Move-সংখ্যার ওপর induction:
১. q1 → q2: x = ε, h = 0, stack $. ২. “(, ε → (”: h এক বাড়ে, stack-এ একটি “(” বাড়ে, prefix-শর্ত অটুট। ৩. “), ( → ε”: ওপরে “(” থাকতে হবে, তাই h(x) ≥ 1; পরে h(x)) = h(x) − 1 ≥ 0, stack-এ একটি “(” কমে। ৪. q2 → q3: ওপরে $ মানে h(x) = 0; q3 থেকে কোনো move নেই, তাই গ্রহণের জন্য এখানেই input শেষ হতে হবে।
অতএব গৃহীত w-এর প্রতিটি prefix-এ h ≥ 0 আর h(w) = 0, যা ঠিক সুষম বন্ধনীর সংজ্ঞা (pda_bruteforce.py-এর
balfunction যা পরীক্ষা করে)। ∎ উল্টো দিক (BAL ⊆ L(P)): সুষম w-এ কোনো prefix-এ h ঋণাত্মক হয় না, তাই প্রতিটি “)”-এর সময় ওপরে “(” থাকে, আর শেষে h = 0 মানে ওপরে $: deterministic পথটি গ্রহণে শেষ হয়। -
Trace: একই BAL-এর PDA-তে (()-এর সব সম্ভাব্য computation লিখুন। কোথায় কোথায় পথ ভাগ হয়, আর string-টি গৃহীত কি না?
(q1, ((), ε) ⊢ (q2, ((), $). এখানে দুটি পথ: “(” push, অথবা ε, $ → ε দিয়ে (q3, ((), ε), যা input বাকি রেখে মরে যায়। প্রথম পথে (q2, (), ($) ⊢ (q2, ), (($) ⊢ (q2, ε, ($). এখন input শেষ, কিন্তু ওপরে “(”, তাই ε, $ → ε খাটে না, আর q2 ∉ F. কোনো পথ গ্রহণে শেষ হয় না: (() গৃহীত নয়।
পথ ভাগ হয় শুধু সেই configuration-গুলোতে, যেখানে ওপরে $ আর পরের চিহ্ন “(”: এখানে একবারই, শুরুতে। Invariant-এর ভাষায়: শেষে h = 1 ≠ 0. Scratch-এর simulator-এও (() বাতিল, আর stack_trace.js-এ
trace(BAL, "(()")চালালে “stuck in q2, 0 symbol(s) unread” আসবে। -
নকশা, গোনা আর অনুমান একসঙ্গে: L = {aibj : i ≤ j ≤ 2i}-এর একটি PDA দিন। দৈর্ঘ্য ৫ পর্যন্ত L-এর সব string লিখুন।
প্রতিটি a-তে অনুমান করুন একটি চিহ্ন রাখবেন না দুটি; তাহলে stack-এ মোট t চিহ্ন, যেখানে i ≤ t ≤ 2i. তারপর প্রতিটি b-তে একটি তুলুন, আর শেষে stack-এ শুধু $ থাকতে হবে, অর্থাৎ j = t. q1 → q2: ε, ε → $; q2-তে a, ε → a আর a, ε → aa (দুটি চিহ্ন, বাড়তি state দিয়ে যার আসল রূপ); q2 → q3: ε, ε → ε; q3-তে b, a → ε; q3 → q4: ε, $ → ε; F = {q4}.
⊆: গ্রহণে j = t আর i ≤ t ≤ 2i. ⊇: j দেওয়া থাকলে j − i-টি a-তে দুটি আর বাকি 2i − j-টিতে একটি চিহ্ন বেছে নিন (দুটিই অঋণাত্মক কারণ i ≤ j ≤ 2i). দৈর্ঘ্য ৫ পর্যন্ত: ε, ab, abb, aabb, aabbb. Scratch-এ দৈর্ঘ্য ১০ পর্যন্ত PDA আর সংজ্ঞা মিলেছে (মোট ১৪টি string).
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি language-এর বর্ণনা থেকে PDA নকশা আর যাচাইয়ের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- ছোট উদাহরণ আর পাল্টা-উদাহরণ লেখা, ε আছে কি না ঠিক করা
- stack-এ কী জমবে আর প্রতিটি stack চিহ্ন কী বোঝায়, তা ঠিক করা
- প্রথম move-এ তলার চিহ্ন $ বসানো
- প্রতিটি পর্যায়ের state আর transition লেখা (push, অনুমান, pop)
- ছোট দৈর্ঘ্যের সব string-এ simulator চালিয়ে সংজ্ঞার সঙ্গে মেলানো
- প্রতিটি state-এর stack invariant লিখে L(P) = L প্রমাণ করা
একটি PDA-তে (r, y) ∈ δ(q, a, x), অর্থাৎ transition “a, x → y”. Configuration (state, বাকি input, stack) লেখা হয় stack-এর ওপরের চিহ্ন বাঁয়ে রেখে। β যেকোনো stack-string হলে কোন ধাপটি এই transition দেয়?
- (q, aw, xβ) ⊢ (r, w, yxβ)
- (q, aw, xβ) ⊢ (r, w, yβ)
- (q, aw, xβ) ⊢ (r, aw, yβ)
- (q, aw, βx) ⊢ (r, w, βy)
নিচের কোন language-এর জন্য PDA-তে nondeterminism অপরিহার্য, অর্থাৎ কোনো deterministic PDA এটি চেনে না?
- {anbn : n ≥ 0}
- {wcwR : w ∈ {a, b}∗}
- {wwR : w ∈ {a, b}∗}
- সুষম বন্ধনীর language
Sipser রীতির PDA-তে (শুরুতে stack ফাঁকা, কোনো start stack symbol নেই) প্রথম move-এ সাধারণত ε, ε → $ দিয়ে একটি বিশেষ চিহ্ন $ push করা হয়। এর মূল কারণ কী?
- PDA সরাসরি stack ফাঁকা কি না পরীক্ষা করতে পারে না, $ দেখে তা বোঝা যায়
- $ input-এর শেষ চিহ্নিত করে
- $ ছাড়া PDA nondeterministic হতে পারে না
- গ্রহণের জন্য শেষে stack-এ ঠিক $ থাকতে হয়
নিচের কোন language কোনো pushdown automaton চেনে না?
- {wwR : w ∈ {a, b}∗}
- {anb2n : n ≥ 0}
- a আর b সমান সংখ্যক এমন সব string
- {anbncn : n ≥ 0}
PDA P-এর state q1 (start, accept), q2, q3, q4 (accept); transition: q1 → q2 “ε, ε → $”, q2 → q2 “a, ε → a”, q2 → q3 “b, a → ε”, q3 → q3 “b, a → ε”, q3 → q4 “ε, $ → ε”. Input aabb গ্রহণ করতে মোট কয়টি move লাগে?
- ৪
- ৫
- ৬
- ৮
একটি finite-state নিয়ন্ত্রণের সঙ্গে একটির বদলে দুটি সীমাহীন stack দিলে যন্ত্রটি কোন শ্রেণির language চিনতে পারে?
- ঠিক context-free language
- ঠিক Turing-recognizable language
- ঠিক regular language
- ঠিক decidable language, এর বেশি নয়
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- PDA = finite-state নিয়ন্ত্রণ + একটি সীমাহীন stack: P = (Q, Σ, Γ, δ, q0, F), δ: Q × Σε × Γε → P(Q × Γε); “a, x → y” মানে a পড়ে x তুলে y রাখা।
- Configuration (q, w, γ), ওপর বাঁয়ে; w ∈ L(P) মানে (q0, w, ε) ⊢∗ (f, ε, γ) কোনো f ∈ F-এর জন্য, অন্তত একটি পথে।
- প্রথম move-এ $ push করুন, কারণ PDA সরাসরি “stack ফাঁকা” দেখতে পারে না।
- নকশা: push-তারপর-pop (anbn, BAL), মাঝখান অনুমান (wwR), গোনার চিহ্ন (EQ, anb2n); সঠিকতা: প্রতিটি state-এর stack invariant, দুই দিকের inclusion.
- Regular ⊊ PDA-র language; nondeterminism PDA-র ক্ষমতা বাড়ায় (wwR); anbncn PDA-র বাইরে; দুটি stack = Turing machine.
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ২৫ · Context-free grammar — formal definition আর উদাহরণফিরে দেখুনএকই language-গুলোর grammar: anbn, BAL, palindrome আর সমান a ও b.
- পর্ব ০৯ · NFA — nondeterminism, একসঙ্গে অনেক পথ আর গ্রহণের নিয়মপটভূমি“অন্তত একটি পথ” আর guess and verify, যা এখানে stack-সহ ফিরে এসেছে।
- পর্ব ১৭ · Regular language-এর pumping lemma — non-regular প্রমাণপটভূমিanbn কেন কোনো DFA চেনে না, যার উত্তর stack.
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ৩৩ PDA-র গ্রহণের রীতি।
- DSA · পর্ব ১৩ — Stackপাশের ট্র্যাকData structure হিসেবে stack, push, pop আর বন্ধনী মেলানোর কোড।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৪ — Finite automataপাশের ট্র্যাকAutomaton-এর প্রথম পরিচয়, গণিতের দিক থেকে।