ফরমাল ল্যাঙ্গুয়েজ ও গ্রামার পরিচিতি
এই পাঠে যা শিখবেন
- আলফাবেট, স্ট্রিং ও ফরমাল ল্যাঙ্গুয়েজের নির্দিষ্ট গাণিতিক সংজ্ঞা
- গ্রামার কী এবং কেন এটি "সসীম বর্ণনা দিয়ে অসীম ভাষা প্রকাশ করা"-র সমাধান
- এই মডিউলটি discrete-math কোর্সের ফরমাল-ল্যাঙ্গুয়েজ তত্ত্বের সাথে কীভাবে সম্পর্কিত
- Python-এ মেম্বারশিপ টেস্টিং ও একটি ছোট ভাষা সরাসরি জেনারেট করে যাচাই করা
১ · ফরমাল ল্যাঙ্গুয়েজ — স্ট্রিং-এর একটি সেট
একটি ফরমাল ল্যাঙ্গুয়েজFormal Languageএকটি নির্দিষ্ট আলফাবেটের ওপর স্ট্রিং-এর একটি (সম্ভবত অসীম) সেট। হলো একটি নির্দিষ্ট আলফাবেটের (চিহ্নের একটি সসীম সেট) ওপর স্ট্রিং-এর একটি (সম্ভবত অসীম) সেট। এই সংজ্ঞাটি এই কোর্সের সবচেয়ে গুরুত্বপূর্ণ ভিত্তিগুলোর একটি — একটি প্রোগ্রামিং ভাষার সিনট্যাক্স মূলত, তার মূলে, ঠিক এভাবেই সংজ্ঞায়িত: সেই ভাষার সব বৈধ প্রোগ্রাম গঠনকারী স্ট্রিং-এর সেট। L01-এ যখন আমরা বলেছিলাম একটি প্রোগ্রামিং ল্যাঙ্গুয়েজ "ফরমাল ও দ্ব্যর্থহীন," তখন এই "ফরমাল" শব্দটির সুনির্দিষ্ট গাণিতিক অর্থ এখন স্পষ্ট হলো।
২ · গ্রামার — সসীম নিয়মে অসীম ভাষা বর্ণনা
একটি গ্রামারGrammarনিয়মের একটি সসীম সেট যা একটি ফরমাল ল্যাঙ্গুয়েজের ঠিক সেই স্ট্রিংগুলোই নির্ভুলভাবে জেনারেট (বা রিকগনাইজ) করে। হলো নিয়মের একটি সসীম সেট যা একটি ভাষার অন্তর্গত ঠিক সেই স্ট্রিংগুলোই নির্ভুলভাবে জেনারেট (বা সমতুল্যভাবে, রিকগনাইজ) করে। এটি সরাসরি একটি স্বাভাবিক প্রশ্নের উত্তর: "কীভাবে একটি সম্ভাব্য-অসীম বৈধ প্রোগ্রামের সেটকে একটি সসীম বর্ণনা দিয়ে প্রকাশ করবেন?" — একটি ভাষায় অসীম সংখ্যক ভিন্ন প্রোগ্রাম লেখা সম্ভব (যেমন যত ইচ্ছা লম্বা একটি এক্সপ্রেশন), কিন্তু গ্রামারের নিয়মগুলো সবসময় সসীম সংখ্যক — এই সসীম নিয়মগুলোই M12 পর্যন্ত এই পুরো কোর্সের ভিত্তি।
ফরমাল ল্যাঙ্গুয়েজ ও অটোমাটা তত্ত্ব Discrete Mathematics কোর্সের (যদি নেওয়া হয়ে থাকে) একটি বিষয়বস্তুর সাথে সরাসরি ভাগাভাগি করা তাত্ত্বিক ভিত্তি — এই কোর্স সেই একই তত্ত্ব নির্দিষ্টভাবে প্রোগ্রামিং ভাষার সিনট্যাক্স ডিজাইন ও কম্পাইলার নির্মাণে প্রয়োগ করে। গভীর অটোমাটা-তাত্ত্বিক প্রমাণ ও জটিলতা এখানে পুনরায় derive করা হবে না — বরং M4 (লেক্সিক্যাল অ্যানালাইসিস) ও M5 (পার্সিং)-এ এই তত্ত্বের সরাসরি প্র্যাকটিক্যাল প্রয়োগ দেখানো হবে।
৩ · মৌলিক পরিভাষা — আলফাবেট, স্ট্রিং, ল্যাঙ্গুয়েজ
নির্দিষ্ট ফরমাল টার্মগুলো একসাথে দেখা যাক। একটি আলফাবেট $\Sigma$ হলো চিহ্নের একটি সসীম সেট (যেমন $\Sigma = \{0, 1\}$)। একটি স্ট্রিং হলো $\Sigma$ থেকে চিহ্নের একটি সসীম অনুক্রম। একটি ভাষা $L$ হলো $\Sigma$-এর ওপর স্ট্রিং-এর একটি সেট (সম্ভবত অসীম) — যেমন, দৈর্ঘ্য ঠিক ৩-এর সব বাইনারি স্ট্রিং-এর ভাষা নিচের মতো ফরমালি লেখা যায়:
$$L = \{\, w \in \Sigma^{*} \mid |w| = 3 \,\}$$
চিহ্নের একটি সসীম সেট, যেমন {0,1} বা {a,b,...,z}।
আলফাবেট থেকে চিহ্নের একটি সসীম অনুক্রম, যেমন "101"।
স্ট্রিং-এর একটি সেট (সম্ভবত অসীম), যেমন "দৈর্ঘ্য-৩ সব বাইনারি স্ট্রিং" — সসীম আকারেও গ্রামার এই সেট বর্ণনা করতে পারে।
৪ · কোড: মেম্বারশিপ টেস্টিং ও একটি টয় ভাষা জেনারেট করা
নিচের কোডে দুটি জিনিস দেখানো হয়েছে — প্রথমত, is_valid_string ফাংশনটি যাচাই করে একটি স্ট্রিং-এর
প্রতিটি ক্যারেক্টার একটি নির্দিষ্ট আলফাবেটের অন্তর্গত কি না। দ্বিতীয়ত, একটি সম্পূর্ণ টয় ভাষা — ঠিক দৈর্ঘ্য
৩-এর সব বাইনারি স্ট্রিং — সরাসরি itertools.product দিয়ে জেনারেট করে একটি Python set
হিসেবে রাখা হয়েছে, এবং তার আকার স্বাধীনভাবে গণনা করা $2^3$-এর সাথে মিলিয়ে যাচাই করা হয়েছে।
import itertools
def is_valid_string(s, alphabet):
"""স্ট্রিং s-এর প্রতিটি ক্যারেক্টার কি প্রদত্ত আলফাবেটের অন্তর্গত?"""
return all(ch in alphabet for ch in s)
alphabet = {"0", "1"}
# ভাষা L = দৈর্ঘ্য ঠিক ৩-এর সব বাইনারি স্ট্রিং -- সরাসরি জেনারেট করা হচ্ছে, হাতে লিখে নয়
language = {"".join(bits) for bits in itertools.product(alphabet, repeat=3)}
print(f"আলফাবেট Σ = {alphabet}")
print(f"ভাষার আকার |L| = {len(language)} (প্রত্যাশিত 2^3 = {2**3})")
print("\nসম্পূর্ণ ভাষা L:")
for s in sorted(language):
print(" ", s)
test_strings = ["101", "111", "12", "0000"]
print("\nমেম্বারশিপ ও আলফাবেট-বৈধতা টেস্ট:")
for s in test_strings:
valid_alphabet = is_valid_string(s, alphabet)
in_language = s in language
print(f" {s!r:8} valid_alphabet={valid_alphabet!s:5} in_language={in_language}")"0000"-এর প্রতিটি ক্যারেক্টার আলফাবেটের অন্তর্গত (valid_alphabet=True),
কিন্তু তবু in_language=False — কারণ ভাষা L নির্দিষ্টভাবে দৈর্ঘ্য ঠিক ৩-এর
স্ট্রিং-এর সেট, আর "0000"-এর দৈর্ঘ্য ৪। এটি একটি গুরুত্বপূর্ণ পার্থক্য স্পষ্ট করে: "আলফাবেটের
বৈধ চিহ্ন দিয়ে গঠিত হওয়া" এবং "একটি নির্দিষ্ট ভাষার সদস্য হওয়া" — এই দুটো ভিন্ন প্রশ্ন। উল্টোদিকে
"12"-এর "2" চিহ্নটি আলফাবেটেই নেই, তাই এটি স্বাভাবিকভাবেই দুটো টেস্টেই ব্যর্থ হয়।
একটি প্রোগ্রামিং ভাষার সিনট্যাক্স, তার সবচেয়ে বিমূর্ত স্তরে, স্রেফ একটি স্ট্রিং-এর সেট — এবং একটি গ্রামার হলো সেই (সম্ভবত অসীম) সেটের একটি সসীম বর্ণনা। M12/L12-এ আমরা দেখব কীভাবে BNF নোটেশন দিয়ে এই গ্রামারগুলো প্রকৃতপক্ষে লেখা হয়, এবং M15-এ দেখব বিভিন্ন ধরনের গ্রামার (রেগুলার, কনটেক্সট-ফ্রি ইত্যাদি) কীভাবে ভিন্ন ভিন্ন "শক্তি"-তে ভাষা বর্ণনা করতে পারে।
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।
প্র ০১ একটি প্রোগ্রামিং ভাষার সিনট্যাক্স "স্ট্রিং-এর একটি সেট" — এই সংজ্ঞা কেন কম্পাইলার ডিজাইনের জন্য গুরুত্বপূর্ণ, শুধু একটি তাত্ত্বিক কৌতূহল নয়?
কারণ এই সংজ্ঞাটিই প্রশ্নটাকে সুনির্দিষ্ট করে তোলে যা M5-এর একটি পার্সার আসলে সমাধান করে: "প্রদত্ত একটি স্ট্রিং, এটি কি এই ভাষা L-এর সদস্য?" — একটি সিনট্যাক্স-এরর আসলে ঠিক এই প্রশ্নের উত্তর "না।" যদি সিনট্যাক্স অস্পষ্টভাবে সংজ্ঞায়িত থাকত (যেমন স্বাভাবিক ভাষার ক্ষেত্রে হয়), "এই স্ট্রিংটি বৈধ কি না" প্রশ্নের কোনো নির্ভরযোগ্য, অ্যালগরিদমিক উত্তর সম্ভব হতো না — একটি পার্সার লেখাই অসম্ভব হয়ে যেত।
প্র ০২ কোড সেলে ভাষা L-এর আকার ঠিক ৮টি স্ট্রিং — একটি সসীম সংখ্যা। তাহলে "ফরমাল ল্যাঙ্গুয়েজ সম্ভবত অসীম হতে পারে" কথাটির প্রাসঙ্গিকতা কোথায়?
কোড সেলের উদাহরণটি ইচ্ছাকৃতভাবে সসীম রাখা হয়েছে (শুধু দৈর্ঘ্য-৩ স্ট্রিং) যাতে পুরো ভাষাটি সরাসরি জেনারেট
ও প্রিন্ট করে দেখানো যায়। কিন্তু একটি বাস্তব প্রোগ্রামিং ভাষার ক্ষেত্রে কোনো সর্বোচ্চ দৈর্ঘ্যের সীমা নেই —
"যেকোনো দৈর্ঘ্যের বৈধ এক্সপ্রেশন"-এর ভাষা সত্যিকার অর্থেই অসীম (যেমন 1+1+1+... যত ইচ্ছা
লম্বা করা যায়)। তাই একটি বাস্তব গ্রামারকে অসীম সংখ্যক স্ট্রিং তালিকাভুক্ত না করে, সসীম নিয়ম দিয়ে সেই
অসীম সেট বর্ণনা করতে হয় — যা ঠিক পরের পাঠ (L12, BNF/EBNF) থেকে দেখানো শুরু হবে।
প্র ০৩
কোড সেলে itertools.product(alphabet, repeat=3) ব্যবহার করা হয়েছে। এটি যদি repeat=2 করা হতো, ভাষার আকার কত হতো?
2^2 = 4 — মোট চারটি স্ট্রিং: "00", "01", "10", "11"। সাধারণভাবে, একটি n-চিহ্নের আলফাবেটের
ওপর ঠিক দৈর্ঘ্য-k-এর ভাষার আকার হয় $n^k$ — এখানে আলফাবেটের আকার (n=2, শুধু "0" ও "1") আর
দৈর্ঘ্য (k) দুটোর ওপরই ভাষার আকার সূচকীয়ভাবে (exponentially) নির্ভর করে, যা দেখায় কেন এমনকি সীমিত-দৈর্ঘ্যের
ভাষাও দ্রুত অনেক বড় হয়ে যেতে পারে।
অনুশীলন
-
পরীক্ষা করুন: উপরের কোডে
itertools.product(alphabet, repeat=3)-এর বদলেrepeat=4করে Run চাপুন — নতুন|L|কত হবে?|L| = 2^4 = 16— মোট ১৬টি ভিন্ন দৈর্ঘ্য-৪ বাইনারি স্ট্রিং জেনারেট হবে ("0000" থেকে "1111" পর্যন্ত)। কোডেরprint(f"...প্রত্যাশিত 2^3...")লাইনটিতেও তখন2**3-এর বদলে2**4লিখতে হবে যাতে "প্রত্যাশিত" মানটিও সঠিকভাবে মিলিয়ে দেখায় — নাহলে প্রিন্ট করা বার্তায় ভুল প্রত্যাশিত মান দেখাবে, যদিও প্রকৃতlen(language)ঠিকই ১৬ হবে। -
চিন্তা করুন: যদি
alphabet = {"0", "1", "2"}(তিন-চিহ্নের আলফাবেট) করা হয়,repeat=3রেখে দিলে ভাষার আকার কত হবে (কোড না চালিয়ে হিসাব করুন)?3^3 = 27— কারণ প্রতিটি অবস্থানে (৩টি অবস্থান) এখন ৩টি সম্ভাব্য চিহ্ন বসতে পারে ("0", "1", বা "2"), ফলে3 × 3 × 3 = 27ভিন্ন সমন্বয় সম্ভব। এটি প্র-০৩-এর সূত্র $n^k$-এর সরাসরি প্রয়োগ, এখানে n=3 (আলফাবেটের আকার) এবং k=3 (স্ট্রিং-এর দৈর্ঘ্য)।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- কোর্সের সম্পূর্ণ সিলেবাস দেখুন ৫৮টি পাঠ M3 সিনট্যাক্স ও গ্রামার মডিউলের বাকি পাঠগুলো দেখুন — BNF/EBNF, কনটেক্সট-ফ্রি গ্রামার ও চমস্কি হায়ারার্কি।
- Discrete Mathematics কোর্স তাত্ত্বিক পূর্বসূরি ফরমাল ল্যাঙ্গুয়েজ ও অটোমাটা তত্ত্বের গভীর গাণিতিক ভিত্তি সেই কোর্সে কভার করা হয়েছে — এই কোর্স সেই তত্ত্ব সরাসরি কম্পাইলার ডিজাইনে প্রয়োগ করে।
- আগের পাঠ L10 মাল্টি-প্যারাডাইম ল্যাঙ্গুয়েজ ও প্যারাডাইম বেছে নেওয়া — M2 মডিউলের সমাপনী পাঠ।
- পরের পাঠ L12 BNF ও EBNF নোটেশন — এই পাঠের "গ্রামার" ধারণাকে একটি কংক্রিট, লেখার-যোগ্য নোটেশনে রূপান্তর করা হবে।