Compiler & Theory of ComputationCompiler & Theory of Computation

From simple machines (DFA) to Turing machines, and how a compiler turns your code into something a computer runs. সহজ machine (DFA) থেকে Turing machine পর্যন্ত, আর compiler কীভাবে আপনার code-কে computer-এর চালানোর মতো জিনিসে বদলায়।

In this chapterএই chapter-এ যা আছে

Regular Languages and Regular ExpressionsRegular Languages আর Regular Expressions
DFA and NFADFA আর NFA
CFG and PDACFG আর PDA
Turing Machines and DecidabilityTuring Machine আর Decidability
Lexical Analysis and ParsingLexical Analysis আর Parsing
Syntax and Semantic AnalysisSyntax আর Semantic Analysis
Practice Questions (Admission Style)Practice Questions (Admission Style)

1. Regular Languages and Regular Expressions1. Regular Languages আর Regular Expressions

Basic words: alphabet, string, languageমূল শব্দ: alphabet, string, language

Theory of Computation starts with three simple words:

Alphabet ($\Sigma$): a finite set of symbols. Example: $\Sigma = \{0, 1\}$ or $\Sigma = \{a, b\}$.
String: a finite sequence of symbols from the alphabet. Example: 0110. The empty string is written $\varepsilon$ (epsilon). Its length is 0.
Language: a set of strings. Example: $L = \{\text{all binary strings that end in } 01\}$. So 101 is in $L$, but 110 is not.

Some useful notation: $\Sigma^*$ means "all possible strings over $\Sigma$", including $\varepsilon$. $|w|$ means the length of string $w$.

Theory of Computation শুরু হয় তিনটা সহজ শব্দ দিয়ে:

Alphabet ($\Sigma$): symbol-এর একটা finite set। যেমন: $\Sigma = \{0, 1\}$ বা $\Sigma = \{a, b\}$।
String: alphabet-এর symbol দিয়ে বানানো একটা finite sequence। যেমন: 0110। খালি string-কে লেখা হয় $\varepsilon$ (epsilon)। এর length 0।
Language: string-এর একটা set। যেমন: $L = \{01 \text{ দিয়ে শেষ হওয়া সব binary string}\}$। তাই 101 এই $L$-এ আছে, কিন্তু 110 নেই।

দরকারি notation: $\Sigma^*$ মানে "$\Sigma$-এর উপর সব সম্ভব string", $\varepsilon$ সহ। $|w|$ মানে string $w$-এর length।

Regular expressions: the three operatorsRegular expression: তিনটা operator

A regular expression (regex) is a short formula that describes a language. It uses only three operations:

Union (+): $a + b$ means "either a or b". Some books write $a \mid b$.
Concatenation: $ab$ means "a followed by b".
Kleene star (*): $a^*$ means "zero or more a's": $\varepsilon, a, aa, aaa, \ldots$

Star binds tightest, then concatenation, then union. So $ab^* + c$ means $(a(b^*)) + c$. A language is called regular if some regular expression (or DFA — next section) describes it.

Regular expression (regex) হলো একটা ছোট formula, যেটা একটা language বর্ণনা করে। এতে মাত্র তিনটা operation থাকে:

Union (+): $a + b$ মানে "a অথবা b"। কোনো কোনো বইয়ে $a \mid b$ লেখা হয়।
Concatenation: $ab$ মানে "a-এর পরে b"।
Kleene star (*): $a^*$ মানে "শূন্য বা তার বেশি a": $\varepsilon, a, aa, aaa, \ldots$

Star সবচেয়ে আগে বসে, তারপর concatenation, তারপর union। তাই $ab^* + c$ মানে $(a(b^*)) + c$। কোনো language-কে regular বলা হয় যদি কোনো regular expression (বা DFA — পরের section) সেটা বর্ণনা করতে পারে।

Example:

Write a regex for each language over $\Sigma = \{0,1\}$:

Strings ending in 01: $(0+1)^*01$. Read it as "anything, then 01 at the end".
Strings starting with 1: $1(0+1)^*$.
Strings containing substring 11: $(0+1)^*11(0+1)^*$.
Strings of even length: $((0+1)(0+1))^*$. Each loop step adds exactly 2 symbols.
Strings with no 1 at all: $0^*$.
Strings where every 1 is followed by at least one 0: $(0 + 10)^*$.

$\Sigma = \{0,1\}$-এর উপর প্রতিটা language-এর জন্য regex লিখুন:

01 দিয়ে শেষ হওয়া string: $(0+1)^*01$। পড়ুন এভাবে — "যেকোনো কিছু, তারপর শেষে 01"।
1 দিয়ে শুরু হওয়া string: $1(0+1)^*$।
11 substring থাকা string: $(0+1)^*11(0+1)^*$।
Even length-এর string: $((0+1)(0+1))^*$। প্রতি loop step-এ ঠিক 2টা symbol যোগ হয়।
যে string-এ কোনো 1 নেই: $0^*$।
যেখানে প্রতিটা 1-এর পরে কমপক্ষে একটা 0 আছে: $(0 + 10)^*$।

Example — at least one 0 AND at least one 1:

Write a regex for binary strings that contain at least one 0 and at least one 1. This is a recurring BUET-style question.

Way 1 (case split): either some 0 comes before some 1, or some 1 comes before some 0:

\[ (0+1)^*\,0\,(0+1)^*\,1\,(0+1)^* \;+\; (0+1)^*\,1\,(0+1)^*\,0\,(0+1)^* \]

Way 2 (short trick): if a string has both symbols, then somewhere a 0 must sit right next to a 1. So the string must contain 01 or 10:

\[ (0+1)^*(01+10)(0+1)^* \]

Both are correct. Quick check: 000 fails (no 1), 1 fails (no 0), 10 is accepted — it matches the middle part directly.

এমন binary string-এর জন্য regex লিখুন যাতে কমপক্ষে একটা 0 আর কমপক্ষে একটা 1 আছে। এটা BUET-style-এ বারবার আসা প্রশ্ন।

Way 1 (case ভাগ করে): হয় কোনো 0 কোনো 1-এর আগে আসে, নয়তো কোনো 1 কোনো 0-এর আগে আসে:

\[ (0+1)^*\,0\,(0+1)^*\,1\,(0+1)^* \;+\; (0+1)^*\,1\,(0+1)^*\,0\,(0+1)^* \]

Way 2 (ছোট কৌশল): string-এ দুই symbol-ই থাকলে, কোথাও না কোথাও একটা 0 একটা 1-এর ঠিক পাশে থাকবেই। তাই string-এ 01 বা 10 থাকতেই হবে:

\[ (0+1)^*(01+10)(0+1)^* \]

দুটোই সঠিক। দ্রুত check: 000 fail (1 নেই), 1 fail (0 নেই), 10 accepted — মাঝের অংশের সাথে সরাসরি মেলে।

Example — asked April 2017:

BUET asked: write a regular expression for "one or more alphanumeric characters, followed by an even number of digits".

Answer: [a-zA-Z0-9]+([0-9][0-9])*

[a-zA-Z0-9]+ — one or more alphanumeric characters (letters or digits). The + means "at least one".
([0-9][0-9])* — digits taken two at a time, repeated zero or more times. Each loop adds exactly 2 digits, so the digit count is always even. Zero repeats gives 0 digits — and 0 is even, so that case is also correct.

In pure TOC notation: let $A$ = any alphanumeric symbol and $D$ = any digit. Then the answer is $AA^*(DD)^*$. The $AA^*$ part is exactly "one or more" (that is what + means), and $(DD)^*$ is "even number of digits".

BUET জিজ্ঞেস করেছিল: "এক বা তার বেশি alphanumeric character, তারপর even সংখ্যক digit"-এর জন্য একটা regular expression লিখুন।

Answer: [a-zA-Z0-9]+([0-9][0-9])*

[a-zA-Z0-9]+ — এক বা তার বেশি alphanumeric character (letter বা digit)। + মানে "কমপক্ষে একটা"।
([0-9][0-9])* — digit গুলো দুটো করে জোড়ায়, শূন্য বা তার বেশি বার repeat। প্রতি loop-এ ঠিক 2টা digit যোগ হয়, তাই digit-এর count সবসময় even। শূন্যবার repeat মানে 0টা digit — 0-ও even, তাই সেই case-ও ঠিক।

Pure TOC notation-এ: ধরুন $A$ = যেকোনো alphanumeric symbol আর $D$ = যেকোনো digit। তাহলে answer $AA^*(DD)^*$। $AA^*$ অংশটাই ঠিক "এক বা তার বেশি" (+-এর মানে এটাই), আর $(DD)^*$ হলো "even সংখ্যক digit"।

Useful regex identitiesদরকারি regex identity

IdentityIdentity	Meaningমানে
$r + r = r$	Union with itself changes nothing.নিজের সাথে union করলে কিছু বদলায় না।
$r + \emptyset = r$	Empty language is the identity for union.Union-এর জন্য empty language হলো identity।
$r\varepsilon = \varepsilon r = r$	Epsilon is the identity for concatenation.Concatenation-এর জন্য $\varepsilon$ হলো identity।
$r\emptyset = \emptyset$	Concatenating with the empty language kills everything.Empty language-এর সাথে concatenate করলে সব শেষ।
$(r^)^ = r^*$	Star of star is still star.Star-এর star মানেও star-ই।
$\varepsilon^* = \varepsilon$, $\emptyset^* = \varepsilon$	Star always contains at least $\varepsilon$.Star-এ সবসময় কমপক্ষে $\varepsilon$ থাকে।
$(a+b)^* = (a^b^)^*$	Both mean "all strings of a's and b's".দুটোরই মানে "a আর b-এর সব string"।

Note:

Careful: $\emptyset$ (empty language, no strings) and $\varepsilon$ (empty string, one string of length 0) are NOT the same. $L(\emptyset) = \{\}$ but $L(\varepsilon) = \{\varepsilon\}$. Exams love this trap.

সাবধান: $\emptyset$ (empty language, কোনো string নেই) আর $\varepsilon$ (empty string, length 0-এর একটা string) এক জিনিস না। $L(\emptyset) = \{\}$ কিন্তু $L(\varepsilon) = \{\varepsilon\}$। Exam-এ এই trap খুব আসে।

Exam tip — Pumping Lemma intuition:

A DFA has a fixed, finite number of states. If a string is longer than the number of states, the machine must visit some state twice — so there is a loop. That loop part can be repeated ("pumped") any number of times and the string stays in the language. This is the pumping lemma.

Why is $L = \{a^n b^n\}$ not regular? To accept it, a machine must count the a's, then match that count with b's. But a DFA has finite memory (only its states). It cannot count an unlimited $n$. If we pump the loop inside the a-part, we get more a's than b's — the pumped string leaves the language. Contradiction, so $L$ is not regular.

Quick trick: if a language needs unbounded counting or matching (equal counts, balanced brackets, palindromes), it is NOT regular. If it only needs to remember a finite pattern (ends in 01, contains 11, length mod 3), it IS regular.

একটা DFA-তে state-এর সংখ্যা fixed আর finite। কোনো string যদি state সংখ্যার চেয়ে লম্বা হয়, machine-কে কোনো state-এ দুইবার যেতেই হবে — মানে একটা loop আছে। ওই loop অংশটা যতবার খুশি repeat ("pump") করা যায়, string তবুও language-এই থাকে। এটাই pumping lemma।

$L = \{a^n b^n\}$ কেন regular না? এটা accept করতে হলে machine-কে a গুনতে হবে, তারপর সেই সংখ্যা b-এর সাথে মেলাতে হবে। কিন্তু DFA-এর memory finite (শুধু তার state গুলো)। সে unlimited $n$ গুনতে পারে না। a-অংশের ভেতরের loop pump করলে b-এর চেয়ে বেশি a হয়ে যায় — pumped string আর language-এ থাকে না। Contradiction, তাই $L$ regular না।

Quick trick: কোনো language-এ unbounded counting বা matching লাগলে (equal count, balanced bracket, palindrome) — সেটা regular না। শুধু finite pattern মনে রাখলেই চললে (ends in 01, contains 11, length mod 3) — সেটা regular।

Pumping Lemma is a NEGATIVE proofPumping Lemma একটা NEGATIVE proof

The pumping lemma says: if $L$ is regular, then every string $s \in L$ with $|s| \ge p$ (the pumping length) can be split as $s = xyz$ with three conditions: $|xy| \le p$, $|y| \ge 1$, and $xy^iz \in L$ for every $i \ge 0$.

Look carefully at the direction of that sentence. It is a ONE-WAY implication:

\[ L \text{ is regular} \implies L \text{ satisfies the pumping property} \]

Logic gives us only the contrapositive for free:

\[ L \text{ fails the pumping property} \implies L \text{ is NOT regular} \]

So the lemma can only ever prove that a language is not regular. That is why it is called a negative proof — it is a tool for refuting, never for confirming. The converse is FALSE: if a language passes the pumping test, we learn nothing. It may still be non-regular. To prove a language IS regular, you must build something positive instead: a DFA, an NFA, or a regular expression.

Pumping lemma বলে: $L$ যদি regular হয়, তাহলে $|s| \ge p$ (pumping length) দৈর্ঘ্যের প্রতিটা string $s \in L$-কে $s = xyz$ ভাবে ভাঙা যায়, তিনটা শর্তসহ: $|xy| \le p$, $|y| \ge 1$, আর প্রতিটা $i \ge 0$-এর জন্য $xy^iz \in L$।

বাক্যটার দিক ভালো করে খেয়াল করুন। এটা এক-মুখী (ONE-WAY) implication:

\[ L \text{ is regular} \implies L \text{ satisfies the pumping property} \]

Logic থেকে আমরা free পাই শুধু contrapositive-টা:

\[ L \text{ fails the pumping property} \implies L \text{ is NOT regular} \]

তাই lemma-টা শুধু এটুকুই প্রমাণ করতে পারে যে একটা language regular না। এজন্যই একে negative proof বলা হয় — এটা refute করার tool, confirm করার না। উল্টো দিকটা মিথ্যা: কোনো language pumping test pass করলে আমরা কিছুই শিখি না। সেটা তবুও non-regular হতে পারে। কোনো language regular — এটা প্রমাণ করতে হলে positive কিছু বানাতে হবে: একটা DFA, NFA, বা regular expression।

Example — full negative proof that $a^n b^n$ is not regular:

Play it like a game against the lemma:

Assume $L = \{a^n b^n \mid n \ge 0\}$ IS regular. Then some pumping length $p$ exists.
Choose the string $s = a^p b^p$. It is in $L$, and $|s| = 2p \ge p$. Good.
Split: the lemma says $s = xyz$ with $|xy| \le p$ and $|y| \ge 1$. The first $p$ symbols of $s$ are ALL a's, so $y$ can contain only a's: $y = a^k$ for some $k \ge 1$.
Pump: take $i = 2$. Then $xy^2z = a^{p+k}b^p$. Now there are more a's than b's, so $xy^2z \notin L$. (Pumping down with $i = 0$ gives $a^{p-k}b^p$ — also out.)
Contradiction: the lemma promised $xy^iz \in L$ for all $i$, but we found an $i$ that fails. So the assumption in step 1 was wrong — $L$ is not regular. ∎

Lemma-র বিরুদ্ধে খেলার মতো করে ভাবুন:

Assume করুন $L = \{a^n b^n \mid n \ge 0\}$ regular। তাহলে কোনো একটা pumping length $p$ আছে।
Choose করুন string $s = a^p b^p$। এটা $L$-এ আছে, আর $|s| = 2p \ge p$। ঠিক আছে।
Split: lemma বলে $s = xyz$, যেখানে $|xy| \le p$ আর $|y| \ge 1$। $s$-এর প্রথম $p$টা symbol সবই a, তাই $y$-তে শুধু a থাকতে পারে: $y = a^k$, কোনো $k \ge 1$-এর জন্য।
Pump: $i = 2$ নিন। তাহলে $xy^2z = a^{p+k}b^p$। এখন b-এর চেয়ে a বেশি, তাই $xy^2z \notin L$। ($i = 0$ দিয়ে pump down করলে $a^{p-k}b^p$ — সেটাও বাইরে।)
Contradiction: lemma কথা দিয়েছিল সব $i$-এর জন্য $xy^iz \in L$, কিন্তু আমরা একটা $i$ পেলাম যেটা fail করে। তাই step 1-এর assumption ভুল — $L$ regular না। ∎

Warning — passing the pumping test proves NOTHING:

There exist non-regular languages that still satisfy the pumping lemma. Classic example: $L = \{a^m b^n c^n \mid m \ge 1,\ n \ge 0\} \cup \{b^n c^k \mid n, k \ge 0\}$.

Every long string in $L$ CAN be pumped: if it starts with a, pump the first a — with 2 or more a's the "b-count = c-count" rule no longer applies, and pumping down to zero a's lands in the second set. If it starts with b or c, pump that first symbol — the string stays of the form $b^n c^k$.
Yet $L$ is NOT regular: intersect it with the regular language $ab^*c^*$ and you get $\{a b^n c^n\}$, which needs unbounded counting. If $L$ were regular, this intersection would be regular too — contradiction.

Moral: failing the lemma ⇒ not regular. Passing the lemma ⇒ no conclusion at all.

এমন non-regular language আছে যারা তবুও pumping lemma satisfy করে। Classic উদাহরণ: $L = \{a^m b^n c^n \mid m \ge 1,\ n \ge 0\} \cup \{b^n c^k \mid n, k \ge 0\}$।

$L$-এর প্রতিটা লম্বা string pump করা যায়: string a দিয়ে শুরু হলে প্রথম a-টা pump করুন — 2 বা বেশি a থাকলে "b-count = c-count" নিয়মটা আর খাটে না, আর pump down করে a শূন্য করলে দ্বিতীয় set-এ পড়ে। b বা c দিয়ে শুরু হলে প্রথম symbol-টা pump করুন — string $b^n c^k$ আকারেই থাকে।
তবুও $L$ regular না: একে regular language $ab^*c^*$-এর সাথে intersect করলে পাওয়া যায় $\{a b^n c^n\}$, যেটার জন্য unbounded counting লাগে। $L$ regular হলে এই intersection-ও regular হতো — contradiction।

শিক্ষা: lemma fail করা ⇒ regular না। Lemma pass করা ⇒ কোনো সিদ্ধান্তই না।

Note — asked April 2024:

BUET (April 2024) asked exactly this: "Why is it said that the pumping lemma is a negative proof?" A full-marks answer: state the one-way implication, write its contrapositive, say "so it can only DISPROVE regularity, never prove it", and give one example — the $a^nb^n$ proof above plus the warning that some non-regular languages still pass the test.

BUET (April 2024) ঠিক এটাই জিজ্ঞেস করেছিল: "Why is it said that the pumping lemma is a negative proof?" Full-marks উত্তর: এক-মুখী implication-টা লিখুন, তার contrapositive লিখুন, বলুন "তাই এটা শুধু regularity DISPROVE করতে পারে, কখনো prove করতে পারে না", আর একটা উদাহরণ দিন — উপরের $a^nb^n$ proof, সাথে এই সাবধানবাণী যে কিছু non-regular language-ও test pass করে।

2. DFA and NFA2. DFA আর NFA

DFA: formal definitionDFA: formal definition

A DFA (Deterministic Finite Automaton) is a small machine with a finite number of states. It reads a string one symbol at a time. From each state, each symbol leads to exactly ONE next state — that is why it is called deterministic.

Formally, a DFA is a 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$:

$Q$: finite set of states
$\Sigma$: input alphabet
$\delta: Q \times \Sigma \to Q$: transition function (one next state, always defined)
$q_0 \in Q$: start state
$F \subseteq Q$: set of accept (final) states

The machine accepts a string if, after reading the whole string, it stops in an accept state.

DFA (Deterministic Finite Automaton) হলো finite সংখ্যক state-ওয়ালা একটা ছোট machine। এটা string-কে এক symbol করে পড়ে। প্রতিটা state থেকে প্রতিটা symbol ঠিক একটাই পরের state-এ নিয়ে যায় — এজন্যই একে deterministic বলা হয়।

Formally, DFA একটা 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$:

$Q$: state-এর finite set
$\Sigma$: input alphabet
$\delta: Q \times \Sigma \to Q$: transition function (একটাই পরের state, সবসময় defined)
$q_0 \in Q$: start state
$F \subseteq Q$: accept (final) state-এর set

পুরো string পড়ার পর machine যদি কোনো accept state-এ থামে, তাহলে string-টা accept হয়।

Worked example: DFA for "strings ending in 01"Worked example: "01 দিয়ে শেষ হওয়া string"-এর DFA

Let us build it step by step. The machine only needs to remember "how much of 01 have I just seen?" That gives three states:

A: no useful progress (start state)
B: the last symbol was 0 (halfway there)
C: the last two symbols were 01 (accept!)

Now fill the moves. In A, reading 0 gives progress → go to B; reading 1 gives nothing → stay in A. In B, reading 1 completes 01 → go to C; reading 0 means the last symbol is still 0 → stay in B. In C, reading 0 → the last symbol is 0 → go to B; reading 1 → last two are 11, no progress → go to A.

ধাপে ধাপে বানাই। Machine-কে শুধু মনে রাখতে হবে "এইমাত্র 01-এর কতটুকু দেখলাম?" তাতেই তিনটা state হয়:

A: কোনো কাজের progress নেই (start state)
B: শেষ symbol ছিল 0 (অর্ধেক হয়েছে)
C: শেষ দুই symbol ছিল 01 (accept!)

এবার move গুলো বসাই। A-তে 0 পড়লে progress হয় → B-তে যান; 1 পড়লে কিছুই হয় না → A-তেই থাকুন। B-তে 1 পড়লে 01 complete → C-তে যান; 0 পড়লে শেষ symbol এখনো 0 → B-তেই থাকুন। C-তে 0 পড়লে শেষ symbol 0 → B-তে যান; 1 পড়লে শেষ দুইটা 11, progress নেই → A-তে যান।

DFA for binary strings ending in 01. Double circle = accept state. 01 দিয়ে শেষ হওয়া binary string-এর DFA। Double circle = accept state।

The same machine as a transition table:

একই machine transition table আকারে:

δ	on 00 পড়লে	on 11 পড়লে
→ A (start)	B	A
B	B	C
* C (accept)	B	A

Example:

Trace the string 1001 on this DFA: A --1--> A --0--> B --0--> B --1--> C. We end in C, an accept state. So 1001 is accepted — and yes, it ends in 01. Now trace 010: A --0--> B --1--> C --0--> B. We end in B, not accepting. Rejected — correct, it ends in 10.

1001 string-টা এই DFA-তে trace করুন: A --1--> A --0--> B --0--> B --1--> C। শেষে C-তে, একটা accept state। তাই 1001 accepted — আর সত্যিই এটা 01 দিয়ে শেষ। এবার 010 trace করুন: A --0--> B --1--> C --0--> B। শেষে B-তে, accept না। Rejected — ঠিকই আছে, এটা 10 দিয়ে শেষ।

Example:

One more classic: DFA for "even number of 0s". Two states are enough: E = "even 0s so far" (start and accept), O = "odd 0s so far". Reading 0 flips E↔O. Reading 1 changes nothing (self-loop). The empty string has zero 0s (even), so E must be accepting.

আরেকটা classic: "even সংখ্যক 0"-এর DFA। দুইটা state-ই যথেষ্ট: E = "এখন পর্যন্ত even সংখ্যক 0" (start এবং accept), O = "odd সংখ্যক 0"। 0 পড়লে E↔O উল্টে যায়। 1 পড়লে কিছু বদলায় না (self-loop)। Empty string-এ শূন্যটা 0 আছে (even), তাই E accept state হতেই হবে।

Worked example: DFA for binary numbers divisible by 3Worked example: 3 দিয়ে বিভাজ্য binary number-এর DFA

Task: accept a binary string exactly when the number it represents is divisible by 3. Trick: you never need the whole number — only its remainder mod 3. So 3 states are enough: $q_0$ (remainder 0), $q_1$ (remainder 1), $q_2$ (remainder 2). Start state and accept state: $q_0$.

Reading one more bit $b$ turns the number $N$ into $2N + b$ (shift left, then add the bit). So the remainder updates by one simple rule:

কাজ: একটা binary string তখনই accept করতে হবে যখন সংখ্যাটা 3 দিয়ে বিভাজ্য। Trick: পুরো সংখ্যাটা মনে রাখা লাগে না — লাগে শুধু তার remainder mod 3। তাই 3টা state-ই যথেষ্ট: $q_0$ (remainder 0), $q_1$ (remainder 1), $q_2$ (remainder 2)। Start state আর accept state: $q_0$।

আরেকটা bit $b$ পড়লে সংখ্যা $N$ হয়ে যায় $2N + b$ (বামে shift, তারপর bit যোগ)। তাই remainder update হয় একটা সহজ নিয়মে:

\[ r' = (2r + b) \bmod 3 \]

State (remainder)State (remainder)	on 00 পড়লে	on 11 পড়লে
$q_0$ (r = 0) — start, acceptstart, accept	$q_0$ — (2·0+0) mod 3 = 0	$q_1$ — (2·0+1) mod 3 = 1
$q_1$ (r = 1)	$q_2$ — (2·1+0) mod 3 = 2	$q_0$ — (2·1+1) mod 3 = 0
$q_2$ (r = 2)	$q_1$ — (2·2+0) mod 3 = 1	$q_2$ — (2·2+1) mod 3 = 2

Example:

Check 110 (= 6). Start $q_0$ → read 1 → $q_1$ → read 1 → $q_0$ → read 0 → $q_0$. We end in $q_0$ = accept, and 6 IS divisible by 3. Now check 101 (= 5): $q_0$ → $q_1$ → $q_2$ → $q_2$. Not an accept state — correct, because 5 is not divisible by 3.

110 (= 6) check করি। Start $q_0$ → 1 পড়ে → $q_1$ → 1 পড়ে → $q_0$ → 0 পড়ে → $q_0$। শেষে $q_0$-তে = accept, আর 6 আসলেই 3 দিয়ে বিভাজ্য। এবার 101 (= 5): $q_0$ → $q_1$ → $q_2$ → $q_2$। Accept state না — ঠিকই আছে, কারণ 5 বিভাজ্য না।

Note: "divisible by k" always needs exactly k remainder states. This mod-3 DFA is a classic exam favorite — memorize the update rule $r' = (2r + b) \bmod 3$ and you can rebuild the whole table in seconds.

Note: "k দিয়ে বিভাজ্য" language-এর জন্য সবসময় ঠিক kটা remainder state লাগে। এই mod-3 DFA পরীক্ষার খুব প্রিয় প্রশ্ন — update rule $r' = (2r + b) \bmod 3$ মনে রাখলে পুরো table কয়েক সেকেন্ডে বানিয়ে ফেলা যায়।

NFA: nondeterminismNFA: nondeterminism

An NFA (Nondeterministic Finite Automaton) relaxes the rules. From a state, one symbol may lead to zero, one, or MANY next states. It may also jump without reading anything (an $\varepsilon$-move). Think of it as trying all choices in parallel. The NFA accepts a string if AT LEAST ONE path of choices ends in an accept state.

Formally the only change is the transition function: $\delta: Q \times (\Sigma \cup \{\varepsilon\}) \to 2^Q$ — it returns a SET of states.

NFA (Nondeterministic Finite Automaton)-তে নিয়ম শিথিল। একটা state থেকে একটা symbol শূন্য, এক, বা অনেকগুলো পরের state-এ নিতে পারে। কিছু না পড়েই jump-ও করতে পারে ($\varepsilon$-move)। ভাবুন — সব choice একসাথে parallel-এ চেষ্টা করছে। কমপক্ষে একটা path যদি accept state-এ শেষ হয়, NFA string-টা accept করে।

Formally শুধু transition function বদলায়: $\delta: Q \times (\Sigma \cup \{\varepsilon\}) \to 2^Q$ — এটা state-এর একটা SET return করে।

	DFA	NFA
Moves per symbolপ্রতি symbol-এ move	Exactly oneঠিক একটা	Zero, one, or manyশূন্য, এক, বা অনেক
$\varepsilon$-moves	Not allowedনেই	Allowedআছে
Power (languages accepted)Power (কোন language পারে)	Equal! Both accept exactly the regular languages.সমান! দুটোই ঠিক regular language গুলো accept করে।
Ease of designDesign করা কত সহজ	Harder, more statesকঠিন, বেশি state	Easier, fewer statesসহজ, কম state
Conversion costConversion-এর খরচ	NFA with $n$ states → DFA with at most $2^n$ states$n$ state-এর NFA → সর্বোচ্চ $2^n$ state-এর DFA

Example — asked April 2019:

BUET asked: construct an NFA that accepts binary strings with an odd number of 1s OR an even number of 0s.

The clean trick for any "OR" language: build one small DFA for each condition, then join them with a new start state and two $\varepsilon$-moves. The NFA "guesses" which condition to check — and it accepts if at least one branch accepts. This is exactly the union construction.

Branch 1 (odd 1s): states A0 = "even 1s so far" (start of branch), A1 = "odd 1s" (accept). Reading 1 flips A0↔A1; reading 0 changes nothing.
Branch 2 (even 0s): states B0 = "even 0s" (start of branch, accept), B1 = "odd 0s". Reading 0 flips B0↔B1; reading 1 changes nothing.
Glue: new start state q0 with $\varepsilon$-moves to A0 and B0. Accept states: {A1, B0}.

BUET জিজ্ঞেস করেছিল: এমন একটা NFA বানান যা odd সংখ্যক 1 OR even সংখ্যক 0 থাকা binary string accept করে।

যেকোনো "OR" language-এর সহজ কৌশল: প্রতিটা শর্তের জন্য একটা ছোট DFA বানান, তারপর একটা নতুন start state আর দুইটা $\varepsilon$-move দিয়ে জোড়া লাগান। NFA "guess" করে কোন শর্তটা check করবে — কমপক্ষে একটা branch accept করলেই accept। এটাই union construction।

Branch 1 (odd 1s): state A0 = "এখন পর্যন্ত even সংখ্যক 1" (branch-এর start), A1 = "odd সংখ্যক 1" (accept)। 1 পড়লে A0↔A1 উল্টে যায়; 0 পড়লে কিছু বদলায় না।
Branch 2 (even 0s): state B0 = "even সংখ্যক 0" (branch-এর start, accept), B1 = "odd সংখ্যক 0"। 0 পড়লে B0↔B1 উল্টে যায়; 1 পড়লে কিছু বদলায় না।
জোড়া: নতুন start state q0, সাথে A0 আর B0-তে $\varepsilon$-move। Accept state: {A1, B0}।

δ	$\varepsilon$	on 00 পড়লে	on 11 পড়লে
→ q0 (start)	{A0, B0}	—	—
A0	—	{A0}	{A1}
* A1	—	{A1}	{A0}
* B0	—	{B1}	{B0}
B1	—	{B0}	{B1}

Quick checks: 1 → branch 1 reaches A1 (one 1, odd) → accepted. 00 → branch 2 reaches B0 (two 0s, even) → accepted. 0 → branch 1 ends in A0 (zero 1s, even — fail), branch 2 ends in B1 (one 0, odd — fail) → rejected. Correct! Also $\varepsilon$ is accepted (zero 0s is even) — via the $\varepsilon$-move to B0.

দ্রুত check: 1 → branch 1 পৌঁছায় A1-এ (একটা 1, odd) → accepted। 00 → branch 2 পৌঁছায় B0-তে (দুইটা 0, even) → accepted। 0 → branch 1 শেষ হয় A0-তে (শূন্যটা 1, even — fail), branch 2 শেষ হয় B1-এ (একটা 0, odd — fail) → rejected। ঠিক আছে! আর $\varepsilon$-ও accepted (শূন্যটা 0 মানে even) — B0-তে যাওয়া $\varepsilon$-move-এর মাধ্যমে।

Worked example: NFA → DFA (subset construction)Worked example: NFA → DFA (subset construction)

Here is a small NFA for "strings ending in 01". It just guesses when the final 01 starts:

"01 দিয়ে শেষ হওয়া string"-এর একটা ছোট NFA। এটা শুধু guess করে শেষের 01 কোথা থেকে শুরু:

NFA for $(0+1)^*01$. In q0, on 0 it can stay OR move to q1 — two choices, so nondeterministic. $(0+1)^*01$-এর NFA। q0-তে 0 পড়লে থাকতেও পারে, q1-এ যেতেও পারে — দুইটা choice, তাই nondeterministic।

Example — subset construction:

To convert, each DFA state is a SET of NFA states ("all the places the NFA could be right now"). Start from {q0} and follow every symbol:

{q0} on 0 → q0 can stay in q0 or go to q1 → {q0, q1}. On 1 → only stay → {q0}.
{q0, q1} on 0 → from q0: {q0, q1}; from q1: nothing → {q0, q1}. On 1 → from q0: {q0}; from q1: {q2} → {q0, q2}.
{q0, q2} on 0 → {q0, q1}. On 1 → {q0}. No new sets appear, so we stop.

Any set containing q2 is accepting. Rename {q0}=A, {q0,q1}=B, {q0,q2}=C — we get EXACTLY the 3-state DFA we built by hand above. Only 3 of the possible $2^3 = 8$ subsets were actually reachable.

Convert করতে হলে, DFA-এর প্রতিটা state হবে NFA state-এর একটা SET ("এই মুহূর্তে NFA যেসব জায়গায় থাকতে পারে")। {q0} থেকে শুরু করে প্রতিটা symbol ধরে এগোন:

{q0}-এ 0 পড়লে → q0 নিজে থাকতে পারে বা q1-এ যেতে পারে → {q0, q1}। 1 পড়লে → শুধু নিজেই → {q0}।
{q0, q1}-এ 0 পড়লে → q0 থেকে: {q0, q1}; q1 থেকে: কিছু না → {q0, q1}। 1 পড়লে → q0 থেকে: {q0}; q1 থেকে: {q2} → {q0, q2}।
{q0, q2}-এ 0 পড়লে → {q0, q1}। 1 পড়লে → {q0}। নতুন কোনো set আসছে না, তাই এখানেই শেষ।

q2 থাকা যেকোনো set হলো accept state। নাম দিন {q0}=A, {q0,q1}=B, {q0,q2}=C — উপরে হাতে বানানো 3-state DFA-টাই পাওয়া গেল। সম্ভব $2^3 = 8$টা subset-এর মধ্যে মাত্র 3টা reachable ছিল।

DFA state (set)DFA state (set)	on 00 পড়লে	on 11 পড়লে
→ A = {q0}	B	A
B = {q0, q1}	B	C
* C = {q0, q2}	B	A

DFA minimization (the idea)DFA minimization (মূল ধারণা)

Two states are equivalent if no input string can tell them apart — from both, every string leads to the same accept/reject result. Minimization merges equivalent states. The standard method: first split states into two groups (accepting, non-accepting), then keep splitting a group whenever two of its states go to different groups on some symbol. When nothing splits anymore, each group becomes one state of the minimal DFA. For every regular language, this minimal DFA is unique.

দুইটা state equivalent যদি কোনো input string-ই তাদের আলাদা করতে না পারে — দুই জায়গা থেকেই প্রতিটা string একই accept/reject result দেয়। Minimization এই equivalent state গুলো merge করে। Standard পদ্ধতি: প্রথমে state-দের দুই group-এ ভাগ করুন (accepting, non-accepting), তারপর কোনো group-এর দুইটা state কোনো symbol-এ ভিন্ন group-এ গেলে সেই group ভাঙুন। আর কিছু না ভাঙলে, প্রতিটা group minimal DFA-এর একটা state হয়। প্রতিটা regular language-এর জন্য এই minimal DFA unique।

Note:

Exam favorites: (1) "The minimal DFA for strings ending in 01 has how many states?" Answer: 3. (2) "An NFA has n states. The equivalent DFA has at most how many?" Answer: $2^n$. (3) Remember: NFA and DFA have EQUAL power — nondeterminism adds convenience, not power, for finite automata.

Exam-এর প্রিয় প্রশ্ন: (1) "01 দিয়ে শেষ হওয়া string-এর minimal DFA-তে কয়টা state?" উত্তর: 3। (2) "একটা NFA-তে n state আছে। Equivalent DFA-তে সর্বোচ্চ কয়টা?" উত্তর: $2^n$। (3) মনে রাখুন: NFA আর DFA-এর power সমান — finite automata-র ক্ষেত্রে nondeterminism সুবিধা দেয়, extra power দেয় না।

3. CFG and PDA3. CFG আর PDA

Context-Free Grammar (CFG): the partsContext-Free Grammar (CFG): অংশগুলো

A CFG is a set of rewriting rules. It is a 4-tuple $G = (V, T, P, S)$:

$V$: variables (non-terminals), written in capital letters, like $S, A, E$
$T$: terminals — the actual alphabet symbols, like $a, b, +, id$
$P$: productions — rules like $S \to aSb$. "Context-free" means the left side is always a SINGLE variable.
$S$: the start symbol

A derivation starts from $S$ and keeps replacing variables using rules until only terminals remain. Leftmost derivation always replaces the leftmost variable first; rightmost replaces the rightmost first.

CFG হলো কিছু rewriting rule-এর set। এটা একটা 4-tuple $G = (V, T, P, S)$:

$V$: variables (non-terminal), capital letter-এ লেখা হয়, যেমন $S, A, E$
$T$: terminals — আসল alphabet symbol, যেমন $a, b, +, id$
$P$: productions — rule, যেমন $S \to aSb$। "Context-free" মানে বাম পাশে সবসময় মাত্র একটা variable।
$S$: start symbol

Derivation শুরু হয় $S$ থেকে, আর rule দিয়ে variable বদলাতে থাকে যতক্ষণ না শুধু terminal থাকে। Leftmost derivation-এ সবসময় সবচেয়ে বামের variable আগে বদলায়; rightmost-এ সবচেয়ে ডানেরটা।

Worked example: CFG for $a^n b^n$Worked example: $a^n b^n$-এর CFG

Example:

The language $L = \{a^n b^n \mid n \ge 0\}$ = { $\varepsilon$, ab, aabb, aaabbb, ... }. Grammar:

S → aSb | ε

Each use of $S \to aSb$ adds one a on the left AND one b on the right — so counts always stay equal. Derivation of aabb (leftmost):

S ⇒ aSb ⇒ aaSbb ⇒ aabb   (last step uses S → ε)

Language $L = \{a^n b^n \mid n \ge 0\}$ = { $\varepsilon$, ab, aabb, aaabbb, ... }। Grammar:

S → aSb | ε

$S \to aSb$ প্রতিবার ব্যবহারে বামে একটা a আর ডানে একটা b যোগ হয় — তাই count সবসময় সমান থাকে। aabb-এর derivation (leftmost):

S ⇒ aSb ⇒ aaSbb ⇒ aabb   (শেষ step-এ S → ε)

More practice grammars: palindromes over {a,b}: S → aSa | bSb | a | b | ε. Balanced parentheses: S → (S)S | ε. Equal number of a's and b's in any order: S → aSbS | bSaS | ε.

আরো practice grammar: {a,b}-এর উপর palindrome: S → aSa | bSb | a | b | ε। Balanced parentheses: S → (S)S | ε। যেকোনো order-এ সমান সংখ্যক a আর b: S → aSbS | bSaS | ε।

Worked example: even-length palindromes over {a,b,c} — asked October 2017Worked example: {a,b,c}-এর উপর even-length palindrome — asked October 2017

BUET asked exactly this (October 2017): write a CFG for all non-empty, even-length palindromes over $\{a, b, c\}$. Think outside-in: an even-length palindrome must start and end with the SAME symbol. Peel that outer pair off — what is left in the middle is again an even-length palindrome (or nothing). The smallest members of the language are the two-symbol palindromes aa, bb, cc. That thinking gives the grammar directly:

S → aSa | bSb | cSc | aa | bb | cc

Why no $\varepsilon$ rule? The language must be non-empty, so we stop at a two-letter core instead of at $\varepsilon$. Why no single-letter rules like S → a? A single letter in the center would make the length odd. Every rule adds symbols two at a time, so the length is always even.

BUET ঠিক এটাই জিজ্ঞেস করেছিল (October 2017): $\{a, b, c\}$-এর উপর সব non-empty, even-length palindrome-এর একটা CFG লিখুন। ভাবুন outside-in: even-length palindrome-এর শুরু আর শেষ symbol একই হতে বাধ্য। ওই বাইরের জোড়াটা খুলে ফেলুন — মাঝে যা থাকে সেটাও আবার একটা even-length palindrome (বা কিছুই না)। Language-এর সবচেয়ে ছোট সদস্য হলো দুই-symbol-এর palindrome aa, bb, cc। এই চিন্তা থেকেই grammar সরাসরি বেরিয়ে আসে:

S → aSa | bSb | cSc | aa | bb | cc

$\varepsilon$ rule নেই কেন? Language-টা non-empty হতে হবে, তাই আমরা $\varepsilon$-তে না থেমে দুই-অক্ষরের core-এ থামি। S → a-এর মতো এক-অক্ষরের rule নেই কেন? মাঝে একটা একা অক্ষর থাকলে length odd হয়ে যেত। প্রতিটা rule একসাথে দুইটা করে symbol যোগ করে, তাই length সবসময় even।

Example — derivation of abccba:

Read the target outside-in: outer pair a...a, next pair b...b, core cc.

S ⇒ aSa        (rule S → aSa: outer pair a...a)
  ⇒ abSba      (rule S → bSb: next pair b...b)
  ⇒ abccba     (rule S → cc: the two-letter core)

Each step wraps one matching pair around both sides, and the last rule drops in a two-letter core. So the string always reads the same both ways, and its length is always even — exactly what the question asked for.

Target-টা outside-in পড়ুন: বাইরের জোড়া a...a, পরের জোড়া b...b, core cc।

S ⇒ aSa        (rule S → aSa: বাইরের জোড়া a...a)
  ⇒ abSba      (rule S → bSb: পরের জোড়া b...b)
  ⇒ abccba     (rule S → cc: দুই-অক্ষরের core)

প্রতিটা step দুই পাশে একটা matching জোড়া জড়িয়ে দেয়, আর শেষ rule-টা মাঝে দুই-অক্ষরের core বসায়। তাই string দুই দিক থেকেই একই পড়া যায়, আর length সবসময় even — প্রশ্নে ঠিক যা চাওয়া হয়েছিল।

Parse trees and ambiguityParse tree আর ambiguity

A parse tree shows a derivation as a tree: root = start symbol, leaves = the string. A grammar is ambiguous if some string has TWO different parse trees (equivalently, two different leftmost derivations). The classic example:

E → E + E | E * E | id

The string id + id * id has two parse trees. One groups it as id + (id * id) (multiplication first — what we want). The other groups it as (id + id) * id (wrong precedence).

Parse tree একটা derivation-কে গাছ আকারে দেখায়: root = start symbol, leaf গুলো = string। কোনো string-এর যদি দুইটা আলাদা parse tree থাকে (মানে দুইটা আলাদা leftmost derivation), তাহলে grammar-টা ambiguous। Classic উদাহরণ:

E → E + E | E * E | id

id + id * id string-টার দুইটা parse tree আছে। একটা group করে id + (id * id) হিসেবে (আগে multiplication — যেটা আমরা চাই)। অন্যটা (id + id) * id হিসেবে (ভুল precedence)।

Two parse trees for the same string — so the grammar is ambiguous. একই string-এর দুইটা parse tree — তাই grammar-টা ambiguous।

Note:

The fix used in real compilers: layer the grammar so precedence is forced — E → E + T | T, T → T * F | F, F → (E) | id. This unambiguous version makes * bind tighter than +, and both left-associative. Exams often ask you to show ambiguity OR to write this fixed grammar.

আসল compiler-এ যে সমাধান ব্যবহার হয়: grammar-কে স্তরে সাজান যাতে precedence বাধ্যতামূলক হয় — E → E + T | T, T → T * F | F, F → (E) | id। এই unambiguous version-এ *, +-এর চেয়ে শক্ত করে বসে, আর দুটোই left-associative। Exam-এ প্রায়ই ambiguity দেখাতে বা এই ঠিক করা grammar লিখতে বলে।

Chomsky hierarchyChomsky hierarchy

TypeType	Grammar / LanguageGrammar / Language	MachineMachine	Exampleউদাহরণ
Type 3	Regular	Finite Automaton (DFA/NFA)	$(0+1)^*01$
Type 2	Context-Free (CFL)	Pushdown Automaton (PDA)	$a^n b^n$
Type 1	Context-Sensitive	Linear Bounded Automaton (LBA)	$a^n b^n c^n$
Type 0	Recursively Enumerable	Turing Machine (TM)	Halting problem languageHalting problem-এর language

Each type sits INSIDE the next: Regular $\subset$ CFL $\subset$ CSL $\subset$ RE. So every regular language is also context-free, but not the other way around.

প্রতিটা type পরেরটার ভেতরে থাকে: Regular $\subset$ CFL $\subset$ CSL $\subset$ RE। তাই প্রতিটা regular language-ই context-free, কিন্তু উল্টোটা সত্যি না।

PDA: a finite automaton with a stackPDA: stack-ওয়ালা finite automaton

A PDA (Pushdown Automaton) = NFA + one stack of unlimited depth. At each step it reads a symbol (or $\varepsilon$), looks at the top of the stack, and may push or pop. PDAs accept exactly the context-free languages.

Why does $a^n b^n$ need a stack? The machine must remember an unbounded count $n$. Finite states cannot do that (that was the pumping lemma argument). A stack can: push one marker per a, then pop one marker per b. Accept if the stack is empty exactly when the input ends.

PDA (Pushdown Automaton) = NFA + unlimited গভীরতার একটা stack। প্রতি step-এ এটা একটা symbol (বা $\varepsilon$) পড়ে, stack-এর top দেখে, আর push বা pop করতে পারে। PDA ঠিক context-free language গুলোই accept করে।

$a^n b^n$-এর জন্য stack কেন লাগে? Machine-কে unbounded একটা count $n$ মনে রাখতে হবে। Finite state তা পারে না (pumping lemma-র যুক্তিটাই)। Stack পারে: প্রতিটা a-এর জন্য একটা marker push করুন, তারপর প্রতিটা b-এর জন্য একটা pop করুন। Input শেষ হওয়ার ঠিক সময়ে stack খালি থাকলে accept।

Example:

PDA trace on aabb (X = counter symbol, Z = bottom marker):

Input left   Stack (top→bottom)   Action
aabb         Z                    read a, push X
abb          X Z                  read a, push X
bb           X X Z                read b, pop X
b            X Z                  read b, pop X
(empty)      Z                    stack back to Z → accept

On aab, one X would remain — reject. On abb, a b arrives with no X to pop — reject.

aabb-এর উপর PDA trace (X = counter symbol, Z = bottom marker):

বাকি input    Stack (top→bottom)   Action
aabb         Z                    a পড়ুন, X push
abb          X Z                  a পড়ুন, X push
bb           X X Z                b পড়ুন, X pop
b            X Z                  b পড়ুন, X pop
(খালি)       Z                    stack আবার Z → accept

aab-এ একটা X থেকে যেত — reject। abb-এ pop করার মতো X ছাড়াই b আসে — reject।

Exam tip — "which class is L?" strategy:

Finite pattern only (ends with, contains, length mod k)? → Regular.
ONE unbounded comparison ($a^nb^n$, balanced brackets, $ww^R$ palindrome)? → Context-free, not regular. One stack handles one comparison.
TWO+ linked comparisons ($a^nb^nc^n$, $ww$, $a^nb^nc^md^m$ crossed)? → usually not context-free. $a^nb^nc^n$: after popping the stack for b's, nothing is left to check c's.

শুধু finite pattern (ends with, contains, length mod k)? → Regular।
একটা unbounded comparison ($a^nb^n$, balanced bracket, $ww^R$ palindrome)? → Context-free, regular না। একটা stack একটা comparison সামলাতে পারে।
দুই বা বেশি জোড়া লাগানো comparison ($a^nb^nc^n$, $ww$)? → সাধারণত context-free না। $a^nb^nc^n$: b-এর জন্য stack pop করার পর c check করার কিছুই থাকে না।

4. Turing Machines and Decidability4. Turing Machine আর Decidability

What is a Turing machine?Turing machine কী?

A Turing Machine (TM) is the most powerful model. Picture an infinite tape of cells, a head that reads/writes one cell, and a finite control. In one step the TM: reads the current cell, writes a symbol, moves the head Left or Right, and changes state. It halts when it reaches the accept state or the reject state — or it may loop forever.

Formally it is a 7-tuple $(Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$, where $\Gamma$ is the tape alphabet (it contains $\Sigma$ plus a blank symbol $\sqcup$) and $\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$.

The key upgrades over a PDA: the TM can WRITE anywhere, move BOTH directions, and reuse the tape as unlimited memory.

Turing Machine (TM) হলো সবচেয়ে শক্তিশালী model। কল্পনা করুন — cell-এর একটা infinite tape, একটা head যেটা এক cell পড়ে/লেখে, আর একটা finite control। এক step-এ TM: বর্তমান cell পড়ে, একটা symbol লেখে, head-কে Left বা Right সরায়, আর state বদলায়। Accept state বা reject state-এ পৌঁছালে halt করে — অথবা চিরকাল loop-ও করতে পারে।

Formally এটা একটা 7-tuple $(Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$, যেখানে $\Gamma$ হলো tape alphabet (এতে $\Sigma$ আর একটা blank symbol $\sqcup$ থাকে) এবং $\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$।

PDA-এর চেয়ে মূল upgrade: TM যেকোনো জায়গায় WRITE করতে পারে, দুই দিকেই যেতে পারে, আর tape-কে unlimited memory হিসেবে ব্যবহার করতে পারে।

Example:

TM idea for $L = \{0^n 1^n\}$ (works like crossing off pairs):

Scan right to the first 0; replace it with X.
Scan right to the first 1; replace it with Y. If none found → reject.
Return to the left end; repeat.
When no 0 is left, check that no 1 is left either. All crossed → accept.

Trace on 0011: 0011 → X011 → X0Y1 → XX Y1 → XXYY → accept. The same trick extends to $0^n1^n2^n$ — a TM easily does what a PDA cannot.

$L = \{0^n 1^n\}$-এর TM idea (জোড়া কেটে দেওয়ার মতো কাজ করে):

ডান দিকে গিয়ে প্রথম 0 খুঁজুন; সেটাকে X বানান।
ডান দিকে গিয়ে প্রথম 1 খুঁজুন; সেটাকে Y বানান। না পেলে → reject।
বাম প্রান্তে ফিরে যান; repeat করুন।
0 শেষ হলে check করুন কোনো 1-ও বাকি নেই। সব কাটা হলে → accept।

0011-এর trace: 0011 → X011 → X0Y1 → XXY1 → XXYY → accept। একই কৌশল $0^n1^n2^n$-এও চলে — PDA যা পারে না, TM সহজেই পারে।

Church-Turing thesisChurch-Turing thesis

The Church-Turing thesis says: anything that can be computed by ANY reasonable algorithm can be computed by a Turing machine. "Algorithm" and "Turing machine" mean the same thing. This is a thesis (a belief backed by evidence), not a theorem — but no counterexample has ever been found. Your laptop, Python, quantum computers — none can decide a language that a TM cannot.

Church-Turing thesis বলে: যেকোনো reasonable algorithm দিয়ে যা compute করা যায়, তা Turing machine দিয়েও করা যায়। "Algorithm" আর "Turing machine" আসলে একই জিনিস। এটা একটা thesis (প্রমাণসহ বিশ্বাস), theorem না — কিন্তু আজ পর্যন্ত কোনো counterexample পাওয়া যায়নি। আপনার laptop, Python, quantum computer — কেউই এমন language decide করতে পারে না যা TM পারে না।

Decidable, undecidable, recognizableDecidable, undecidable, recognizable

Decidable (recursive): some TM ALWAYS halts and answers yes/no correctly. Example: "is this string in $a^nb^n$?"
Recognizable (recursively enumerable, RE): some TM says yes (halts and accepts) for every string in the language — but for strings NOT in the language, it may loop forever instead of saying no.
Undecidable: NO TM decides it. Some undecidable languages are still recognizable (like the halting problem); some are not even recognizable (like the complement of the halting problem).

Fact worth memorizing: $L$ is decidable $\iff$ both $L$ and its complement $\overline{L}$ are recognizable.

Decidable (recursive): এমন একটা TM আছে যা সবসময় halt করে এবং সঠিক yes/no উত্তর দেয়। যেমন: "এই string কি $a^nb^n$-এ আছে?"
Recognizable (recursively enumerable, RE): এমন TM আছে যা language-এর প্রতিটা string-এর জন্য yes বলে (halt করে accept করে) — কিন্তু language-এর বাইরের string-এর জন্য no বলার বদলে চিরকাল loop করতে পারে।
Undecidable: কোনো TM-ই এটা decide করতে পারে না। কিছু undecidable language তবুও recognizable (যেমন halting problem); কিছু recognizable-ও না (যেমন halting problem-এর complement)।

মুখস্থ রাখার মতো fact: $L$ decidable $\iff$ $L$ এবং তার complement $\overline{L}$ দুটোই recognizable।

The halting problem (proof sketch)Halting problem (proof sketch)

HALT = "given a program $P$ and input $x$, does $P$ halt on $x$?" This is undecidable. Intuition proof (by contradiction):

Suppose a program H(P, x) exists that always correctly answers "halts" or "loops".
Build a mischievous program D(P): it runs H(P, P). If H says "P halts on P", then D deliberately loops forever. If H says "loops", then D halts.
Now ask: what does D(D) do? If D(D) halts, then H said "loops" — but H must be correct, contradiction. If D(D) loops, then H said "halts" — again contradiction.
Both cases are impossible → H cannot exist. HALT is undecidable.

This is the same self-reference trick as "this sentence is false". Many other questions reduce to HALT and are also undecidable: "does this program ever print X?", "are these two programs equivalent?", "is this CFG ambiguous?".

HALT = "program $P$ আর input $x$ দিলে, $P$ কি $x$-এর উপর halt করবে?" এটা undecidable। Intuition proof (contradiction দিয়ে):

ধরুন H(P, x) নামে একটা program আছে যা সবসময় সঠিকভাবে "halts" বা "loops" বলে।
একটা দুষ্টু program D(P) বানান: এটা H(P, P) চালায়। H যদি বলে "P নিজের উপর halt করে", তাহলে D ইচ্ছা করে চিরকাল loop করে। H যদি বলে "loops", তাহলে D halt করে।
এবার প্রশ্ন: D(D) কী করে? D(D) halt করলে H বলেছিল "loops" — কিন্তু H সঠিক হওয়ার কথা, contradiction। D(D) loop করলে H বলেছিল "halts" — আবারো contradiction।
দুই case-ই অসম্ভব → H থাকতে পারে না। HALT undecidable।

এটা "this sentence is false"-এর মতোই self-reference-এর কৌশল। আরো অনেক প্রশ্ন HALT-এ reduce হয় এবং undecidable: "এই program কি কখনো X print করবে?", "এই দুই program কি equivalent?", "এই CFG কি ambiguous?"।

Closure properties summaryClosure properties summary

OperationOperation	Regular	CFL	DecidableDecidable
Union	✓	✓	✓
Concatenation	✓	✓	✓
Kleene star	✓	✓	✓
Intersection	✓	✗	✓
Complement	✓	✗	✓
Intersection with a regular languageRegular language-এর সাথে intersection	✓	✓	✓

Note:

CFLs are NOT closed under intersection or complement — a favorite MCQ. Classic counterexample: $\{a^nb^nc^m\} \cap \{a^mb^nc^n\} = \{a^nb^nc^n\}$, which is not context-free even though both pieces are.

CFL, intersection বা complement-এর under-এ closed না — MCQ-এর প্রিয় প্রশ্ন। Classic counterexample: $\{a^nb^nc^m\} \cap \{a^mb^nc^n\} = \{a^nb^nc^n\}$ — দুই টুকরাই context-free হলেও ফলাফলটা context-free না।

5. Lexical Analysis and Parsing5. Lexical Analysis আর Parsing

The phases of a compilerCompiler-এর phase গুলো

A compiler translates source code into target code (like machine code) in stages. Each stage does one clear job and passes its result to the next. The first three phases "analyze" (front end); the last three "synthesize" (back end). The symbol table and the error handler talk to every phase.

Compiler ধাপে ধাপে source code-কে target code-এ (যেমন machine code) translate করে। প্রতিটা ধাপ একটা পরিষ্কার কাজ করে আর result পরের ধাপে পাঠায়। প্রথম তিন phase "analyze" করে (front end); শেষ তিনটা "synthesize" করে (back end)। Symbol table আর error handler প্রতিটা phase-এর সাথে কথা বলে।

The six phases of a compiler. The symbol table and error handler serve every phase. Compiler-এর ছয়টা phase। Symbol table আর error handler প্রতিটা phase-কে service দেয়।

Tokens, lexemes, patternsToken, lexeme, pattern

The lexical analyzer (scanner/lexer) reads raw characters and groups them into tokens. Three words to keep straight:

Lexeme: the actual text in the source, like count or 42.
Token: the category (with optional value), like <id, count> or <number, 42>.
Pattern: the rule that decides the category — usually a regular expression! Example: an identifier matches [a-zA-Z_][a-zA-Z0-9_]*. This is why regex and DFA matter to compilers: lexers are built from them.

Lexical analyzer (scanner/lexer) কাঁচা character পড়ে সেগুলোকে token-এ group করে। তিনটা শব্দ পরিষ্কার রাখুন:

Lexeme: source-এর আসল text, যেমন count বা 42।
Token: category (সাথে value থাকতে পারে), যেমন <id, count> বা <number, 42>।
Pattern: যে rule category ঠিক করে — সাধারণত একটা regular expression! যেমন: identifier match করে [a-zA-Z_][a-zA-Z0-9_]*। এজন্যই regex আর DFA compiler-এ এত জরুরি: lexer এগুলো দিয়েই বানানো হয়।

Example:

Tokenize total = price * 5;

<id, total>  <assign, =>  <id, price>  <op, *>  <number, 5>  <semi, ;>

Whitespace and comments are thrown away here. The symbol table now stores an entry for total and price: name, type, scope, memory location. Later phases look identifiers up in this table.

total = price * 5; tokenize করুন

<id, total>  <assign, =>  <id, price>  <op, *>  <number, 5>  <semi, ;>

Whitespace আর comment এখানেই ফেলে দেওয়া হয়। Symbol table-এ এখন total আর price-এর entry থাকে: name, type, scope, memory location। পরের phase গুলো identifier এই table-এ খোঁজে।

Top-down vs bottom-up parsingTop-down বনাম bottom-up parsing

	Top-downTop-down	Bottom-upBottom-up
Directionদিক	Start symbol → string (root to leaves)Start symbol → string (root থেকে leaf)	String → start symbol (leaves to root)String → start symbol (leaf থেকে root)
Main moveমূল move	Expand (derive): pick a productionExpand (derive): একটা production বাছুন	Shift and reduce: replace a handle by its variableShift আর reduce: handle-কে তার variable দিয়ে বদলান
Derivation builtযে derivation বানায়	LeftmostLeftmost	Rightmost, in reverseRightmost, উল্টো করে
Common parsersপরিচিত parser	LL(1), recursive descent	LR(0), SLR, LALR, LR(1) — used by yacc/bisonyacc/bison ব্যবহার করে
Cannot handleযা পারে না	Left recursion, common prefixesLeft recursion, common prefix	(More powerful; handles more grammars)(বেশি শক্তিশালী; বেশি grammar পারে)

Parser comparison: LL(1) vs SLR vs LALR vs CLRParser তুলনা: LL(1) বনাম SLR বনাম LALR বনাম CLR

Exams love ranking the table-driven parsers by two things: power (how many grammars they can handle) and table size. Memorize the power order:

পরীক্ষায় table-driven parser গুলোকে দুইটা জিনিস দিয়ে rank করতে বলা হয়: power (কতগুলো grammar সামলাতে পারে) আর table size। Power-এর order-টা মুখস্থ রাখুন:

\[ \text{LL(1)} < \text{SLR} < \text{LALR} < \text{CLR (LR(1))} \]

Parser	Typeধরন	Power (grammars handled)Power (কত grammar পারে)	Table sizeTable size
LL(1)	Top-downTop-down	Weakest — no left recursion, no common prefixesসবচেয়ে দুর্বল — left recursion বা common prefix চলে না	Smallest (nonterminals × terminals)সবচেয়ে ছোট (nonterminal × terminal)
SLR	Bottom-upBottom-up	Weakest LR — uses FOLLOW sets to decide reduces, so some conflicts remainসবচেয়ে দুর্বল LR — reduce ঠিক করতে FOLLOW set ব্যবহার করে, তাই কিছু conflict থেকে যায়	Small — built on LR(0) statesছোট — LR(0) state-এর উপর বানানো
LALR	Bottom-upBottom-up	Middle — CLR states with same core merged; rarely adds reduce-reduce conflictsমাঝামাঝি — একই core-এর CLR state merge করা; কালেভদ্রে reduce-reduce conflict আসে	Same number of states as SLR — used by yacc/bisonSLR-এর সমান সংখ্যক state — yacc/bison এটাই ব্যবহার করে
CLR (LR(1))	Bottom-upBottom-up	Most powerful — full one-token lookahead in every stateসবচেয়ে শক্তিশালী — প্রতিটা state-এ full এক-token lookahead	Largest — states multiply because of lookaheadsসবচেয়ে বড় — lookahead-এর কারণে state অনেক বেড়ে যায়

Note: two facts answer most MCQs here. (1) Power: LL(1) < SLR < LALR < CLR. (2) Table size: SLR = LALR (same states) < CLR. LALR is the practical sweet spot — almost CLR power at SLR size.

Note: এখানকার বেশিরভাগ MCQ দুইটা fact দিয়েই মেলে। (1) Power: LL(1) < SLR < LALR < CLR। (2) Table size: SLR = LALR (একই state) < CLR। LALR-ই practical sweet spot — SLR-এর size-এ প্রায় CLR-এর power।

FIRST and FOLLOW (with example)FIRST আর FOLLOW (উদাহরণসহ)

An LL(1) parser looks at ONE next token and must pick the right production. Two helper sets make that possible:

FIRST(X): the set of terminals that can begin a string derived from X (plus $\varepsilon$ if X can vanish).
FOLLOW(A): the set of terminals that can appear immediately AFTER A in some derivation. $ (end marker) is in FOLLOW of the start symbol.

Take the standard expression grammar (already left-recursion-free):

একটা LL(1) parser পরের মাত্র একটা token দেখে সঠিক production বাছে। দুইটা helper set এটা সম্ভব করে:

FIRST(X): X থেকে derive হওয়া string যেসব terminal দিয়ে শুরু হতে পারে, তাদের set (X হাওয়া হয়ে যেতে পারলে $\varepsilon$-ও)।
FOLLOW(A): কোনো derivation-এ A-এর ঠিক পরে যেসব terminal আসতে পারে, তাদের set। Start symbol-এর FOLLOW-তে $ (end marker) থাকে।

Standard expression grammar-টা নিন (এতে left recursion আগেই সরানো):

E  → T E'
E' → + T E' | ε
T  → F T'
T' → * F T' | ε
F  → ( E ) | id

	FIRST	FOLLOW
E	{ (, id }	{ ), $ }
E'	{ +, ε }	{ ), $ }
T	{ (, id }	{ +, ), $ }
T'	{ *, ε }	{ +, ), $ }
F	{ (, id }	{ *, +, ), $ }

Example:

How to read one row: FIRST(E) = FIRST(T) = FIRST(F) = { (, id } because E ⇒ T E' ⇒ F T' E' — everything starts at F, and F starts with ( or id. FOLLOW(T) = { +, ), $ }: after T comes E', and E' can start with +; E' can also vanish (ε), so whatever follows E — that is ) or $ — can also follow T. The parser uses these sets: seeing token + while expanding E', it picks E' → + T E'; seeing ) or $ (they are in FOLLOW(E')), it picks E' → ε.

একটা row কীভাবে পড়বেন: FIRST(E) = FIRST(T) = FIRST(F) = { (, id } কারণ E ⇒ T E' ⇒ F T' E' — সবকিছু F থেকে শুরু, আর F শুরু হয় ( বা id দিয়ে। FOLLOW(T) = { +, ), $ }: T-এর পরে আসে E', আর E' শুরু হতে পারে + দিয়ে; E' হাওয়াও (ε) হতে পারে, তাই E-এর পরে যা আসে — মানে ) বা $ — তাও T-এর পরে আসতে পারে। Parser এই set গুলো ব্যবহার করে: E' expand করার সময় token + দেখলে E' → + T E' বাছে; ) বা $ দেখলে (এরা FOLLOW(E')-তে আছে) E' → ε বাছে।

Building the LL(1) parsing table: full worked exampleLL(1) parsing table বানানো: full worked example

Exams ask this as one complete flow: grammar → FIRST → FOLLOW → table → parse a string. Let us do all of it on a small grammar:

Exam-এ এটা একটা complete flow হিসেবে আসে: grammar → FIRST → FOLLOW → table → একটা string parse। ছোট একটা grammar-এ পুরোটা করি:

E  → T E'
E' → + T E' | ε
T  → id | ( E )

Step 1 — FIRST sets. Ask: "which terminals can a string from this variable START with?"

Step 1 — FIRST sets। প্রশ্ন করুন: "এই variable থেকে আসা string কোন কোন terminal দিয়ে START হতে পারে?"

	FIRST	Whyকেন
T	{ id, ( }	T → id starts with id; T → ( E ) starts with (T → id শুরু হয় id দিয়ে; T → ( E ) শুরু হয় ( দিয়ে
E	{ id, ( }	E → T E' — E starts wherever T startsE → T E' — T যেখানে শুরু, E-ও সেখানে
E'	{ +, ε }	E' → + T E' starts with +; E' → ε means it can vanishE' → + T E' শুরু হয় + দিয়ে; E' → ε মানে এটা হাওয়া হতে পারে

Step 2 — FOLLOW sets. Ask: "which terminals can appear right AFTER this variable?" Start symbol always gets $.

Step 2 — FOLLOW sets। প্রশ্ন করুন: "এই variable-এর ঠিক PORE কোন কোন terminal আসতে পারে?" Start symbol সবসময় $ পায়।

	FOLLOW	Whyকেন
E	{ ), $ }	$ because E is the start symbol; ) because T → ( E ) puts a ) right after E$ কারণ E start symbol; ) কারণ T → ( E )-তে E-এর ঠিক পরে ) আছে
E'	{ ), $ }	E' sits at the END of E → T E', so FOLLOW(E') = FOLLOW(E)E' আছে E → T E'-এর একদম শেষে, তাই FOLLOW(E') = FOLLOW(E)
T	{ +, ), $ }	after T comes E'; E' can start with + — and E' can vanish (ε), so FOLLOW(E') = { ), $ } also follows TT-এর পরে E'; E' শুরু হতে পারে + দিয়ে — আর E' হাওয়াও (ε) হতে পারে, তাই FOLLOW(E') = { ), $ }-ও T-এর পরে আসে

Step 3 — fill the parsing table. Two simple rules for each production A → α:

For every terminal $a$ in FIRST(α): put "A → α" in cell M[A, a].
If ε is in FIRST(α): put "A → α" in M[A, b] for every $b$ in FOLLOW(A).

Step 3 — parsing table পূরণ করুন। প্রতিটা production A → α-এর জন্য দুইটা সহজ নিয়ম:

FIRST(α)-এর প্রতিটা terminal $a$-এর জন্য: cell M[A, a]-তে "A → α" বসান।
FIRST(α)-তে ε থাকলে: FOLLOW(A)-এর প্রতিটা $b$-এর জন্য M[A, b]-তে "A → α" বসান।

M	id	+	(	)	$
E	E → T E'		E → T E'
E'		E' → + T E'		E' → ε	E' → ε
T	T → id		T → ( E )

Where did each entry come from? E → T E' goes under id and ( because FIRST(T E') = { id, ( }. E' → + T E' goes under + only. E' → ε goes under ) and $ because FOLLOW(E') = { ), $ }. T → id under id; T → ( E ) under (. No cell has two entries → the grammar IS LL(1). (A conflict in any cell would mean: not LL(1).)

প্রতিটা entry কোথা থেকে এলো? E → T E' বসেছে id আর (-এর নিচে, কারণ FIRST(T E') = { id, ( }। E' → + T E' শুধু +-এর নিচে। E' → ε বসেছে ) আর $-এর নিচে, কারণ FOLLOW(E') = { ), $ }। T → id বসেছে id-এর নিচে; T → ( E ) বসেছে (-এর নিচে। কোনো cell-এ দুইটা entry নেই → grammar-টা LL(1)। (কোনো cell-এ conflict থাকলে বুঝতেন: LL(1) না।)

Example — parsing id + id with the table (stack trace):

Push $ then the start symbol E. At each step: if the stack top is a variable, look up M[top, current token] and replace the top by that production's right side (reversed, so the left end is on top). If the top is a terminal, it must MATCH the current token — pop and advance.

প্রথমে $ push করুন, তারপর start symbol E। প্রতি step-এ: stack-এর top একটা variable হলে M[top, current token] দেখুন আর top-কে সেই production-এর ডান পাশ দিয়ে বদলান (উল্টো করে, যাতে বাম প্রান্ত top-এ থাকে)। Top একটা terminal হলে সেটা current token-এর সাথে MATCH করতেই হবে — pop করুন আর এগোন।

Stack (top on right)Stack (ডানে top)	Input	Action
$ E	id + id $	M[E, id] = E → T E'
$ E' T	id + id $	M[T, id] = T → id
$ E' id	id + id $	match idid match
$ E'	+ id $	M[E', +] = E' → + T E'
$ E' T +	+ id $	match ++ match
$ E' T	id $	M[T, id] = T → id
$ E' id	id $	match idid match
$ E'	$	M[E', $] = E' → ε
$	$	accept — stack and input both emptyaccept — stack আর input দুটোই খালি

Note — asked April 2024:

BUET (April 2024) asked exactly this chain: given a grammar, generate strings from it AND construct its parsing table. Practice the full pipeline until it is automatic: FIRST → FOLLOW → table (two placement rules) → stack trace. Most marks are lost in FOLLOW — remember: "E' can vanish" is what pushes FOLLOW(E) into FOLLOW(T).

BUET (April 2024) ঠিক এই chain-টাই জিজ্ঞেস করেছিল: একটা grammar দিয়ে তার থেকে string generate করা AND তার parsing table বানানো। পুরো pipeline-টা automatic না হওয়া পর্যন্ত practice করুন: FIRST → FOLLOW → table (দুইটা placement rule) → stack trace। বেশির ভাগ নম্বর কাটা যায় FOLLOW-তে — মনে রাখুন: "E' হাওয়া হতে পারে" — এই কারণেই FOLLOW(E), FOLLOW(T)-এর ভেতরে ঢোকে।

Left recursion removalLeft recursion সরানো

A rule like $A \to A\alpha$ is left recursive. A top-down parser expanding A would call A again immediately — infinite loop. The standard fix:

\[ A \to A\alpha \mid \beta \quad\Longrightarrow\quad A \to \beta A' ,\qquad A' \to \alpha A' \mid \varepsilon \]

Meaning: A really produces one $\beta$ followed by many $\alpha$'s — so write it that way, looping on the right instead of the left.

$A \to A\alpha$-এর মতো rule হলো left recursive। Top-down parser, A expand করতে গিয়ে সাথে সাথে আবার A call করবে — infinite loop। Standard সমাধান:

\[ A \to A\alpha \mid \beta \quad\Longrightarrow\quad A \to \beta A' ,\qquad A' \to \alpha A' \mid \varepsilon \]

মানে: A আসলে একটা $\beta$-এর পরে অনেকগুলো $\alpha$ বানায় — তাহলে সেভাবেই লিখুন, বামের বদলে ডানে loop করে।

Example:

Remove left recursion from E → E + T | T. Here $\alpha = {+T}$ and $\beta = T$. Result:

E  → T E'
E' → + T E' | ε

That is exactly where the grammar in the FIRST/FOLLOW example came from. Same for T → T * F | F giving T → F T', T' → * F T' | ε.

E → E + T | T থেকে left recursion সরান। এখানে $\alpha = {+T}$ আর $\beta = T$। ফলাফল:

E  → T E'
E' → + T E' | ε

FIRST/FOLLOW উদাহরণের grammar-টা ঠিক এখান থেকেই এসেছে। একইভাবে T → T * F | F থেকে পাই T → F T', T' → * F T' | ε।

Note — asked April 2019:

BUET (April 2019) asked exactly this: eliminate left recursion from a given grammar. The general recipe when there are MANY alternatives:

\[ A \to A\alpha_1 \mid \cdots \mid A\alpha_m \mid \beta_1 \mid \cdots \mid \beta_n \;\Longrightarrow\; A \to \beta_1 A' \mid \cdots \mid \beta_n A', \quad A' \to \alpha_1 A' \mid \cdots \mid \alpha_m A' \mid \varepsilon \]

Exam routine: (1) sort each alternative into "starts with A" (its tail is an $\alpha$) or "does not" (a $\beta$); (2) write the two new rules; (3) sanity-check by deriving one small string in both grammars. See Q14 below for a full worked answer in this exact style.

BUET (April 2019) ঠিক এটাই জিজ্ঞেস করেছিল: একটা দেওয়া grammar থেকে left recursion eliminate করুন। অনেকগুলো alternative থাকলে general recipe:

Exam-এর routine: (1) প্রতিটা alternative ভাগ করুন — "A দিয়ে শুরু" (তার লেজটা একটা $\alpha$) নাকি "না" (একটা $\beta$); (2) নতুন দুইটা rule লিখুন; (3) দুই grammar-এই একটা ছোট string derive করে sanity-check করুন। ঠিক এই style-এর full worked answer-এর জন্য নিচের Q14 দেখুন।

Left factoringLeft factoring

If two productions share a common prefix, an LL(1) parser cannot choose between them by one lookahead token. Left factoring pulls the common part out:

\[ A \to \alpha\beta_1 \mid \alpha\beta_2 \quad\Longrightarrow\quad A \to \alpha A' ,\qquad A' \to \beta_1 \mid \beta_2 \]

দুইটা production-এর শুরুতে common prefix থাকলে, LL(1) parser এক token দেখে তাদের মধ্যে বাছতে পারে না। Left factoring common অংশটা বাইরে টেনে আনে:

\[ A \to \alpha\beta_1 \mid \alpha\beta_2 \quad\Longrightarrow\quad A \to \alpha A' ,\qquad A' \to \beta_1 \mid \beta_2 \]

Example:

stmt → if expr then stmt else stmt
     | if expr then stmt

Both start with if expr then stmt. After factoring:

stmt  → if expr then stmt rest
rest  → else stmt | ε

stmt → if expr then stmt else stmt
     | if expr then stmt

দুটোই শুরু হয় if expr then stmt দিয়ে। Factoring-এর পরে:

stmt  → if expr then stmt rest
rest  → else stmt | ε

Note:

Remember the pairing: left recursion removal fixes "parser loops forever"; left factoring fixes "parser cannot decide". Both are preprocessing steps needed before building an LL(1) parser. Bottom-up (LR) parsers do not need either.

জোড়াটা মনে রাখুন: left recursion removal ঠিক করে "parser চিরকাল loop করে" সমস্যা; left factoring ঠিক করে "parser সিদ্ধান্ত নিতে পারে না" সমস্যা। LL(1) parser বানানোর আগে দুটোই preprocessing step। Bottom-up (LR) parser-এর কোনোটাই লাগে না।

6. Syntax and Semantic Analysis6. Syntax আর Semantic Analysis

What each phase checksকোন phase কী check করে

PhasePhase	Question it answersযে প্রশ্নের উত্তর দেয়	Catches errors likeযেমন error ধরে
Lexical	"Are these valid words?""এগুলো কি বৈধ শব্দ?"	`int 9x = 5;` (bad identifier)(ভুল identifier)
Syntax	"Is the sentence structure valid (grammar)?""বাক্যের গঠন কি বৈধ (grammar)?"	`x = 5 + ;` (missing operand)(operand নেই)
Semantic	"Does it make sense (meaning)?""অর্থ কি ঠিক আছে?"	`x = "hi" * 3.5;` (type mismatch), undeclared variable, wrong argument count(type mismatch), undeclared variable, ভুল সংখ্যক argument

Syntax-directed translation (SDT)Syntax-directed translation (SDT)

Idea: attach small actions (semantic rules) to grammar productions. As the parser builds the tree, the actions compute values or generate code. Each grammar symbol carries attributes (like val or type).

Idea: grammar-এর production-এর সাথে ছোট ছোট action (semantic rule) জুড়ে দিন। Parser tree বানানোর সময় action গুলো value হিসাব করে বা code generate করে। প্রতিটা grammar symbol কিছু attribute বহন করে (যেমন val বা type)।

Example:

A tiny calculator by SDT:

E → E1 + T    { E.val = E1.val + T.val }
E → T         { E.val = T.val }
T → T1 * F    { T.val = T1.val * F.val }
T → F         { T.val = F.val }
F → num       { F.val = num.value }

Parsing 2 + 3 * 4 computes bottom-up: F.val=3, F.val=4 → T.val=12 → E.val = 2 + 12 = 14. The grammar's precedence layers make * happen first automatically.

SDT দিয়ে ছোট্ট একটা calculator:

E → E1 + T    { E.val = E1.val + T.val }
E → T         { E.val = T.val }
T → T1 * F    { T.val = T1.val * F.val }
T → F         { T.val = F.val }
F → num       { F.val = num.value }

2 + 3 * 4 parse করলে হিসাব হয় নিচ থেকে উপরে: F.val=3, F.val=4 → T.val=12 → E.val = 2 + 12 = 14। Grammar-এর precedence স্তরের কারণে * নিজে থেকেই আগে হয়।

Type checkingType checking

The semantic analyzer walks the tree and checks types using the symbol table. Common jobs: every variable is declared before use; operator operands have compatible types; function calls match the declared signature. Sometimes it inserts automatic conversions (coercion): in 2 + 3.5, the int 2 is converted to float 2.0 first (an inttofloat node is added).

Semantic analyzer, symbol table ব্যবহার করে tree ঘুরে ঘুরে type check করে। সাধারণ কাজ: প্রতিটা variable ব্যবহারের আগে declared কি না; operator-এর operand-দের type মেলে কি না; function call declared signature-এর সাথে মেলে কি না। কখনো এটা automatic conversion (coercion) বসায়: 2 + 3.5-এ আগে int 2-কে float 2.0 বানানো হয় (একটা inttofloat node যোগ হয়)।

Intermediate code: three-address code (TAC)Intermediate code: three-address code (TAC)

Three-address code is a simple middle form between source and machine code. Each instruction has at most one operator and at most three "addresses" (two operands, one result). Temporaries $t_1, t_2, \ldots$ hold in-between values.

Three-address code হলো source আর machine code-এর মাঝের একটা সহজ রূপ। প্রতিটা instruction-এ সর্বোচ্চ একটা operator আর সর্বোচ্চ তিনটা "address" থাকে (দুইটা operand, একটা result)। মাঝের value গুলো temporary $t_1, t_2, \ldots$-তে রাখা হয়।

Example — asked April 2017: why do we need an intermediate code generator?

BUET asked exactly this. The three-point answer:

Portability (the big one): the intermediate representation (IR) sits between the front end (language-specific) and the back end (machine-specific). With $m$ source languages and $n$ target machines, direct translation needs $m \times n$ compilers. With one common IR, you need only $m$ front ends + $n$ back ends — $m + n$ pieces. Example: 3 languages, 4 machines → 12 compilers become 7 pieces.
Optimization: the IR is machine-independent, so one optimizer (constant folding, dead code elimination, etc.) can be written ONCE and reused for every language and every machine.
Simplicity: translating source → simple TAC, and TAC → machine code, are each much easier than one giant source → machine jump. Retargeting to a new CPU means writing only a new back end.

BUET ঠিক এটাই জিজ্ঞেস করেছিল। তিন-point উত্তর:

Portability (সবচেয়ে বড়টা): intermediate representation (IR) থাকে front end (language-specific) আর back end (machine-specific)-এর মাঝে। $m$টা source language আর $n$টা target machine হলে সরাসরি translate করতে $m \times n$টা compiler লাগে। একটা common IR থাকলে লাগে শুধু $m$টা front end + $n$টা back end — মোট $m + n$টা অংশ। উদাহরণ: 3টা language, 4টা machine → 12টা compiler-এর বদলে 7টা অংশ।
Optimization: IR machine-independent, তাই একটা optimizer (constant folding, dead code elimination ইত্যাদি) একবারই লিখে প্রতিটা language আর প্রতিটা machine-এ reuse করা যায়।
Simplicity: source → সহজ TAC, আর TAC → machine code — এই দুই ধাপ আলাদাভাবে অনেক সহজ, এক লাফে source → machine-এর চেয়ে। নতুন CPU-তে retarget করতে শুধু নতুন একটা back end লিখলেই হয়।

Example:

Source: a = b + c * d - b. TAC (respecting precedence):

t1 = c * d
t2 = b + t1
t3 = t2 - b
a  = t3

Another: if (x < 10) y = 0; becomes:

t1 = x < 10
ifFalse t1 goto L1
y = 0
L1: ...

Source: a = b + c * d - b। TAC (precedence মেনে):

t1 = c * d
t2 = b + t1
t3 = t2 - b
a  = t3

আরেকটা: if (x < 10) y = 0; হয়ে যায়:

t1 = x < 10
ifFalse t1 goto L1
y = 0
L1: ...

Quadruples vs Triples — asked October 2017Quadruples বনাম Triples — asked October 2017

TAC has to be stored in some data structure inside the compiler. BUET asked (October 2017) to show and compare the two classic forms. A quadruple has four fields: (op, arg1, arg2, result) — the result is a named temporary. A triple has only three fields: (op, arg1, arg2) — there is NO result field; a later instruction refers to an earlier result by its position number, like (0).

Compiler-এর ভেতরে TAC কোনো একটা data structure-এ রাখতে হয়। BUET (October 2017) দুইটা classic রূপ দেখাতে আর তুলনা করতে বলেছিল। Quadruple-এ চারটা field: (op, arg1, arg2, result) — result হলো নাম দেওয়া একটা temporary। Triple-এ মাত্র তিনটা field: (op, arg1, arg2) — কোনো result field নেই; পরের instruction আগের result-কে তার position number দিয়ে refer করে, যেমন (0)।

Example — a = b * c + d:

First write the TAC (precedence: * before +):

t1 = b * c
t2 = t1 + d
a  = t2

As quadruples — every instruction names its result:

আগে TAC লিখি (precedence: +-এর আগে *):

t1 = b * c
t2 = t1 + d
a  = t2

Quadruple হিসেবে — প্রতিটা instruction তার result-এর নাম দেয়:

#	op	arg1	arg2	result
(0)	*	b	c	t1
(1)	+	t1	d	t2
(2)	=	t2		a

As triples — no result column; (0) and (1) are position references:

Triple হিসেবে — result column নেই; (0) আর (1) হলো position reference:

#	op	arg1	arg2
(0)	*	b	c
(1)	+	(0)	d
(2)	=	a	(1)

	Quadruples	Triples
FieldsField	4: op, arg1, arg2, result4টা: op, arg1, arg2, result	3: op, arg1, arg2 (result = the row's own position)3টা: op, arg1, arg2 (result = row-এর নিজের position)
SpaceSpace	More — stores temporary namesবেশি — temporary-র নাম রাখতে হয়	Less — compact, no temp namesকম — compact, temp-এর নাম লাগে না
Moving instructions (optimization)Instruction সরানো (optimization)	Easy — named temps stay valid after reordering, so code motion worksসহজ — reorder করলেও নাম দেওয়া temp ঠিক থাকে, তাই code motion চলে	Hard — reordering changes positions, so every (n) reference breaksকঠিন — reorder করলে position বদলে যায়, তাই প্রতিটা (n) reference ভেঙে যায়

Note: the fix for triples is indirect triples: keep a separate list of pointers to the triples, and reorder the pointer list instead of the triples themselves. References stay valid, and you get back the freedom to optimize. Exam one-liner: quadruples = easy to move, more space; triples = compact, hard to move; indirect triples = compact AND movable.

Note: Triple-এর সমাধান হলো indirect triples: triple গুলোর দিকে pointer-এর আলাদা একটা list রাখুন, আর triple না সরিয়ে pointer list-টা reorder করুন। Reference ঠিক থাকে, আর optimize করার স্বাধীনতাও ফিরে আসে। পরীক্ষার এক লাইনে: quadruple = সরানো সহজ, space বেশি; triple = compact, সরানো কঠিন; indirect triple = compact এবং সরানো যায়।

Code optimization: two quick examplesCode optimization: দুইটা ছোট উদাহরণ

Example — constant folding:

If all operands are known at compile time, compute the result now, not at run time.

Before:  t1 = 60 * 60      After:  t1 = 3600
         area = 2 * 3.1416         area = 6.2832

Related: constant propagation — after x = 5, replace later uses of x with 5, which may enable more folding.

সব operand compile time-এই জানা থাকলে, result এখনই হিসাব করুন, run time-এ না।

আগে:   t1 = 60 * 60      পরে:   t1 = 3600
       area = 2 * 3.1416        area = 6.2832

সম্পর্কিত: constant propagation — x = 5-এর পরে, পরের x-এর ব্যবহারগুলো 5 দিয়ে বদলান; তাতে আরো folding সম্ভব হতে পারে।

Example — dead code elimination:

Remove code whose result is never used or that can never run.

Before:                     After:
x = 10                      return y * 2
x = 20        // first x=10 is dead
if (false) { print(x) }     // unreachable — dead
return y * 2                // x never used at all

Other classics worth naming in an exam: common subexpression elimination, loop-invariant code motion, strength reduction (x*2 → x+x or a shift).

যে code-এর result কখনো ব্যবহার হয় না বা যা কখনো চলবেই না — বাদ দিন।

আগে:                        পরে:
x = 10                      return y * 2
x = 20        // প্রথম x=10 dead
if (false) { print(x) }     // unreachable — dead
return y * 2                // x আসলে ব্যবহারই হয়নি

Exam-এ নাম বলার মতো আরো classic: common subexpression elimination, loop-invariant code motion, strength reduction (x*2 → x+x বা একটা shift)।

Note:

Map the theory to the compiler in your head: regex/DFA → lexical analysis; CFG/parse trees → syntax analysis; attributes/SDT → semantic analysis and code generation. Exams love the question "which phase uses a finite automaton?" (lexical) and "which phase uses a CFG?" (syntax/parser).

Theory-টা মাথায় compiler-এর সাথে map করুন: regex/DFA → lexical analysis; CFG/parse tree → syntax analysis; attribute/SDT → semantic analysis আর code generation। Exam-এ প্রিয় প্রশ্ন: "কোন phase finite automaton ব্যবহার করে?" (lexical) আর "কোন phase CFG ব্যবহার করে?" (syntax/parser)।

Practice Questions (Admission Style)Practice Questions (Admission Style)

Q1. Which string belongs to the language of the regex $(0+1)^*01$?

(a) 010
(b) 110
(c) 1101
(d) 100

Q1. কোন string-টা regex $(0+1)^*01$-এর language-এ আছে?

(a) 010
(b) 110
(c) 1101
(d) 100

Show Answerউত্তর দেখুন

Answer: (c) — the regex means "anything, then 01 at the end". Only 1101 ends in 01. 010 ends in 10, 110 ends in 10, 100 ends in 00.

Answer: (c) — regex-টার মানে "যেকোনো কিছু, শেষে 01"। শুধু 1101-ই 01 দিয়ে শেষ। 010 শেষ হয় 10 দিয়ে, 110 শেষ হয় 10 দিয়ে, 100 শেষ হয় 00 দিয়ে।

Q2. The language of the regex $0^*$ is:

(a) all strings with at least one 0
(b) all strings with no 1, including $\varepsilon$
(c) only the string 0
(d) all binary strings

Q2. Regex $0^*$-এর language কোনটা?

(a) কমপক্ষে একটা 0 থাকা সব string
(b) কোনো 1 না থাকা সব string, $\varepsilon$ সহ
(c) শুধু 0 string-টা
(d) সব binary string

Show Answerউত্তর দেখুন

Answer: (b) — star means "zero or more 0s": $\{\varepsilon, 0, 00, 000, \ldots\}$. "Zero copies" gives $\varepsilon$, so (a) and (c) are wrong; there is no 1 anywhere, so (d) is wrong.

Answer: (b) — star মানে "শূন্য বা তার বেশি 0": $\{\varepsilon, 0, 00, 000, \ldots\}$। "শূন্যটা copy" মানেই $\varepsilon$, তাই (a) আর (c) ভুল; কোথাও 1 নেই, তাই (d)-ও ভুল।

Q3. The minimal DFA for "binary strings ending in 01" has how many states?

(a) 2
(b) 3
(c) 4
(d) 5

Q3. "01 দিয়ে শেষ হওয়া binary string"-এর minimal DFA-তে কয়টা state?

(a) 2
(b) 3
(c) 4
(d) 5

Show Answerউত্তর দেখুন

Answer: (b) — the machine must remember progress toward 01: "no progress" (A), "just saw 0" (B), "just saw 01" (C). These three are pairwise distinguishable (e.g., $\varepsilon$ separates C from A and B; the string 1 separates A from B), so none can merge — 3 is minimal.

Answer: (b) — machine-কে 01-এর দিকে progress মনে রাখতে হবে: "progress নেই" (A), "এইমাত্র 0 দেখলাম" (B), "এইমাত্র 01 দেখলাম" (C)। তিনটাই একে অন্যের থেকে আলাদা করা যায় (যেমন $\varepsilon$ দিয়ে C-কে A আর B থেকে আলাদা করা যায়; 1 string দিয়ে A আর B আলাদা হয়), তাই কোনোটা merge হয় না — 3-ই minimal।

Q4. Which language is NOT regular?

(a) strings ending in 11
(b) strings of even length
(c) $\{a^n b^n \mid n \ge 0\}$
(d) strings containing 101

Q4. কোন language-টা regular না?

(a) 11 দিয়ে শেষ হওয়া string
(b) even length-এর string
(c) $\{a^n b^n \mid n \ge 0\}$
(d) 101 substring থাকা string

Show Answerউত্তর দেখুন

Answer: (c) — (a), (b), (d) only need a finite pattern memory, so small DFAs exist for them. $a^nb^n$ needs to COUNT an unbounded $n$ and match it — finite states cannot do that (pumping lemma: pumping the loop inside the a-part breaks the balance).

Answer: (c) — (a), (b), (d)-এর জন্য শুধু finite pattern-এর memory লাগে, তাই ছোট DFA-ই যথেষ্ট। $a^nb^n$-এর জন্য unbounded $n$ গুনে মেলাতে হয় — finite state তা পারে না (pumping lemma: a-অংশের loop pump করলে balance ভেঙে যায়)।

Q5. (Written) Design a DFA for binary strings with an EVEN number of 1s. Give the 5-tuple parts and the transition table.

Q5. (Written) EVEN সংখ্যক 1 থাকা binary string-এর জন্য একটা DFA design করুন। 5-tuple-এর অংশগুলো আর transition table দিন।

Show Answerউত্তর দেখুন

Answer: Two states are enough — the machine only needs the parity of 1s seen so far.

$Q = \{E, O\}$, $\Sigma = \{0,1\}$, start $q_0 = E$, accept $F = \{E\}$ (zero 1s is even, so $\varepsilon$ must be accepted).

δ	on 0	on 1
→ * E (even)	E	O
O (odd)	O	E

Reasoning: a 0 never changes the count of 1s (self-loop); a 1 flips the parity E↔O. Check with 1011 (three 1s, odd): E→O→O→E→O — ends in O, rejected. Correct.

Answer: দুইটা state-ই যথেষ্ট — machine-কে শুধু এখন পর্যন্ত দেখা 1-এর parity মনে রাখতে হবে।

$Q = \{E, O\}$, $\Sigma = \{0,1\}$, start $q_0 = E$, accept $F = \{E\}$ (শূন্যটা 1 মানে even, তাই $\varepsilon$ accept হতে হবে)।

δ	0 পড়লে	1 পড়লে
→ * E (even)	E	O
O (odd)	O	E

যুক্তি: 0 পড়লে 1-এর count বদলায় না (self-loop); 1 পড়লে parity E↔O উল্টে যায়। 1011 (তিনটা 1, odd) দিয়ে check করুন: E→O→O→E→O — শেষে O, rejected। ঠিক আছে।

Q6. (Written) Write regular expressions over $\Sigma=\{0,1\}$ for: (i) strings containing the substring 11; (ii) strings of odd length.

Q6. (Written) $\Sigma=\{0,1\}$-এর উপর regular expression লিখুন: (i) 11 substring থাকা string; (ii) odd length-এর string।

Show Answerউত্তর দেখুন

Answer:

(i) $(0+1)^*\,11\,(0+1)^*$ — anything, then 11 somewhere, then anything. The two 1s must be adjacent, and this regex forces exactly that.

(ii) $(0+1)\big((0+1)(0+1)\big)^*$ — one symbol first (length 1), then pairs of symbols. Length = 1 + 2k, which is exactly the odd numbers.

Answer:

(i) $(0+1)^*\,11\,(0+1)^*$ — যেকোনো কিছু, মাঝে কোথাও 11, তারপর যেকোনো কিছু। 1 দুটো পাশাপাশি থাকতেই হবে, এই regex সেটাই নিশ্চিত করে।

(ii) $(0+1)\big((0+1)(0+1)\big)^*$ — প্রথমে একটা symbol (length 1), তারপর জোড়ায় জোড়ায় symbol। Length = 1 + 2k, মানে ঠিক odd সংখ্যাগুলো।

Q7. An NFA has 4 states. The equivalent DFA (by subset construction) has at most how many states?

(a) 4
(b) 8
(c) 16
(d) 24

Q7. একটা NFA-তে 4টা state আছে। Equivalent DFA-তে (subset construction-এ) সর্বোচ্চ কয়টা state হতে পারে?

(a) 4
(b) 8
(c) 16
(d) 24

Show Answerউত্তর দেখুন

Answer: (c) — each DFA state is a SUBSET of the NFA's states. A 4-element set has $2^4 = 16$ subsets, so at most 16 DFA states. Usually far fewer are reachable (our worked example reached only 3 of 8).

Answer: (c) — DFA-এর প্রতিটা state হলো NFA-এর state-দের একটা SUBSET। 4টা element-এর set-এর $2^4 = 16$টা subset আছে, তাই সর্বোচ্চ 16টা DFA state। সাধারণত এর অনেক কম reachable হয় (আমাদের worked example-এ 8টার মধ্যে মাত্র 3টা)।

Q8. (Written) An NFA for "strings ending in 1": state q0 (start) loops on 0 and 1; on 1 it can also go to q1 (accept). Convert it to a DFA by subset construction.

Q8. (Written) "1 দিয়ে শেষ হওয়া string"-এর একটা NFA: state q0 (start) 0 আর 1-এ নিজের উপর loop করে; 1 পড়লে q1 (accept)-এও যেতে পারে। Subset construction দিয়ে এটাকে DFA বানান।

Show Answerউত্তর দেখুন

Answer: Start from {q0} and follow each symbol:

{q0} on 0 → {q0}; on 1 → q0 can stay or jump to q1 → {q0, q1}
{q0, q1} on 0 → only q0 moves → {q0}; on 1 → {q0, q1}

DFA state	on 0	on 1
→ A = {q0}	A	B
* B = {q0, q1}	A	B

B contains q1, so B is accepting. The result is the natural 2-state DFA: "was the last symbol a 1?" No new subsets appear, so we are done.

Answer: {q0} থেকে শুরু করে প্রতিটা symbol ধরে এগোন:

{q0}-এ 0 পড়লে → {q0}; 1 পড়লে → q0 থাকতেও পারে, q1-এও যেতে পারে → {q0, q1}
{q0, q1}-এ 0 পড়লে → শুধু q0 move করে → {q0}; 1 পড়লে → {q0, q1}

DFA state	0 পড়লে	1 পড়লে
→ A = {q0}	A	B
* B = {q0, q1}	A	B

B-তে q1 আছে, তাই B accept state। ফলাফল হলো স্বাভাবিক 2-state DFA: "শেষ symbol কি 1 ছিল?" নতুন কোনো subset আসেনি, তাই কাজ শেষ।

Q9. (Written) Write a CFG for palindromes over $\{a, b\}$, and show a derivation of the string abba.

Q9. (Written) $\{a, b\}$-এর উপর palindrome-এর একটা CFG লিখুন, আর abba string-এর একটা derivation দেখান।

Show Answerউত্তর দেখুন

Answer:

S → aSa | bSb | a | b | ε

Reasoning: a palindrome reads the same both ways, so its first and last symbols match — peel them off and the middle is again a palindrome. $S \to aSa$ and $S \to bSb$ build matching outer pairs; $a$, $b$, $\varepsilon$ are the smallest palindromes (odd center or empty).

Derivation of abba: $S \Rightarrow aSa \Rightarrow abSba \Rightarrow abba$ (last step uses $S \to \varepsilon$).

Answer:

S → aSa | bSb | a | b | ε

যুক্তি: palindrome দুই দিক থেকে একই — তাই প্রথম আর শেষ symbol মেলে; ওদের খুলে ফেললে মাঝেরটাও আবার palindrome। $S \to aSa$ আর $S \to bSb$ বাইরের matching জোড়া বানায়; $a$, $b$, $\varepsilon$ হলো সবচেয়ে ছোট palindrome (odd center বা empty)।

abba-এর derivation: $S \Rightarrow aSa \Rightarrow abSba \Rightarrow abba$ (শেষ step-এ $S \to \varepsilon$)।

Q10. Which machine exactly recognizes the context-free languages?

(a) DFA
(b) Pushdown Automaton (PDA)
(c) Linear Bounded Automaton
(d) Turing Machine

Q10. কোন machine ঠিক context-free language গুলো recognize করে?

(a) DFA
(b) Pushdown Automaton (PDA)
(c) Linear Bounded Automaton
(d) Turing Machine

Show Answerউত্তর দেখুন

Answer: (b) — Chomsky hierarchy pairing: Regular↔DFA/NFA, Context-free↔PDA, Context-sensitive↔LBA, Recursively enumerable↔TM. A DFA is too weak (no stack for $a^nb^n$); LBA and TM are strictly more powerful, so they recognize more than just CFLs.

Answer: (b) — Chomsky hierarchy-র জোড়া: Regular↔DFA/NFA, Context-free↔PDA, Context-sensitive↔LBA, Recursively enumerable↔TM। DFA খুব দুর্বল ($a^nb^n$-এর জন্য stack নেই); LBA আর TM আরো বেশি শক্তিশালী, তাই তারা CFL-এর চেয়েও বেশি recognize করে।

Q11. Which statement is TRUE?

(a) Every context-free language is regular
(b) Every regular language is context-free
(c) $a^nb^n$ is regular
(d) $a^nb^nc^n$ is context-free

Q11. কোন statement-টা সত্যি?

(a) প্রতিটা context-free language regular
(b) প্রতিটা regular language context-free
(c) $a^nb^n$ regular
(d) $a^nb^nc^n$ context-free

Show Answerউত্তর দেখুন

Answer: (b) — the hierarchy is Regular $\subset$ CFL $\subset$ CSL: the smaller class always sits inside the bigger one. (a) is backwards ($a^nb^n$ is a CFL that is not regular, which also kills (c)). (d) is false: $a^nb^nc^n$ needs two linked comparisons — one stack is not enough; it is context-sensitive.

Answer: (b) — hierarchy হলো Regular $\subset$ CFL $\subset$ CSL: ছোট class সবসময় বড়টার ভেতরে থাকে। (a) উল্টো কথা ($a^nb^n$ একটা CFL যা regular না — এতে (c)-ও ভুল প্রমাণ হয়)। (d) মিথ্যা: $a^nb^nc^n$-এ দুইটা জোড়া লাগানো comparison লাগে — একটা stack যথেষ্ট না; এটা context-sensitive।

Q12. The halting problem is:

(a) decidable
(b) undecidable but recognizable
(c) not even recognizable
(d) context-free

Q12. Halting problem হলো:

(a) decidable
(b) undecidable কিন্তু recognizable
(c) recognizable-ও না
(d) context-free

Show Answerউত্তর দেখুন

Answer: (b) — no TM can always decide "does P halt on x?" (the D(D) diagonalization contradiction). But it IS recognizable: just simulate P on x; if it halts, say yes. The "no" side is the problem — simulation may run forever, so we can never confirm "loops". That is also why the COMPLEMENT of the halting problem is not recognizable.

Answer: (b) — কোনো TM সবসময় "P কি x-এ halt করে?" decide করতে পারে না (D(D) diagonalization-এর contradiction)। কিন্তু এটা recognizable: P-কে x-এর উপর simulate করুন; halt করলে yes বলুন। সমস্যা "no" দিকটায় — simulation চিরকাল চলতে পারে, তাই "loops" কখনো নিশ্চিত করা যায় না। এজন্যই halting problem-এর COMPLEMENT recognizable না।

Q13. (Written) Show that the grammar E → E + E | E * E | id is ambiguous, using the string id + id * id.

Q13. (Written) id + id * id string ব্যবহার করে দেখান যে E → E + E | E * E | id grammar-টা ambiguous।

Show Answerউত্তর দেখুন

Answer: Give two different leftmost derivations (equivalently, two parse trees) for the same string:

Derivation 1 ( + at the root → id + (id*id) ):
E ⇒ E + E ⇒ id + E ⇒ id + E * E ⇒ id + id * E ⇒ id + id * id

Derivation 2 ( * at the root → (id+id) * id ):
E ⇒ E * E ⇒ E + E * E ⇒ id + E * E ⇒ id + id * E ⇒ id + id * id

One string, two distinct leftmost derivations → the grammar is ambiguous by definition. (Fix: layered grammar E → E + T | T, T → T * F | F, F → (E) | id.)

Answer: একই string-এর দুইটা আলাদা leftmost derivation (মানে দুইটা parse tree) দিন:

Derivation 1 ( root-এ + → id + (id*id) ):
E ⇒ E + E ⇒ id + E ⇒ id + E * E ⇒ id + id * E ⇒ id + id * id

Derivation 2 ( root-এ * → (id+id) * id ):
E ⇒ E * E ⇒ E + E * E ⇒ id + E * E ⇒ id + id * E ⇒ id + id * id

একটা string, দুইটা আলাদা leftmost derivation → definition অনুযায়ী grammar-টা ambiguous। (সমাধান: স্তরের grammar E → E + T | T, T → T * F | F, F → (E) | id।)

Q14. (Written) Remove left recursion from: A → Aa | Ab | c

Q14. (Written) এই grammar থেকে left recursion সরান: A → Aa | Ab | c

Show Answerউত্তর দেখুন

Answer: Here the left-recursive parts are $\alpha_1 = a$, $\alpha_2 = b$, and the non-recursive part is $\beta = c$. Apply $A \to \beta A'$, $A' \to \alpha A' \mid \varepsilon$:

A  → c A'
A' → a A' | b A' | ε

Why it is the same language: the old grammar builds strings c, ca, cb, cab, ... — one c followed by any mix of a/b, i.e. $c(a+b)^*$. The new grammar produces exactly that, but grows on the RIGHT, so a top-down parser never loops.

Answer: এখানে left-recursive অংশ $\alpha_1 = a$, $\alpha_2 = b$, আর non-recursive অংশ $\beta = c$। $A \to \beta A'$, $A' \to \alpha A' \mid \varepsilon$ formula লাগান:

A  → c A'
A' → a A' | b A' | ε

কেন একই language: পুরনো grammar বানায় c, ca, cb, cab, ... — একটা c-এর পরে a/b-এর যেকোনো মিশ্রণ, অর্থাৎ $c(a+b)^*$। নতুন grammar ঠিক তা-ই বানায়, কিন্তু ডান দিকে বাড়ে — তাই top-down parser কখনো loop করে না।

Q15. (Written) (i) Write three-address code for: a = (b + c) * (b + c) + d. (ii) Optimize it and name the optimizations you used.

Q15. (Written) (i) এই statement-এর জন্য three-address code লিখুন: a = (b + c) * (b + c) + d। (ii) সেটা optimize করুন আর কোন কোন optimization ব্যবহার করলেন, নাম বলুন।

Show Answerউত্তর দেখুন

Answer:

(i) Naive TAC — each operator gets one instruction, at most three addresses each:

t1 = b + c
t2 = b + c
t3 = t1 * t2
t4 = t3 + d
a  = t4

(ii) t1 and t2 compute the same thing — apply common subexpression elimination, then copy propagation to remove the extra copy into a:

t1 = b + c
t2 = t1 * t1
a  = t2 + d

5 instructions became 3, and one addition is saved at run time. (If b, c, d were known constants, constant folding could shrink it further.)

Answer:

(i) সরল TAC — প্রতিটা operator-এর জন্য একটা instruction, প্রতিটায় সর্বোচ্চ তিনটা address:

t1 = b + c
t2 = b + c
t3 = t1 * t2
t4 = t3 + d
a  = t4

(ii) t1 আর t2 একই জিনিস হিসাব করে — common subexpression elimination লাগান, তারপর a-তে বাড়তি copy সরাতে copy propagation:

t1 = b + c
t2 = t1 * t1
a  = t2 + d

5টা instruction কমে 3টা হলো, run time-এ একটা addition বাঁচলো। (b, c, d constant হলে constant folding দিয়ে আরো ছোট করা যেত।)

Q16. (Written) (Real exam style) (i) Why is the pumping lemma called a negative proof? (ii) Using it, prove that $L = \{ww^R \mid w \in \{0,1\}^*\}$ (even-length palindromes) is not regular.

Q16. (Written) (Real exam style) (i) Pumping lemma-কে negative proof বলা হয় কেন? (ii) এটা ব্যবহার করে প্রমাণ করুন যে $L = \{ww^R \mid w \in \{0,1\}^*\}$ (even-length palindrome) regular না।

Show Answerউত্তর দেখুন

Answer:

(i) The lemma is a one-way implication: regular ⇒ pumpable. Its contrapositive — not pumpable ⇒ not regular — is the only conclusion we can draw. So it can only DISPROVE regularity; a language that passes the test may still be non-regular. To prove a language IS regular you must build a DFA/NFA/regex.

(ii) Proof by contradiction:

Assume $L$ is regular with pumping length $p$.
Choose $s = 0^p 1 1 0^p$. Here $w = 0^p 1$, so $s = ww^R \in L$, and $|s| = 2p + 2 \ge p$.
Any split $s = xyz$ with $|xy| \le p$, $|y| \ge 1$ puts $y$ inside the first block of 0s: $y = 0^k$, $k \ge 1$.
Pump down ($i = 0$): $xz = 0^{p-k} 1 1 0^p$. Its reverse is $0^p 1 1 0^{p-k}$ — not the same string, since $k \ge 1$. So $xz$ is not a palindrome, and every string in $L$ IS a palindrome. Hence $xz \notin L$.
Contradiction with the lemma → $L$ is not regular. ∎

(Intuition: the machine would need to remember the entire first half to compare with the second half — infinite memory, impossible for finite states.)

Answer:

(i) Lemma-টা এক-মুখী implication: regular ⇒ pumpable। এর contrapositive — pumpable না ⇒ regular না — এটাই একমাত্র সিদ্ধান্ত যা টানা যায়। তাই এটা শুধু regularity DISPROVE করতে পারে; test pass করা language-ও non-regular হতে পারে। কোনো language regular — প্রমাণ করতে হলে DFA/NFA/regex বানাতে হবে।

(ii) Contradiction দিয়ে proof:

Assume করুন $L$ regular, pumping length $p$।
Choose করুন $s = 0^p 1 1 0^p$। এখানে $w = 0^p 1$, তাই $s = ww^R \in L$, আর $|s| = 2p + 2 \ge p$।
$|xy| \le p$, $|y| \ge 1$ শর্তে যেকোনো split $s = xyz$-এ $y$ পড়ে প্রথম 0-block-এর ভেতরে: $y = 0^k$, $k \ge 1$।
Pump down করুন ($i = 0$): $xz = 0^{p-k} 1 1 0^p$। এর reverse হলো $0^p 1 1 0^{p-k}$ — একই string না, কারণ $k \ge 1$। তাই $xz$ palindrome না, অথচ $L$-এর প্রতিটা string palindrome। সুতরাং $xz \notin L$।
Lemma-র সাথে contradiction → $L$ regular না। ∎

(Intuition: machine-কে দ্বিতীয় অর্ধেকের সাথে মেলাতে পুরো প্রথম অর্ধেক মনে রাখতে হতো — infinite memory, finite state-এর পক্ষে অসম্ভব।)

Q17. (Written) (Real exam style) For the grammar S → ( S ) S | ε (balanced parentheses): (i) compute FIRST(S) and FOLLOW(S); (ii) build the LL(1) parsing table; (iii) show the stack trace parsing the input ( ).

Q17. (Written) (Real exam style) S → ( S ) S | ε (balanced parentheses) grammar-টার জন্য: (i) FIRST(S) আর FOLLOW(S) বের করুন; (ii) LL(1) parsing table বানান; (iii) input ( ) parse করার stack trace দেখান।

Show Answerউত্তর দেখুন

Answer:

(i) FIRST(S) = { (, ε } — the first production starts with (; the second is ε. FOLLOW(S) = { ), $ } — $ because S is the start symbol; ) because in S → ( S ) S the inner S is followed by ). (The trailing S is at the very end, so it just inherits FOLLOW(S) — nothing new.)

(ii) Placement rules: put S → (S)S under FIRST = { ( }; put S → ε under FOLLOW(S) = { ), $ }:

M	(	)	$
S	S → ( S ) S	S → ε	S → ε

No cell has two entries → the grammar is LL(1).

(iii) Stack trace for ( ) $ (stack top on the right):

Stack	Input	Action
$ S	( ) $	M[S, (] = S → ( S ) S
$ S ) S (	( ) $	match (
$ S ) S	) $	M[S, )] = S → ε
$ S )	) $	match )
$ S	$	M[S, $] = S → ε
$	$	accept

Reasoning for the key step: with ) as lookahead, the table says the inner S must vanish (S → ε), because ) is in FOLLOW(S) but not in FIRST of the other production.

Answer:

(i) FIRST(S) = { (, ε } — প্রথম production শুরু হয় ( দিয়ে; দ্বিতীয়টা ε। FOLLOW(S) = { ), $ } — $ কারণ S start symbol; ) কারণ S → ( S ) S-তে ভেতরের S-এর পরে ) আছে। (শেষের S একদম শেষে, তাই সে শুধু FOLLOW(S)-ই পায় — নতুন কিছু না।)

(ii) Placement rule: S → (S)S বসান FIRST = { ( }-এর নিচে; S → ε বসান FOLLOW(S) = { ), $ }-এর নিচে:

M	(	)	$
S	S → ( S ) S	S → ε	S → ε

কোনো cell-এ দুইটা entry নেই → grammar-টা LL(1)।

(iii) ( ) $-এর stack trace (ডানে stack-এর top):

Stack	Input	Action
$ S	( ) $	M[S, (] = S → ( S ) S
$ S ) S (	( ) $	( match
$ S ) S	) $	M[S, )] = S → ε
$ S )	) $	) match
$ S	$	M[S, $] = S → ε
$	$	accept

মূল step-এর যুক্তি: lookahead ) হলে table বলে ভেতরের S-কে হাওয়া হতে হবে (S → ε), কারণ ) আছে FOLLOW(S)-এ, অন্য production-এর FIRST-এ নেই।

Q18. (Written) (Real exam style) (i) Write a CFG for the language of all non-empty, even-length palindromes over $\{a, b, c\}$. (ii) Show a derivation of the string baccab. (iii) Explain why your grammar can never generate an odd-length string.

Q18. (Written) (Real exam style) (i) $\{a, b, c\}$-এর উপর সব non-empty, even-length palindrome-এর language-এর একটা CFG লিখুন। (ii) baccab string-এর একটা derivation দেখান। (iii) ব্যাখ্যা করুন কেন আপনার grammar কখনো odd-length string বানাতে পারে না।

Show Answerউত্তর দেখুন

Answer:

(i) Think outside-in: the first and last symbols of an even-length palindrome must match; peel them off and the middle is again an even-length palindrome. The smallest members are aa, bb, cc:

S → aSa | bSb | cSc | aa | bb | cc

No $\varepsilon$ rule, because the language excludes the empty string. No single-letter rules, because they would put an odd center in the middle.

(ii) Derivation of baccab (outer pair b...b, next pair a...a, core cc):

S ⇒ bSb ⇒ baSab ⇒ baccab   (last step uses S → cc)

(iii) Every production adds symbols two at a time: the recursive rules add one symbol on each side (+2), and the base rules produce exactly two symbols. Starting from a single S, the terminal count is always a sum of 2's — so the length is always even.

Answer:

(i) Outside-in ভাবুন: even-length palindrome-এর প্রথম আর শেষ symbol মিলতে বাধ্য; ওদের খুলে ফেললে মাঝেরটাও আবার even-length palindrome। সবচেয়ে ছোট সদস্য aa, bb, cc:

S → aSa | bSb | cSc | aa | bb | cc

$\varepsilon$ rule নেই, কারণ language-এ empty string নেই। এক-অক্ষরের rule নেই, কারণ সেটা মাঝে একটা odd center বসিয়ে দিত।

(ii) baccab-এর derivation (বাইরের জোড়া b...b, পরের জোড়া a...a, core cc):

S ⇒ bSb ⇒ baSab ⇒ baccab   (শেষ step-এ S → cc)

(iii) প্রতিটা production একসাথে দুইটা করে symbol যোগ করে: recursive rule গুলো দুই পাশে একটা করে symbol দেয় (+2), আর base rule গুলো ঠিক দুইটা symbol বানায়। একটা S থেকে শুরু করলে terminal-এর সংখ্যা সবসময় 2-এর যোগফল — তাই length সবসময় even।

Q19. (Written) (Real exam style) For the statement x = (a + b) * (c - d): (i) write the three-address code; (ii) show it as a quadruple table and as a triple table; (iii) give one advantage of each form, and explain why reordering instructions is a problem for triples.

Q19. (Written) (Real exam style) x = (a + b) * (c - d) statement-টার জন্য: (i) three-address code লিখুন; (ii) সেটা quadruple table আর triple table হিসেবে দেখান; (iii) প্রতিটা form-এর একটা করে সুবিধা বলুন, আর ব্যাখ্যা করুন triple-এ instruction reorder করা কেন সমস্যা।

Show Answerউত্তর দেখুন

Answer:

(i) Three-address code:

t1 = a + b
t2 = c - d
t3 = t1 * t2
x  = t3

(ii) Quadruples — four fields, result is a named temporary:

#	op	arg1	arg2	result
(0)	+	a	b	t1
(1)	-	c	d	t2
(2)	*	t1	t2	t3
(3)	=	t3		x

Triples — three fields, results referred to by position:

#	op	arg1	arg2
(0)	+	a	b
(1)	-	c	d
(2)	*	(0)	(1)
(3)	=	x	(2)

(iii) Quadruple advantage: results have explicit names, so the optimizer can move or reorder instructions freely (code motion) — the names stay valid. Triple advantage: more compact — no result field and no temporary names to store. Reordering breaks triples because a reference like (0) means "the result of the instruction at position 0"; move any instruction and the positions shift, so every such reference now points to the wrong row. The fix is indirect triples: reorder a separate list of pointers instead of the triples themselves.

Answer:

(i) Three-address code:

t1 = a + b
t2 = c - d
t3 = t1 * t2
x  = t3

(ii) Quadruple — চারটা field, result হলো নাম দেওয়া temporary:

#	op	arg1	arg2	result
(0)	+	a	b	t1
(1)	-	c	d	t2
(2)	*	t1	t2	t3
(3)	=	t3		x

Triple — তিনটা field, result-কে position দিয়ে refer করা হয়:

#	op	arg1	arg2
(0)	+	a	b
(1)	-	c	d
(2)	*	(0)	(1)
(3)	=	x	(2)

(iii) Quadruple-এর সুবিধা: result-এর স্পষ্ট নাম আছে, তাই optimizer instruction অবাধে সরাতে বা reorder করতে পারে (code motion) — নাম ঠিক থাকে। Triple-এর সুবিধা: বেশি compact — result field নেই, temporary-র নামও রাখতে হয় না। Triple-এ reorder সমস্যা কারণ (0)-এর মতো reference মানে "position 0-এর instruction-এর result"; কোনো instruction সরালেই position বদলে যায়, তখন এই reference গুলো ভুল row-এর দিকে দেখায়। সমাধান indirect triples: triple না সরিয়ে pointer-এর আলাদা একটা list reorder করুন।

IdentityIdentity	Meaningমানে
\(r + r = r\)	Union with itself changes nothing.নিজের সাথে union করলে কিছু বদলায় না।
\(r + \emptyset = r\)	Empty language is the identity for union.Union-এর জন্য empty language হলো identity।
\(r\varepsilon = \varepsilon r = r\)	Epsilon is the identity for concatenation.Concatenation-এর জন্য \(\varepsilon\) হলো identity।
\(r\emptyset = \emptyset\)	Concatenating with the empty language kills everything.Empty language-এর সাথে concatenate করলে সব শেষ।
\((r^)^ = r^*\)	Star of star is still star.Star-এর star মানেও star-ই।
\(\varepsilon^* = \varepsilon\), \(\emptyset^* = \varepsilon\)	Star always contains at least \(\varepsilon\).Star-এ সবসময় কমপক্ষে \(\varepsilon\) থাকে।
\((a+b)^* = (a^b^)^*\)	Both mean "all strings of a's and b's".দুটোরই মানে "a আর b-এর সব string"।

State (remainder)State (remainder)	on 00 পড়লে	on 11 পড়লে
\(q_0\) (r = 0) — start, acceptstart, accept	\(q_0\) — (2·0+0) mod 3 = 0	\(q_1\) — (2·0+1) mod 3 = 1
\(q_1\) (r = 1)	\(q_2\) — (2·1+0) mod 3 = 2	\(q_0\) — (2·1+1) mod 3 = 0
\(q_2\) (r = 2)	\(q_1\) — (2·2+0) mod 3 = 1	\(q_2\) — (2·2+1) mod 3 = 2

Compiler & Theory of ComputationCompiler & Theory of Computation

1. Regular Languages and Regular Expressions1. Regular Languages আর Regular Expressions

Basic words: alphabet, string, languageমূল শব্দ: alphabet, string, language

Regular expressions: the three operatorsRegular expression: তিনটা operator

Useful regex identitiesদরকারি regex identity

Pumping Lemma is a NEGATIVE proofPumping Lemma একটা NEGATIVE proof

2. DFA and NFA2. DFA আর NFA

DFA: formal definitionDFA: formal definition

Worked example: DFA for "strings ending in 01"Worked example: "01 দিয়ে শেষ হওয়া string"-এর DFA

Worked example: DFA for binary numbers divisible by 3Worked example: 3 দিয়ে বিভাজ্য binary number-এর DFA

NFA: nondeterminismNFA: nondeterminism

Worked example: NFA → DFA (subset construction)Worked example: NFA → DFA (subset construction)

DFA minimization (the idea)DFA minimization (মূল ধারণা)

3. CFG and PDA3. CFG আর PDA

Context-Free Grammar (CFG): the partsContext-Free Grammar (CFG): অংশগুলো

Worked example: CFG for \(a^n b^n\)Worked example: \(a^n b^n\)-এর CFG

Worked example: even-length palindromes over {a,b,c} — asked October 2017Worked example: {a,b,c}-এর উপর even-length palindrome — asked October 2017

Parse trees and ambiguityParse tree আর ambiguity

Chomsky hierarchyChomsky hierarchy

PDA: a finite automaton with a stackPDA: stack-ওয়ালা finite automaton

4. Turing Machines and Decidability4. Turing Machine আর Decidability

What is a Turing machine?Turing machine কী?

Church-Turing thesisChurch-Turing thesis

Decidable, undecidable, recognizableDecidable, undecidable, recognizable

The halting problem (proof sketch)Halting problem (proof sketch)

Closure properties summaryClosure properties summary

5. Lexical Analysis and Parsing5. Lexical Analysis আর Parsing

The phases of a compilerCompiler-এর phase গুলো

Tokens, lexemes, patternsToken, lexeme, pattern

Top-down vs bottom-up parsingTop-down বনাম bottom-up parsing

Parser comparison: LL(1) vs SLR vs LALR vs CLRParser তুলনা: LL(1) বনাম SLR বনাম LALR বনাম CLR

FIRST and FOLLOW (with example)FIRST আর FOLLOW (উদাহরণসহ)

Building the LL(1) parsing table: full worked exampleLL(1) parsing table বানানো: full worked example

Left recursion removalLeft recursion সরানো

Left factoringLeft factoring

6. Syntax and Semantic Analysis6. Syntax আর Semantic Analysis

What each phase checksকোন phase কী check করে

Syntax-directed translation (SDT)Syntax-directed translation (SDT)

Type checkingType checking

Intermediate code: three-address code (TAC)Intermediate code: three-address code (TAC)

Quadruples vs Triples — asked October 2017Quadruples বনাম Triples — asked October 2017

Code optimization: two quick examplesCode optimization: দুইটা ছোট উদাহরণ

Practice Questions (Admission Style)Practice Questions (Admission Style)