Grammar আর formal language — BNF থেকে Chomsky-র শ্রেণি

১ · Alphabet, string আর language — ভাষা মানে string-এর সেট

পর্ব ১২-এ alphabet আর Σ* recursive সংজ্ঞায় এসেছিল, আর পর্ব ১৮-এ দেখেছিলেন Σ* countable. এখানে সংজ্ঞাগুলো এক জায়গায় গুছিয়ে নিয়ে language-এর ওপর অপারেশনে যাব।

Concatenation সাধারণত commutative নয় (ab · ba = abba, কিন্তু ba · ab = baab), তবে associative: (uv)w = u(vw). আর ε হলো তার identity. পর্ব ৭০-এর ভাষায় (Σ*, ·) একটি monoid, group নয়, কারণ কোনো অশূন্য string-এর inverse নেই।

1. দৈর্ঘ্য n-এর string-এ n-টি ঘর, প্রতিটিতে k-টি স্বাধীন পছন্দ, তাই product rule অনুযায়ী kⁿটি। — পর্ব ৩১-এর গুণের নিয়ম
2. আলাদা দৈর্ঘ্যের string আলাদা, তাই Σ⁰, …, Σⁿ disjoint; যোগ করলে জ্যামিতিক ধারা। — sum rule আর পর্ব ১৭-এর সূত্র ∎

Σ = {a, b} হলে দৈর্ঘ্য 3 পর্যন্ত (ε-সহ) 1 + 2 + 4 + 8 = 15টি string; Σ = {a, b, c} হলে দৈর্ঘ্য 4 পর্যন্ত (3⁵ − 1)/2 = 121টি।

ছোট উদাহরণ নিন। L = {a, ab}, M = {b, ε} হলে LM = {ab, a, abb, ab} = {a, ab, abb}: চারটি জোড়া থেকে মাত্র তিনটি আলাদা string, কারণ a · b আর ab · ε একই। তাই |LM| ≤ |L| · |M|, সমতা সবসময় নয়। আরও কয়েকটি তথ্য, যা পরীক্ষায় প্রায়ই আসে: ∅L = ∅ (জোড়ার জন্য কোনো u নেই), {ε}L = L, আর ∅* = {ε}, কারণ L⁰ = {ε} সবসময় থাকে। খেয়াল করুন, ∅ আর {ε} আলাদা: প্রথমটিতে কোনো string নেই, দ্বিতীয়টিতে একটি string আছে, যার দৈর্ঘ্য শূন্য।

1. (ক) w ∈ L(M ∪ N) ⇔ w = uv, u ∈ L, আর v ∈ M বা v ∈ N ⇔ w ∈ LM বা w ∈ LN. — “বা” দুই দিকেই ভাগ হয়
2. (খ) w = uv, u ∈ L, v ∈ M ∩ N হলে একই ভাঙনে w ∈ LM আর w ∈ LN. উল্টো দিক ভাঙে: L = {a, ab}, M = {bc}, N = {c} নিন। M ∩ N = ∅, তাই বাঁ দিক ∅; কিন্তু abc = a · bc ∈ LM আর abc = ab · c ∈ LN. সমস্যা হলো, দুই দিকে আলাদা ভাঙন কাজ করেছে। — পাল্টা-উদাহরণ
3. (গ) L* ⊆ (L*)* স্পষ্ট (ঘাত 1). উল্টো দিকে, (L*)*-এর একটি string হলো কয়েকটি L*-string-এর জোড়া, আর প্রতিটি L*-string নিজে কয়েকটি L-শব্দের জোড়া; সব মিলিয়ে সসীম সংখ্যক L-শব্দের জোড়া, তাই L*-এ। — দুই inclusion ∎

একটি গণনা দিয়ে শেষ করি। L = {a, ab} হলে L*-এ দৈর্ঘ্য n-এর কয়টি string? L*-এর প্রতিটি string অনন্যভাবে ভাঙে, কারণ b সবসময় ঠিক আগের a-এর সঙ্গে “ab” হিসেবে আসে। শেষ টুকরো a হলে বাকিটা দৈর্ঘ্য n − 1-এর, ab হলে n − 2-এর। তাই f(n) = f(n − 1) + f(n − 2), f(0) = f(1) = 1: সংখ্যাগুলো 1, 1, 2, 3, 5, 8, … , Fibonacci (পর্ব ৪৪)। অনন্য ভাঙন না থাকলে এই হিসাব ভুল হতো; যেমন {a, aa}*-এ aaa তিনভাবে ভাঙে, কিন্তু string একটিই।

২ · Phrase-structure grammar — নিয়ম দিয়ে ভাষা বানানো

{aⁿbⁿ : n ≥ 0} বা সব balanced বন্ধনীর মতো অসীম language তালিকা করে লেখা যায় না। দরকার একটি সসীম বর্ণনা। একটি উপায় হলো ছক আর প্রতিস্থাপনের নিয়ম, যেমন স্কুলে শেখা “বাক্য → কর্তা + কর্ম + ক্রিয়া, কর্তা → আমি | রহিম, …”। Grammar এই ধারণার গাণিতিক রূপ।

উদাহরণ: V = {S}, T = {a, b}, নিয়ম S → aSb | ε. তাহলে

S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaabbb.

প্রতিটি ধাপে বাঁয়ে একটি a আর ডানে একটি b যোগ হয়, শেষে S মুছে যায়। তাই L(G) = {aⁿbⁿ : n ≥ 0} মনে হয়; এর পূর্ণ প্রমাণ অনুশীলন ১-এ। একটি sentential form-এ একাধিক variable থাকলে কোনটি আগে বদলাবেন, সেই স্বাধীনতা থাকে। প্রতিবার সবচেয়ে বাঁয়ের variable বদলালে তাকে বলে leftmost derivation; §৪-এ দেখবেন এটি গাছের সঙ্গে এক-এক মেলে।

Grammar আসলে একটি recursive সংজ্ঞা (পর্ব ১২): নিয়মগুলো recursive step, আর L(G)-এর “আর কিছু নয়” অংশটি আসে “শুধু derivation-এ যা পাওয়া যায়” থেকে। তাই grammar-এর দাবি প্রমাণের প্রধান অস্ত্র structural induction বা derivation-এর দৈর্ঘ্যের ওপর induction.

নিচের ব্লক একটি grammar থেকে দৈর্ঘ্য n পর্যন্ত সব বাক্য বানায়: শুধু leftmost variable বদলায়, আর কোনো sentential form-এ n-এর বেশি terminal হয়ে গেলে সেই পথ ছেড়ে দেয় (terminal কখনো মোছে না, তাই এটি নিরাপদ)। তারপর ফলাফল সব string-এর মধ্য থেকে একটি সদস্যতা-পরীক্ষা (predicate) দিয়ে বাছাই করা সেটের সঙ্গে মেলায়। তৃতীয় grammar-টি ইচ্ছা করে ত্রুটিপূর্ণ। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

from itertools import product
def generate(rules, n, start="S"):     # all terminal strings of length <= n
    seen, todo, out = {start}, [start], set()
    while todo:
        form = todo.pop()
        i = next((k for k, ch in enumerate(form) if ch in rules), None)
        if i is None:                  # no variable left: a sentence
            out.add(form)
            continue
        for rhs in rules[form[i]]:     # expand the leftmost variable
            new = form[:i] + rhs + form[i + 1:]
            if sum(ch not in rules for ch in new) <= n and new not in seen:
                seen.add(new)
                todo.append(new)
    return out
def balanced(w):                       # counter never negative, ends at 0
    d = 0
    for ch in w:
        d += 1 if ch == "(" else -1
        if d < 0:
            return False
    return d == 0
anbn = lambda w: w == "a" * (len(w) // 2) + "b" * (len(w) // 2)
N = 10
tests = [("S->(S)S|e", {"S": ["(S)S", ""]}, "()", balanced),
         ("S->aSb|e", {"S": ["aSb", ""]}, "ab", anbn),
         ("S->(S)|()S|e", {"S": ["(S)", "()S", ""]}, "()", balanced)]
for name, G, sigma, pred in tests:
    gen = generate(G, N)
    want = {"".join(t) for L in range(N + 1)
            for t in product(sigma, repeat=L) if pred("".join(t))}
    print(f"{name}: lengths 0,2,..,{N}:", [sum(len(w) == L for w in gen) for L in range(0, N + 1, 2)])
    miss = sorted(want - gen, key=lambda w: (len(w), w))
    print("   same as the predicate:", gen == want, "| missing:", miss[:2])

S->(S)S|e: lengths 0,2,..,10: [1, 1, 2, 5, 14, 42]
   same as the predicate: True | missing: []
S->aSb|e: lengths 0,2,..,10: [1, 1, 1, 1, 1, 1]
   same as the predicate: True | missing: []
S->(S)|()S|e: lengths 0,2,..,10: [1, 1, 2, 4, 8, 16]
   same as the predicate: False | missing: ['(())()', '((())())']

৩ · BNF — programming language আর বাজারঘরের অর্ডার-কমান্ড

Programming language-এর manual খুললে syntax লেখা থাকে এমন রূপে: <statement> ::= <assignment> | <if-statement>. এটি BNF (Backus–Naur Form): context-free grammar-এর (§৭) একটি লেখার রীতি। কোণ-বন্ধনীতে নাম মানে variable, উদ্ধৃতিতে লেখা মানে terminal, ::= মানে →, আর | মানে “অথবা”। John Backus ১৯৫৯ সালে ALGOL-এর syntax বর্ণনায় এই ধরনের রীতি প্রস্তাব করেন, আর Peter Naur-এর সম্পাদনায় ALGOL 60-এর রিপোর্টে তা ব্যবহৃত হয় (ইতিহাস ভাবনার প্রশ্ন ১-এ)। পরে EBNF আর ABNF-এর মতো রূপে ঐচ্ছিক অংশ ([ ]) আর পুনরাবৃত্তি ({ }) লেখার সংক্ষেপ যোগ হয়েছে; এদের প্রকাশ-ক্ষমতা একই।

বাজারঘরের গুদামের কর্মীরা একটি ছোট টার্মিনালে লেখা কমান্ড দিয়ে অর্ডার দেন বা বাতিল করেন। পুরো ভাষাটির BNF (সব নাম আর কোড কাল্পনিক):

<command>  ::= <order> | <cancel>
<order>    ::= "ORDER" <items> "TO" <district>
<items>    ::= <item> | <item> "," <items>
<item>     ::= <qty> "x" <code>
<qty>      ::= <nz> | <nz> <digit>
<code>     ::= "P-" <digit> <digit> <digit> <digit>
<district> ::= "DHAKA" | "KHULNA" | "SYLHET" | "RAJSHAHI"
<cancel>   ::= "CANCEL" "BG" <digit><digit><digit><digit><digit><digit>
<nz>       ::= "1" | "2" | … | "9"
<digit>    ::= "0" | <nz>

<items>-এর নিয়মটি recursive: একটি item, অথবা একটি item, কমা, আর আবার <items>. তাই যত খুশি item লেখা যায়, অথচ নিয়ম মাত্র দুটি। <qty> বলে পরিমাণ 1 থেকে 99, আর শুরুতে 0 চলবে না। এই grammar থেকে পরীক্ষাযোগ্য একটি প্রোগ্রাম বানানোর সরল কৌশল হলো recursive descent: প্রতিটি variable-এর জন্য একটি ফাংশন, যা নিয়মের ডান দিক বাঁ থেকে ডানে মেলায়, আর অন্য variable এলে সেই ফাংশনকে ডাকে। Recursive নিয়ম তখন recursive ফাংশন হয়ে যায়; call stack-এর ভূমিকা DSA কোর্সের পর্ব ১৩-এ। নিচের ব্লক ঠিক এভাবে একটি recogniser লেখে, যা বলে কমান্ডটি ভাষায় আছে কি না, আর না থাকলে কোন token-এ আটকাল।

DIGITS, DISTRICTS = "0123456789", {"DHAKA", "KHULNA", "SYLHET", "RAJSHAHI"}
def qty(t):        # <qty> ::= <nz> | <nz> <digit>
    return 1 <= len(t) <= 2 and t[0] in "123456789" and all(c in DIGITS for c in t)
def code(t):       # <code> ::= "P-" <digit> <digit> <digit> <digit>
    return len(t) == 6 and t[:2] == "P-" and all(c in DIGITS for c in t[2:])
def items(toks, i):    # <items> ::= <item> | <item> "," <items>; returns next index
    if i + 2 >= len(toks) or not (qty(toks[i]) and toks[i + 1] == "x" and code(toks[i + 2])):
        raise SyntaxError(f"token {i + 1}: expected <item>")
    if i + 3 < len(toks) and toks[i + 3] == ",":
        return items(toks, i + 4)
    return i + 3
def command(line):
    toks = line.replace(",", " , ").split()
    if toks[:1] == ["CANCEL"]:     # <cancel> ::= "CANCEL" "BG" <digit>^6
        t = toks[1] if len(toks) == 2 else ""
        if not (len(t) == 8 and t[:2] == "BG" and all(c in DIGITS for c in t[2:])):
            raise SyntaxError("expected CANCEL <orderid>")
        return "cancel"
    if toks[:1] != ["ORDER"]:
        raise SyntaxError("token 1: expected ORDER or CANCEL")
    i = items(toks, 1)             # <order> ::= "ORDER" <items> "TO" <district>
    if toks[i:i + 1] != ["TO"] or len(toks) != i + 2 or toks[i + 1] not in DISTRICTS:
        raise SyntaxError(f"token {i + 1}: expected TO <district> and end")
    return f"order, {i // 4} item(s)"
for line in ["ORDER 2 x P-1042 TO KHULNA",
             "ORDER 1 x P-0007, 12 x P-3301 TO SYLHET",
             "CANCEL BG202611",
             "ORDER 0 x P-1042 TO DHAKA",
             "ORDER 2 x P-1042, TO DHAKA",
             "ORDER 3 x P-55 TO RAJSHAHI",
             "ORDER 2 x P-1042 TO COMILLA"]:
    try:
        print("OK  ", line, "->", command(line))
    except SyntaxError as e:
        print("FAIL", line, "->", e)

OK   ORDER 2 x P-1042 TO KHULNA -> order, 1 item(s)
OK   ORDER 1 x P-0007, 12 x P-3301 TO SYLHET -> order, 2 item(s)
OK   CANCEL BG202611 -> cancel
FAIL ORDER 0 x P-1042 TO DHAKA -> token 2: expected <item>
FAIL ORDER 2 x P-1042, TO DHAKA -> token 6: expected <item>
FAIL ORDER 3 x P-55 TO RAJSHAHI -> token 2: expected <item>
FAIL ORDER 2 x P-1042 TO COMILLA -> token 5: expected TO <district> and end

৪ · Derivation tree — বাক্যের গঠন গাছে

Derivation একটি ধাপের তালিকা, কিন্তু কোন অংশ কোন নিয়ম থেকে এসেছে, তা গাছে সবচেয়ে স্পষ্ট দেখা যায়। নিচের সংজ্ঞা context-free grammar-এর জন্য, যেখানে প্রতিটি নিয়মের বাঁ দিকে ঠিক একটি variable (§৭-এর type 2).

1. গাছ থেকে derivation: গাছের ভেতরের node-গুলো preorder-এ (পর্ব ৬৬) ঘুরুন, আর প্রতিটি node-এ তার নিয়মটি খাটান। Preorder সবসময় এখনো-না-খোলা সবচেয়ে বাঁয়ের variable-কেই আগে পায়, তাই derivation-টি leftmost. — preorder-এর সংজ্ঞা
2. Derivation থেকে গাছ: S দিয়ে শুরু করে প্রতিটি ধাপে যে variable বদলাল, গাছে তার নিচে নিয়মের ডান দিকের চিহ্নগুলো সন্তান হিসেবে বসান। Context-free নিয়ম আশপাশের চিহ্নের ওপর নির্ভর করে না, তাই প্রতিটি ধাপ ঠিক একটি node খোলে। — derivation-এর দৈর্ঘ্যে induction
3. দুটি নির্মাণ একে অপরের inverse: একটি leftmost derivation থেকে গাছ বানিয়ে আবার preorder-এ পড়লে একই ধাপ একই ক্রমে আসে, আর উল্টোটাও। তাই এক-এক মিল। ∎ — দুই দিকের composition = identity

এখন গাণিতিক রাশির একটি grammar নিন, যাকে বলব grammar U:

E → E + T | T,   T → T * F | F,   F → ( E ) | a

E মানে expression (যোগফল), T মানে term (গুণফল), F মানে factor (একটি a বা বন্ধনীর ভেতরে একটি পূর্ণ রাশি)। a যেকোনো সংখ্যা বা চলকের প্রতিনিধি। নিচের ছবিতে a + a * a-এর একমাত্র parse tree.

নিচের stepper এই গাছের leftmost derivation দেখায়: প্রতিটি ধাপে সবচেয়ে বাঁয়ের variable বদলায়, আর বাঁয়ের তালিকায় সেই ধাপের নিয়মটি উজ্জ্বল হয়।

1E → E + T2E → T3T → T * F4T → F5F → ( E )6F → a

Parse tree থেকে E → T → F-এর মতো একক-সন্তানের শিকল আর বন্ধনী ছেঁটে ফেললে পাওয়া যায় পর্ব ৬৬-এর expression tree, যাকে compiler-এর ভাষায় abstract syntax tree বলে। তাই grammar-এর গঠনই ঠিক করে, রাশির মান কোন ক্রমে হিসাব হবে।

৫ · Ambiguity — একই string, দুটি গাছ

সরল দেখতে একটি grammar, যাকে বলব grammar A: E → E + E | E * E | ( E ) | a. এটি “যোগ বা গুণ করে দুটি রাশি জোড়া যায়” কথাটি সরাসরি লেখে, কিন্তু কোন অপারেশন আগে, তা বলে না। নিচের stepper-এ a + a * a-এর দুটি গাছ দেখুন, আর তিনটি a-তে ক্রমে 2, 3, 4 বসিয়ে মান হিসাব করুন।

Grammar U দুটি কৌশলে ambiguity দূর করে: আলাদা স্তর (E, T, F) দিয়ে precedence, অর্থাৎ গুণ যোগের চেয়ে শক্ত বাঁধন; আর E → E + T-এর মতো বাঁ-দিকে-recursive নিয়ম দিয়ে বাঁ থেকে ডানে জোড়া (a + a + a মানে (a + a) + a). কিন্তু দুই grammar-এর language কি সত্যিই এক? না হলে ambiguity দূর করতে গিয়ে কিছু রাশি হারিয়ে ফেলতাম।

1. (L(U) ⊆ L(A)) U-এর যেকোনো derivation-এ T আর F-কে E নামে ডাকুন। তাহলে E → E + T হয় E → E + E, T → T * F হয় E → E * E, F → ( E ) আর F → a A-তেও আছে, আর E → T, T → F হয়ে যায় E → E, যা শুধু বাদ দিলেই চলে। ফলে প্রতিটি U-derivation একটি A-derivation হয়ে যায়, একই বাক্যে শেষ হয়। — নিয়মের অনুবাদ
2. (উল্টো দিকের প্রস্তুতি) U-এর নিয়ম E → E + T | T থেকে, derivation-এর দৈর্ঘ্যে induction করে, E থেকে পাওয়া বাক্য ঠিক t₁ + t₂ + ⋯ + t_k আকারের (k ≥ 1), যেখানে প্রতিটি t_i T থেকে পাওয়া; একইভাবে T-এর বাক্য f₁ * ⋯ * f_j, যেখানে প্রতিটি f_i F থেকে পাওয়া। — বাঁ-recursive নিয়মের শিকল
3. L(U) তিনটি অপারেশনে বদ্ধ: x, y ∈ L(U) হলে x + y ∈ L(U) (দুটি term-এর যোগফলের তালিকা জোড়া দিলেই হয়), (x) ∈ L(U) (F → ( E )), আর x * y ∈ L(U): x = t₁ + ⋯ + t_k, y = s₁ + ⋯ + s_l হলে x * y = t₁ + ⋯ + t_k−1 + (t_k * s₁) + s₂ + ⋯ + s_l, আর t_k * s₁ দুটি গুণফলের জোড়া, তাই নিজেই একটি term (এখানে বাইরের বন্ধনীগুলো শুধু পড়ার সুবিধার জন্য, string-এর অংশ নয়)। — ধাপ ২
4. (L(A) ⊆ L(U)) A-এর প্রতিটি বাক্য a থেকে শুরু করে x + y, x * y আর (x) দিয়ে বানানো, আর a ∈ L(U). ধাপ ৩ অনুযায়ী প্রতিটি নির্মাণ L(U)-এর ভেতরে থাকে, তাই A-এর parse tree-র ওপর structural induction-এ L(A) ⊆ L(U). ∎ — structural induction

নিচের ব্লক দুই grammar-এ একটি string-এর parse tree গোনে (প্রতিটি variable আর প্রতিটি substring-এর জন্য গাছের সংখ্যা একবার হিসাব করে মনে রেখে, অর্থাৎ dynamic programming), তারপর a, +, *, (, ) দিয়ে দৈর্ঘ্য 6 পর্যন্ত সব string পরীক্ষা করে দুই language মেলায়।

from functools import lru_cache
from itertools import product
def trees(w):          # parse trees of w in A: E -> E+E | E*E | (E) | a
    @lru_cache(None)
    def E(i, j):
        n = (j - i == 1 and w[i] == "a")
        n += sum(E(i, k) * E(k + 1, j) for k in range(i + 1, j - 1) if w[k] in "+*")
        if j - i >= 3 and w[i] == "(" and w[j - 1] == ")":
            n += E(i + 1, j - 1)
        return n
    return E(0, len(w))
def trees_u(w):        # U: E -> E+T | T,  T -> T*F | F,  F -> (E) | a
    @lru_cache(None)
    def F(i, j):
        if j - i == 1:
            return int(w[i] == "a")
        return E(i + 1, j - 1) if w[i] == "(" and w[j - 1] == ")" and j - i >= 3 else 0
    @lru_cache(None)
    def T(i, j):
        return F(i, j) + sum(T(i, k) * F(k + 1, j) for k in range(i + 1, j - 1) if w[k] == "*")
    @lru_cache(None)
    def E(i, j):
        return T(i, j) + sum(E(i, k) * T(k + 1, j) for k in range(i + 1, j - 1) if w[k] == "+")
    return E(0, len(w))
for w in ["a+a*a", "a+a+a", "a+a+a+a", "a*a+a*a+a", "(a+a)*a", "a+a+a+a+a+a"]:
    print(f"{w:12} grammar A: {trees(w):3} tree(s)  grammar U: {trees_u(w)} tree(s)")
N = 6
words = ["".join(t) for L in range(1, N + 1) for t in product("a+*()", repeat=L)]
LA = {w for w in words if trees(w)}
LU = {w for w in words if trees_u(w)}
print(f"length <= {N}: checked {len(words)} strings; |L(A)| = {len(LA)}, |L(U)| = {len(LU)}, equal: {LA == LU}")
print("max trees per string in U:", max(trees_u(w) for w in LU))

a+a*a        grammar A:   2 tree(s)  grammar U: 1 tree(s)
a+a+a        grammar A:   2 tree(s)  grammar U: 1 tree(s)
a+a+a+a      grammar A:   5 tree(s)  grammar U: 1 tree(s)
a*a+a*a+a    grammar A:  14 tree(s)  grammar U: 1 tree(s)
(a+a)*a      grammar A:   1 tree(s)  grammar U: 1 tree(s)
a+a+a+a+a+a  grammar A:  42 tree(s)  grammar U: 1 tree(s)
length <= 6: checked 19530 strings; |L(A)| = 15, |L(U)| = 15, equal: True
max trees per string in U: 1

Dangling else

Programming language-এ সবচেয়ে বিখ্যাত ambiguity: S → if b then S | if b then S else S | x. বাক্য if b then if b then x else x-এ else-টি কোন if-এর? ভেতরের if-এর সঙ্গে জুড়লে একটি গাছ, বাইরের if-এর সঙ্গে জুড়লে আরেকটি; দুটোই বৈধ, অর্থ আলাদা। (তিনটি if আর দুটি else থাকলে গাছ হয় 3টি; scratch-এ গোনা।) C আর Java নিয়ম করে দিয়েছে, else সবচেয়ে কাছের মেলানো-হয়নি এমন if-এর সঙ্গে যাবে; Python indentation দিয়ে, আর অনেক নতুন ভাষা বাধ্যতামূলক বন্ধনী দিয়ে প্রশ্নটিই এড়ায় (ভাবনার প্রশ্ন ৩)।

দুটি গভীর তথ্য বক্তব্য হিসেবে, প্রমাণ ছাড়া। প্রথমত, কিছু context-free language inherently ambiguous: তাদের প্রতিটি grammar-ই ambiguous. প্রচলিত উদাহরণ {aⁱb^jc^k : i = j অথবা j = k}, যেখানে aⁿbⁿcⁿ-এর মতো string “দুই কারণে” ভাষায় থাকে; এই ধরনের ফলের কৃতিত্ব সাধারণত Rohit Parikh-কে দেওয়া হয় (১৯৬০-এর দশক)। দ্বিতীয়ত, “এই context-free grammar কি ambiguous?” প্রশ্নের উত্তর দেওয়ার এমন কোনো সাধারণ algorithm নেই, যা সব grammar-এ কাজ করে; এটি undecidable বলে ১৯৬০-এর দশকের গোড়ায় কয়েকজন গবেষক দেখান। Undecidable মানে কী, তা পর্ব ৭৫ “Turing machine-এর পরিচয় — computability আর halting problem”-এ।

৬ · প্রমাণ: grammar ঠিক এই language-টিই বানায়

“G-এর language L” দাবিটি আসলে সেটের সমতা, L(G) = L, তাই দুটি inclusion প্রমাণ করতে হয়। Soundness (L(G) ⊆ L): grammar যা বানায়, সবই ঠিক; সাধারণত derivation-এর দৈর্ঘ্যে induction. Completeness (L ⊆ L(G)): L-এর প্রতিটি string grammar বানাতে পারে; সাধারণত string-এর দৈর্ঘ্যে strong induction (পর্ব ১১)। §২-এর ত্রুটিপূর্ণ grammar দেখিয়েছে, শুধু soundness যথেষ্ট নয়।

পর্ব ১২-এ balanced parentheses recursive নিয়মে সংজ্ঞায়িত হয়েছিল। এখানে একটি স্বাধীন, গণনাভিত্তিক সংজ্ঞা নিই: w ∈ {(, )}* balanced, যদি w-এ “(” আর “)”-এর সংখ্যা সমান, আর w-এর প্রতিটি prefix-এ “(” অন্তত “)”-এর সমান। Prefix-এ “(” বিয়োগ “)”-কে বলব গভীরতা।

1. (Soundness, ভিত্তি) S ⇒* w-এর প্রথম ধাপ S → ε হলে w = ε, যা balanced. — derivation-এর দৈর্ঘ্যে strong induction
2. (Soundness, ধাপ) প্রথম ধাপ S → ( S ) S হলে w = (u)v, যেখানে দুই S থেকে আলাদাভাবে u আর v পাওয়া গেছে, প্রতিটি ছোট derivation-এ। Context-free নিয়মে দুই S একে অপরকে প্রভাবিত করে না, তাই এই ভাগ বৈধ। Induction hypothesis অনুযায়ী u, v balanced. — context-free-এর স্বাধীনতা
3. (w balanced) গোনা সমান স্পষ্ট। Prefix-এর গভীরতা: “(” পরে 1; u-এর ভেতরে 1 + (u-এর prefix-এর গভীরতা) ≥ 1; “)” পরে 0; তারপর v-এর prefix-এর গভীরতা ≥ 0. কোথাও ঋণাত্মক নয়। — গভীরতার হিসাব
4. (Completeness) |w|-এ strong induction. w = ε হলে S → ε. নইলে w balanced, তাই প্রথম চিহ্ন “(” (নইলে প্রথম prefix-এর গভীরতা −1). গভীরতা প্রথম যে অবস্থানে আবার 0 হয়, সেটি k (শেষে গভীরতা 0, তাই k আছে)। — first return
5. w = (u)v লিখুন, যেখানে (u) হলো w-এর প্রথম k চিহ্ন। u-এর ভেতরে w-এর গভীরতা ≥ 1, তাই u-এর নিজের প্রতিটি prefix-এর গভীরতা ≥ 0, আর u শেষ হয় 0-এ: u balanced. v শুরু হয় গভীরতা 0 থেকে আর শেষ হয় 0-এ, মাঝে ঋণাত্মক নয়: v balanced. — দুই অংশ
6. |u|, |v| < |w|, তাই induction hypothesis অনুযায়ী S ⇒* u আর S ⇒* v. ফলে S ⇒ (S)S ⇒* (u)S ⇒* (u)v = w. ∎ — induction hypothesis

ধাপ ৪–৫-এর ভাঙন অনন্য, কারণ “প্রথম যেখানে গভীরতা 0” একটিই। তাই প্রতিটি balanced string-এর ঠিক একটি parse tree, অর্থাৎ G_B unambiguous. সঙ্গে একটি গণনাও আসে: দৈর্ঘ্য 2n-এর balanced string-এর সংখ্যা c_n হলে, |u| = 2i বেছে নিয়ে c_n+1 = ∑_i=0..n c_ic_n−i, c₀ = 1. এটিই Catalan সংখ্যা-র recurrence, যা §২-এর আউটপুটে 1, 1, 2, 5, 14, 42 দেখিয়েছে। ত্রুটিপূর্ণ S → (S) | ()S | ε-এ প্রমাণটি ঠিক ধাপ ৬-এ ভাঙে: u আর v দুটিই অশূন্য হলে, যেমন (())()-এ u = (), v = (), কোনো নিয়ম (u)v-কে একসঙ্গে বানাতে পারে না।

৭ · Chomsky hierarchy — নিয়মের আকারে চার শ্রেণি

Noam Chomsky ১৯৫৬ সালে “Three models for the description of language” প্রবন্ধে আর ১৯৫৯ সালের একটি প্রবন্ধে নিয়মের আকারের ওপর ভিত্তি করে grammar-এর কয়েকটি স্তর প্রস্তাব করেন। পাঠ্যবইয়ে প্রচলিত রূপটি নিচে (ছোট বিবরণ বইভেদে সামান্য আলাদা)। ধরুন A, B ∈ V, a ∈ T, আর α, β ∈ (V ∪ T)*.

“Context-sensitive” নামের উৎস: পুরোনো রূপে নিয়ম ছিল γAδ → γβδ, অর্থাৎ A-কে β দিয়ে বদলানো যায় শুধু γ আর δ-এর “প্রসঙ্গে”। Noncontracting grammar আর এই রূপ একই language-শ্রেণি দেয়, এটি একটি জানা উপপাদ্য। Type 2-এ প্রসঙ্গ লাগে না: A যেখানেই থাকুক, বদলানো যায়। একটি সূক্ষ্মতা: type 2 grammar-এ A → ε থাকতে পারে, যা noncontracting নয়; তবু প্রতিটি context-free language type 1, কারণ যেকোনো context-free grammar থেকে ε-নিয়ম সরিয়ে (দরকার হলে শুধু S → ε রেখে) একই language-এর grammar বানানো যায়।

“⊆” অংশগুলো সংজ্ঞা থেকেই প্রায় সরাসরি (type 2 ⊆ type 1-এর ε-সূক্ষ্মতা ওপরে)। কড়াভাবে আলাদা হওয়ার প্রমাণ এখানে নয়: (ক)-এর জন্য regular language-এর pumping lemma পর্ব ৭৪-এ পূর্ণ প্রমাণসহ আসবে; (খ)-এর জন্য context-free language-এর pumping lemma লাগে, যা পরিকল্পিত Theory of Computation কোর্সে; আর type 1 ⊊ type 0-এর যুক্তি পর্ব ৭৫-এর decidability-র ওপর দাঁড়ায়। এই পর্বের সব বিষয়ই আসলে পরিচিতি; automata, grammar আর computability-র পূর্ণ তত্ত্ব পরিকল্পিত Theory of Computation কোর্সের বিষয়।

Grammar-এর শ্রেণি আর language-এর শ্রেণি আলাদা জিনিস। একটি grammar-এর type দেখে বলা যায় তার language অন্তত কতটা সরল, কিন্তু অন্য কোনো সরল grammar একই language দিতে পারে। নিচের stepper চারটি grammar-কে শ্রেণিতে বসায়; প্রতিটির language scratch-এ দৈর্ঘ্য 5–12 পর্যন্ত সব derivation বানিয়ে মেলানো।

1G1: S → aS | bT | b2    T → bT | b3G2: S → aSb | ab4G3: S → aSBC | aBC5    CB → BC, aB → ab6    bB → bb, bC → bc7    cC → cc8G4: S → aS | ε9    aa → a

৮ · কয়টি language-এর grammar আছে? — countability-র উত্তর

Type 0 সবচেয়ে উদার শ্রেণি। তাহলে কি প্রতিটি language-এর কোনো না কোনো grammar আছে? পর্ব ১৮-এর গণনা বলে, না; আর যুক্তিটি এক অনুচ্ছেদের।

1. Variable-গুলোর নাম বদলালে L(G) বদলায় না, তাই ধরে নিন variable-এর নাম V1, V2, V3, … . তাহলে প্রতিটি grammar একটি সসীম লেখা, যেমন S=V1; V1->aV1b; V1->;, একটি সসীম alphabet Δ = T ∪ {V, 0, …, 9, -, >, ;, =, S}-এর ওপর। — সংকেতে লেখা
2. আলাদা grammar আলাদা লেখা পায়, তাই grammar-এর সেট থেকে Δ*-এ একটি one-to-one ফাংশন আছে। Δ* countable (পর্ব ১৮), আর countable সেটের subset countable. — injection
3. প্রতিটি grammar ঠিক একটি language দেয়, তাই grammar আছে এমন language-এর সেটও countable. — countable সেটের image
4. সব language-এর সেট P(T*), আর T* countably infinite, তাই Cantor-এর উপপাদ্যে P(T*) uncountable. Uncountable সেট একটি countable subset-এর সমান হতে পারে না। ∎ — পর্ব ১৮-এর diagonal

T = {a}-এ diagonal সরাসরি লেখা যায়। Grammar-গুলো ক্রমে G₁, G₂, … সাজান (shortlex ক্রমে তাদের লেখা), আর নিন D = {aⁱ : aⁱ ∉ L(G_i)}. প্রতিটি i-এ D আর L(G_i) অন্তত string aⁱ-এ আলাদা, তাই D কোনো grammar-এর language নয়। এই diagonal argument একটি অস্তিত্বের প্রমাণ; কোনো স্বাভাবিক, নির্দিষ্ট উদাহরণ এটি দেয় না। পর্ব ৭৫ দেখাবে type 0 grammar আর Turing machine একই language চেনে, আর halting problem-এর “না”-সেটের মতো নির্দিষ্ট language-এর কোনো grammar নেই।

৯ · পরীক্ষার অঙ্ক আর একটি ভুল প্রমাণ

অঙ্ক ১: string আর language গোনা

(ক) Σ = {0, 1, 2}-এ দৈর্ঘ্য 2 পর্যন্ত কয়টি string? (খ) L = {a, ab} হলে L² লিখুন। (গ) L*-এ দৈর্ঘ্য 5-এর কয়টি string?

1. (ক) 1 + 3 + 9 = 13 (ε-সহ)। সূত্রে (3³ − 1)/2 = 13.
2. (খ) L² = {aa, aab, aba, abab}: চারটি জোড়া থেকে চারটি আলাদা string, এখানে কোনো মিল নেই।
3. (গ) §১-এর recurrence f(n) = f(n − 1) + f(n − 2), f(0) = f(1) = 1: f(2) = 2, f(3) = 3, f(4) = 5, f(5) = 8. তালিকা: aaaaa, aaaab, aaaba, aabaa, abaaa, aabab, abaab, ababa. (scratch-এ গুনে মেলানো।)

অঙ্ক ২: grammar বানান, ambiguity ধরুন

L = {aⁱb^j : i ≥ j ≥ 0}-এর একটি grammar দিন। প্রস্তাব G: S → aS | aSb | ε. এটি কি ambiguous? হলে একটি unambiguous grammar দিন।

1. G-এর প্রতিটি নিয়ম বাঁয়ে একটি a দেয়, আর b দিলে সঙ্গে একটি a দেয়, তাই b কখনো a-এর চেয়ে বেশি হয় না, আর সব a সব b-এর আগে থাকে; উল্টো দিকে aⁱb^j পেতে j বার aSb, তারপর i − j বার aS, শেষে ε. তাই L(G) = L.
2. aab-এর দুটি গাছ: S ⇒ aS ⇒ aaSb ⇒ aab, আর S ⇒ aSb ⇒ aaSb ⇒ aab. প্রথমটিতে বাইরের a “একা”, দ্বিতীয়টিতে ভেতরের a. তাই G ambiguous.
3. সমাধান: আগে সব একা a, পরে জোড়া: S → aS | T, T → aTb | ε. এখন aⁱb^j-এ একা a ঠিক i − j-টি আর তারা বাইরে, তাই গাছ একটিই। Scratch-এ দৈর্ঘ্য 8 পর্যন্ত দুই grammar-এর language L-এর সমান আর নতুন grammar-এ প্রতিটি string-এর ঠিক একটি গাছ মিলেছে; aab-এ G-এর গাছ 2, aaab-এ 3.

অঙ্ক ৩: গাছ গোনা

Grammar A (E → E + E | E * E | ( E ) | a)-এ a * a * a * a * a-এর কয়টি parse tree? চারটি অপারেটর, প্রতিটি গাছ একটি পূর্ণ বন্ধনী-বিন্যাস, তাই C₄ = C(8, 4)/5 = 70/5 = 14. Grammar U-তে 1.

প্রমাণের ভুল ধরুন: “সমান সংখ্যক বন্ধনী”

দাবি: “S → ( S ) | S S | ε grammar-টি ঠিক সেই সব string বানায়, যাতে ( আর ) সমান সংখ্যক। প্রমাণ: S → ( S ) একটি ( আর একটি ) যোগ করে, S → S S আর S → ε কোনো বন্ধনী যোগ করে না। তাই derivation-এর প্রতিটি ধাপে দুই বন্ধনীর সংখ্যা সমান থাকে। ∎”

ভুল কোথায়: যুক্তিটি শুধু soundness দেখায়: grammar-এর প্রতিটি string-এ সংখ্যা সমান। দাবির অন্য দিক, “সমান সংখ্যার প্রতিটি string grammar বানায়”, প্রমাণই হয়নি, আর তা মিথ্যা: )(-এ সংখ্যা সমান, কিন্তু grammar-এর প্রতিটি string ( দিয়ে শুরু হয় (বা ε)। সঠিক দাবি হলো L = balanced string-এর সেট, যার প্রমাণে উপপাদ্য ৬.১-এর মতো দুই দিক লাগে; আর এই grammar ambiguous-ও, কারণ ()()()-কে S S দিয়ে দুইভাবে ভাগ করা যায়।

১০ · AI-এর যুগে — grammar নিয়ে AI-এর উত্তর যাচাই

AI সহকারী grammar লিখতে বেশ পারদর্শী, কিন্তু এমন ভুল নিয়মিত করে, যা চোখে পড়ে না, কারণ grammar দেখতে “ঠিকঠাক” লাগে। কয়েকটি পরিচিত ভুল আর ধরার উপায়:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• ε আর সবচেয়ে ছোট string-গুলো grammar বানায় কি না নিজে দেখেছি
• দৈর্ঘ্য n পর্যন্ত সব বাক্য বানিয়ে predicate-এর সঙ্গে দুই দিকে মিলিয়েছি
• প্রমাণে দুটি inclusion আছে, আর induction-এর ভিত্তি বাদ পড়েনি
• Unambiguity-র দাবি ছোট string-এ গাছ গুনে পরীক্ষা করেছি
• Grammar-এর type আর language-এর type আলাদা করে বিচার করেছি
• নাম, সাল আর উপপাদ্যের শর্ত বিশ্বস্ত উৎসে মিলিয়েছি

Grammar-এর দাবি যাচাই করা সহজ, কারণ ছোট দৈর্ঘ্যে সব string গুনে ফেলা যায়: দৈর্ঘ্য 10 পর্যন্ত {(, )}-এ মাত্র 2,047টি। তবে মনে রাখবেন, ছোট ক্ষেত্রে মিল একটি প্রমাণ নয়; ভুল ধরার জাল মাত্র।