আলফাবেট, স্ট্রিং ও ল্যাঙ্গুয়েজ

১ · আলফাবেট ও স্ট্রিং

একটি আলফাবেটAlphabet (Σ)সিম্বলের একটি ফাইনাইট, নন-এম্পটি সেট — যেমন Σ = {0,1} বা Σ = {a,b,c}। (আলফাবেট, চিহ্নিত করা হয় $\Sigma$) হলো সিম্বলের একটি ফাইনাইট (সসীম) ও নন-এম্পটি সেট — যেমন $\Sigma = \{0,1\}$ (বাইনারি আলফাবেট) বা $\Sigma = \{a,b,\ldots,z\}$। একটি স্ট্রিংString (word)একটি আলফাবেট থেকে নেওয়া সিম্বলের একটি ফাইনাইট সিকোয়েন্স। (বা "word") হলো $\Sigma$ থেকে নেওয়া সিম্বলের একটি ফাইনাইট সিকোয়েন্স — যেমন "0110" একটি স্ট্রিং যা $\Sigma=\{0,1\}$-এর উপর সংজ্ঞায়িত। বিশেষভাবে গুরুত্বপূর্ণ একটি স্ট্রিং হলো খালি স্ট্রিংEmpty string (ε)length শূন্যের একমাত্র স্ট্রিং — কোনো সিম্বল নেই। $\varepsilon$ — length শূন্যের একমাত্র স্ট্রিং, কোনো সিম্বল ছাড়াই।

২ · $\Sigma^*$ — Σ-এর Kleene Star

$\Sigma^*$Kleene Star of ΣΣ-এর উপর সম্ভাব্য সব স্ট্রিং-এর সেট — length ০ (ε) থেকে শুরু করে সীমাহীন length পর্যন্ত। হলো $\Sigma$-এর উপর সম্ভাব্য সব স্ট্রিং-এর সেট — $\varepsilon$ সহ, এবং যেকোনো length-এর স্ট্রিং সহ। $\Sigma$ নিজে ফাইনাইট হলেও, $\Sigma^*$-এর কোনো length-সীমা নেই — length ০, ১, ২, ৩... প্রতিটি length-এর জন্য নতুন স্ট্রিং যোগ হতে থাকে, ফলে $\Sigma^*$ একটি অসীম সেট। তবে এটি একটি বিশেষ ধরনের অসীম — countably infinite (গণনাযোগ্য অসীম): length অনুযায়ী সাজিয়ে (length ০-এর স্ট্রিং, তারপর length ১-এর সব স্ট্রিং, তারপর length ২...) প্রাকৃতিক সংখ্যার সাথে একটি ১-এর-সাথে-১ ম্যাপিং তৈরি করা যায়, যেহেতু প্রতিটি নির্দিষ্ট length-এ ফাইনাইট সংখ্যক স্ট্রিং থাকে ($|\Sigma|^n$টি length-$n$ স্ট্রিং)।

৩ · ল্যাঙ্গুয়েজ — Σ*-এর একটি সাবসেট

একটি ল্যাঙ্গুয়েজLanguageΣ*-এর যেকোনো সাবসেট — অর্থাৎ, একটি নির্দিষ্ট শর্ত পূরণ করা স্ট্রিং-এর একটি সংগ্রহ। (L, চিহ্নিত) হলো $\Sigma^*$-এর যেকোনো সাবসেট — $L \subseteq \Sigma^*$। যেহেতু $\Sigma^*$ অসীম, একটি ভাষা ফাইনাইট (যেমন $\{$"0","1"$\}$) বা ইনফাইনাইট (যেমন "জোড় length-এর সব স্ট্রিং") — দুটোই হতে পারে। কিন্তু এখানে একটি গভীর, গুরুত্বপূর্ণ প্রশ্ন আসে — $\Sigma^*$-এর সম্ভাব্য সাবসেট কতগুলো হতে পারে?

$\Sigma^*$ গণনাযোগ্য-অসীম হলেও, এর পাওয়ার সেট $\mathcal{P}(\Sigma^*)$ (অর্থাৎ, সম্ভাব্য সব ভাষার সেট) uncountably infinite (অগণনীয় অসীম) — এটি সরাসরি ক্যান্টরের ডায়াগোনাল আর্গুমেন্টের একটি ফলাফল (cardinality, discrete-math L11 দ্রষ্টব্য)। এখান থেকে একটি গভীর, গুরুত্বপূর্ণ পর্যবেক্ষণ আসে —

৪ · Python-এ Σ* ও ল্যাঙ্গুয়েজ

নিচের কোড সেলে একটি নির্দিষ্ট length-বাউন্ড পর্যন্ত $\Sigma^*$-এর একটি অংশ জেনারেট করা হচ্ছে, এবং একটি ছোট্ট Language ক্লাস দিয়ে membership ও concatenation দেখানো হচ্ছে।

import itertools

def generate_all_strings(alphabet, max_length):
    """Sigma-এর উপর length 0 থেকে max_length পর্যন্ত সব স্ট্রিং জেনারেট করে -- Sigma*-এর একটি ফাইনাইট প্রিফিক্স"""
    strings = []
    for length in range(max_length + 1):
        for tup in itertools.product(alphabet, repeat=length):
            strings.append(''.join(tup))
    return strings

alphabet = ['0', '1']
all_strings = generate_all_strings(alphabet, 3)

print("length | স্ট্রিংসমূহ                                   | count | 2^length")
print("-" * 70)
for length in range(4):
    strings_of_length = [s for s in all_strings if len(s) == length]
    count = len(strings_of_length)
    expected = 2 ** length
    display = strings_of_length if strings_of_length else ["ε (খালি স্ট্রিং)"]
    match = "মিলছে" if count == expected else "মিলছে না"
    print(f"{length:6d} | {str(display):44s} | {count:5d} | {expected:5d}  {match}")

print()
print(f"Sigma*-এর total স্ট্রিং (length 0-3): {len(all_strings)}")

class Language:
    """একটি ল্যাঙ্গুয়েজ -- Sigma*-এর একটি সাবসেট, স্ট্রিং-এর সেট হিসেবে বাস্তবায়িত"""
    def __init__(self, strings):
        self.strings = set(strings)

    def __contains__(self, w):
        return w in self.strings

    def concatenate(self, other):
        # L1.L2 = { xy : x in L1, y in L2 }
        return Language({x + y for x in self.strings for y in other.strings})

L1 = Language({'0', '1'})
L2 = Language({'0', '11'})
L1L2 = L1.concatenate(L2)

print()
print("L1 =", sorted(L1.strings))
print("L2 =", sorted(L2.strings))
print("L1 . L2 =", sorted(L1L2.strings))
print("'00' in L1.L2 ?", '00' in L1L2)
print("'111' in L1.L2 ?", '111' in L1L2)