আনুষ্ঠানিক ভাষা
আনুষ্ঠানিক ভাষা (formal language) হলো দৈনন্দিন জীবনের পরিচিত “ভাষা” ধারণার এক ধরনের সাধারণীকরণ।
মৌলিক ধারণা
শুরুতে আনুষ্ঠানিক ভাষাকে আমরা বাংলার মতো একটি সাধারণ ভাষা হিসেবে কল্পনা করতে পারি। এমন ভাষা কী দিয়ে গঠিত? শব্দ দিয়ে, আর শব্দগুলো জুড়ে আমরা বাক্য বানাই। বাক্য নিয়ে আমরা মাথা ঘামাব না, আমাদের আগ্রহ শুধু শব্দে। শব্দ কী দিয়ে গঠিত? বর্ণমালার বর্ণ দিয়ে। তাই বর্ণমালা দিয়েই শুরু করি।
বর্ণমালা (alphabet) হলো যেকোনো অশূন্য সেট। বর্ণমালার উপাদানগুলোকে আমরা প্রতীক বলি। বাংলার ক্ষেত্রে এটি হবে পরিচিত বাংলা বর্ণমালা: স্বরবর্ণ, ব্যঞ্জনবর্ণ, কার-চিহ্ন ও অন্যান্য চিহ্ন। বাংলার বদলে যদি সংখ্যা বর্ণনা করতে চাই, তাহলে বর্ণমালায় থাকবে দশটি অঙ্কের সবগুলো। বর্ণমালাকে প্রায়ই Σ প্রতীক দিয়ে প্রকাশ করা হয়।
স্ট্রিং (string) বা শব্দ (word) হলো কোনো বর্ণমালা Σ এর প্রতীকগুলোর একটি সসীম অনুক্রম। যেমন, বর্ণমালা Σ= {a,b,c,d,e,…, z} হলে “ahoj” বা “dobrman” অনুক্রমগুলো স্ট্রিং, কিন্তু “večer” স্ট্রিং নয় (বর্ণমালায় “č” বর্ণ নেই), “Honza” নয় (বর্ণ “H” নেই), “dobry den”-ও নয় (ফাঁকা জায়গা নেই)। স্ট্রিংয়ের দৈর্ঘ্য হলো স্ট্রিংটি যতগুলো প্রতীক দিয়ে গঠিত, তার সংখ্যা।
স্ট্রিং সংযুক্তি (concatenation): দুইটি স্ট্রিং a = a1a2… an ও b = b1b2… bm থাকলে এদের সংযুক্তিতে পাই স্ট্রিং ab = a1a2… anb1b2… bm। উদাহরণ: “ahoj” ও “dobrman” স্ট্রিং দুইটি জুড়ে পাই “ahojdobrman”। সংযুক্তি আমরা হয় একটি ছোট বৃত্ত দিয়ে লিখি, অর্থাৎ a ∘ b, নয়তো কোনো চিহ্নই দিই না, শুধু স্ট্রিংগুলো পরপর লিখে যাই।
ফাঁকা স্ট্রিংকে আমরা ε দিয়ে লিখি। এটি সেই স্ট্রিং, যার দৈর্ঘ্য শূন্য। স্ট্রিং a = a1… an এর সঙ্গে ফাঁকা স্ট্রিং ε জুড়লে আবার a স্ট্রিংটিই ফিরে পাই। অর্থাৎ a ∘ ε = a।
বর্ণমালা Σ এর ক্লোজার হলো বর্ণমালা Σ থেকে যত স্ট্রিং বানানো যায়, ফাঁকা স্ট্রিংসহ তাদের সবগুলোর সেট। ক্লোজারকে লিখি Σ∗। দ্বিমিক বর্ণমালা Σ= {0, 1} এর জন্য
কখনো কখনো বর্ণমালার ধনাত্মক ক্লোজারও ব্যবহার করা হয়। এটিও বর্ণমালা থেকে বানানো যায় এমন সব স্ট্রিংয়ের সেট, শুধু ফাঁকা স্ট্রিং বাদে। ধনাত্মক ক্লোজারকে লিখি Σ+, এবং Σ+ = Σ∗ ∖ {ε}।
বর্ণমালার উদাহরণ
-
বাংলার উদাহরণে ফিরে যাই। যে বর্ণমালায় সব স্বরবর্ণ, ব্যঞ্জনবর্ণ ও চিহ্ন আছে (সঙ্গে হয়তো হাইফেন “-”), তার ক্লোজারে যেকোনো বাংলা শব্দ পাওয়া যাবে। এই বর্ণমালায় ফাঁকা জায়গা ও যতিচিহ্ন (কমা, দাঁড়ি, বিস্ময়চিহ্ন, প্রশ্নচিহ্ন, …) যোগ করলে ক্লোজারে পাব বাংলায় লেখা যায় এমন সব বাক্য। অবশ্য এই ক্লোজারে “কখগট চছজ ঝঞটঠৎংঃঁ ড়ঢ়য় ক্ষক্ষ!!!:??: ::!?:?:ঘঙ” ধরনের অর্থহীন বাক্যও থাকবে।
-
আমাদের বর্ণমালায় সব অঙ্ক Σ= {0, 1, …, 9} থাকলে ক্লোজারে থাকবে সব স্বাভাবিক সংখ্যা, আর সঙ্গে আরও কিছু। সেখানে শূন্য দিয়ে শুরু হওয়া সংখ্যাও থাকবে, যেমন 00054, শুধু শূন্যও থাকবে, আর থাকবে ফাঁকা স্ট্রিং, যা অবশ্যই কোনো সংখ্যা নয়।
-
বর্ণমালা অশূন্য হতে হয়, তাই ক্ষুদ্রতম বর্ণমালায় অন্তত একটি প্রতীক থাকে। যেমন, বর্ণমালা Σ= {!} এর ক্লোজার হবে Σ∗ = {ε, !, !!, !!!, !!!!, …}, অর্থাৎ এমন স্ট্রিংয়ের সেট, যেখানে প্রত্যেক n ∈ ℕ0 এর জন্য n টি বিস্ময়চিহ্নের একটি স্ট্রিং আছে, আর অন্য কোনো স্ট্রিং ক্লোজারে নেই।
-
ধরি Σ= {qw,c}। এটি খুব অদ্ভুত বর্ণমালা, কারণ এতে স্ট্রিং qw আছে। এমন লেখা সাধারণত ব্যবহার করা হয় না, কারণ তা বিভ্রান্তিকর ও অস্বাভাবিক। তবে কল্পনা করা যায় যে “q” ও “w” বর্ণ দুইটি জোড়া লাগিয়ে একটি চিহ্ন বানানো হয়েছে। তখন স্ট্রিং “qw” কে আমরা প্রতীক “qw” হিসেবে দেখতে পারি। এই প্রতীক দিয়ে স্ট্রিং “qwcqw” বানালে এর দৈর্ঘ্য হবে তিন, কারণ এটি “qw”, “c” ও “qw” প্রতীক দিয়ে গঠিত। এমন বর্ণমালা খুব বেশি দেখা যায় না, কিন্তু কিছু ক্ষেত্রে একাধিক প্রতীক দিয়ে গঠিত এমন প্রতীক দরকার হয়।
আনুষ্ঠানিক ভাষা
বর্ণমালা Σ এর উপর (আনুষ্ঠানিক) ভাষা হলো Σ∗ এর যেকোনো উপসেট। তাই বর্ণমালা Σ এর উপর ভাষা L এর জন্য L ⊆ Σ∗। ভাষার কয়েকটি উদাহরণ:
-
আগের অংশে আমরা অঙ্কের বর্ণমালা Σ= {0, 1, …, 9} সংজ্ঞায়িত করেছি। এর ক্লোজারে আছে শুধু অঙ্ক দিয়ে গঠিত সব স্ট্রিং। যদি নিয়ম যোগ করি যে স্ট্রিং শূন্য দিয়ে শুরু হবে না এবং ফাঁকা হবে না, তাহলে পাই স্বাভাবিক সংখ্যার সেট ℕ। যেহেতু ℕ ⊆ Σ∗, তাই ℕ বর্ণমালা Σ এর উপর একটি ভাষা।
-
অঙ্কের আগের সেটে বিয়োগচিহ্ন “-” যোগ করাও যায়, তখন Σ= {0, 1, …, 9, −}। এর ক্লোজারে আছে অঙ্ক বা বিয়োগচিহ্ন দিয়ে গঠিত সব স্ট্রিং। কিন্তু তার মানে ক্লোজারে “12-84-”, “1-5-8” বা “-” এর মতো স্ট্রিংও আছে। পূর্ণ সংখ্যা ℤ এর ভাষা পেতে তিনটি নিয়ম যোগ করি:
- স্ট্রিংয়ে বিয়োগচিহ্ন হয় একেবারেই নেই, নয়তো আছে শুধু স্ট্রিংয়ের শুরুতে।
- স্ট্রিং “0” ছাড়া অন্য কোনো স্ট্রিংয়ের প্রথম অঙ্ক শূন্য হতে পারবে না।
- প্রত্যেক স্ট্রিংয়ে অন্তত একটি অঙ্ক থাকতে হবে।
এই সেট পূর্ণ সংখ্যার সেট বর্ণনা করে এবং এটি Σ∗ সেটের একটি উপসেট, তাই এটি বর্ণমালা Σ এর উপর একটি ভাষা।
-
ধরি Σ= {0, 1}। তাহলে ক্লোজারে আছে শূন্য ও এক দিয়ে গঠিত সব স্ট্রিং। এই বর্ণমালার উপর ভাষা L কে আমরা যেমন এভাবে সংজ্ঞায়িত করতে পারি: যেসব স্ট্রিংয়ে ঠিক তিনটি এক আছে, তাদের সেট। আরও সৃজনশীল হয়ে বলা যায়, ভাষা L হলো সেইসব স্ট্রিংয়ের সেট, যেগুলো বৈধ docx ফাইল (Word যা তৈরি করে)।
-
দ্বিমিক বর্ণমালা Σ= {0, 1} নিয়েই থাকি। যেকোনো অক্ষরের স্ট্রিং (কিবোর্ডে থাকা সাধারণ অক্ষর) দ্বিমিক রূপে, অর্থাৎ শূন্য ও একে রূপান্তর করা যায়, আবার ফিরিয়েও আনা যায়, যেমন ASCII সারণির সাহায্যে (আরও নিখুঁতভাবে বললে, ASCII সারণি অক্ষরকে সংখ্যায় রূপান্তর করে, আর দশমিক পদ্ধতির সংখ্যাকে দ্বিমিক পদ্ধতির সংখ্যায় রূপান্তর করা যায়)। তাই বৈধ ইমেইল ঠিকানার সব স্ট্রিংয়ের ভাষাও সংজ্ঞায়িত করা যায়, এবং সেটিও দ্বিমিক বর্ণমালার উপর একটি ভাষা।
ভাষার সংযুক্তি: ভাষাকেও জুড়ে দেওয়া যায়। সংজ্ঞাটি সেটের কার্তেসীয় গুণজের মতো। ধরি দুইটি ভাষা L1 ও L2। এদের সংযুক্তি L1 ∘ L2 থেকে পাই একটি নতুন ভাষা, যার সংজ্ঞা:
অর্থাৎ ভাষা L1 এর প্রত্যেক স্ট্রিংকে ভাষা L2 এর প্রত্যেক স্ট্রিংয়ের সঙ্গে জুড়ে দিই। উদাহরণ: ধরি
তাহলে
এ পর্যন্ত ভাষা বর্ণনা করতে আমরা সাধারণ ভাষা ব্যবহার করেছি, অর্থাৎ ভাষাটি দেখতে কেমন, তা কথায় বলেছি। কিন্তু এটি খুব অসুবিধাজনক, তাই ভাষা সংজ্ঞায়িত করার আরও আনুষ্ঠানিক উপায় চালু করা হয়। এর প্রথমটি হলো ব্যাকরণ (grammar)।