রেগুলার এক্সপ্রেশন ও রেগুলার ল্যাঙ্গুয়েজ

Regular expressions & regular languages

৮ মিনিট পড়া মধ্যম · Intermediate Python কোডসহ সম্পূর্ণ বাংলায়

এক নজরে · TL;DR

রেগুলার এক্সপ্রেশন (Regex) একটি ভাষা বর্ণনা করার একটি প্যাটার্ন-ভাষা — খালি স্ট্রিং, একক সিম্বল, concatenation, union (|), এবং Kleene star (*) দিয়ে তৈরি।
Kleene's theorem: একটি ভাষা regular হয় যদি এবং কেবল যদি এটি কোনো DFA দিয়ে চেনা যায়, যদি এবং কেবল যদি এটি কোনো regex দিয়ে বর্ণনা করা যায় — DFA, NFA ও regex ঠিক একই ক্ষমতার তিনটি ভিন্ন ভাষা।
L34-এর "জোড় সংখ্যক 1" DFA-র ভাষাটিই regex 0*(10*10*)* দিয়ে হুবহু বর্ণনা করা যায় — কোডে DFA ও regex-এর উত্তর মিলিয়ে যাচাই করব।
Python-এর re মডিউল, grep, এবং প্রতিটি টেক্সট এডিটরের find-replace আসলে এই একই তত্ত্বের (আরও সমৃদ্ধ সংস্করণের) বাস্তবায়ন। তবে সব ভাষা regular নয় — যেমন balanced parentheses, যা চেনার জন্য "গণনা" দরকার, DFA-র সসীম মেমরি যা পারে না।

এই পাঠে যা শিখবেন

রেগুলার এক্সপ্রেশন কী কী মৌলিক উপাদান দিয়ে গঠিত (concatenation, union, Kleene star)
Kleene's theorem-এর বক্তব্য — DFA, NFA ও regex-এর সমতুল্যতা
L34-এর DFA-র ভাষাকে regex দিয়ে বর্ণনা করে দুটোর উত্তর মিলিয়ে দেখা
কেন সব ভাষা regular নয়, এবং Pumping Lemma-র ভূমিকা কী (সংক্ষেপে)

১ · রেগুলার এক্সপ্রেশনের মৌলিক উপাদান

একটি Regular ExpressionRegular Expressionএকটি প্যাটার্ন যা কয়েকটি মৌলিক নিয়ম (খালি স্ট্রিং, একক সিম্বল, concatenation, union, Kleene star) ব্যবহার করে স্ট্রিং-এর একটি সেট (ভাষা) বর্ণনা করে। নিচের মৌলিক উপাদান থেকে তৈরি হয় —

খালি স্ট্রিং ε
শুধু খালি স্ট্রিং-এর ভাষা $\{\varepsilon\}$ বর্ণনা করে

একক সিম্বল
যেমন 0 বা 1 — শুধু সেই একটি সিম্বলের ভাষা

Concatenation (AB)
A-এর একটি স্ট্রিং তারপর B-এর একটি স্ট্রিং — পরপর জোড়া লাগানো

Union (A|B)
A-এর কোনো স্ট্রিং অথবা B-এর কোনো স্ট্রিং

Kleene Star (A*)Kleene StarA-এর শূন্য বা তার বেশিবার (zero or more) পুনরাবৃত্তি — খালি স্ট্রিংও এর অন্তর্ভুক্ত।
A-এর শূন্য বা তার বেশিবার পুনরাবৃত্তি (repetition)

২ · Kleene's theorem — তিনটি সমতুল্য দৃষ্টিভঙ্গি

একটি গভীর ফলাফল (এখানে শুধু বক্তব্য বলা হলো, প্রমাণ এই কোর্সের সুযোগের বাইরে) —

Kleene's Theorem

একটি ভাষা $L$ regular হয় যদি এবং কেবল যদি —

(ক) $L$ কোনো DFA দিয়ে চেনা যায় (L34), ⟺ (খ) $L$ কোনো NFA দিয়ে চেনা যায় (L34), ⟺ (গ) $L$ কোনো regular expression দিয়ে বর্ণনা করা যায়।

অর্থাৎ — DFA, NFA ও regex এই তিনটি সম্পূর্ণ ভিন্ন দেখতে টুল আসলে ঠিক একই শ্রেণীর ভাষা বর্ণনা করতে পারে, একটির চেয়ে অন্যটি বেশি শক্তিশালী নয়।

৩ · Worked উদাহরণ — L34-এর DFA-কে regex দিয়ে বর্ণনা

L34-এ আমরা দেখেছি "জোড় সংখ্যক 1" চেনার একটি দুই-স্টেট DFA। এই একই ভাষা নিচের regex দিয়ে হুবহু বর্ণনা করা যায় —

Regex ⟺ DFA

$$0^*(10^*10^*)^*$$

অনানুষ্ঠানিকভাবে পড়লে: "শুরুতে যেকোনো সংখ্যক 0, তারপর শূন্য বা তার বেশিবার — প্রতিটিতে ঠিক দুটি 1 (মাঝে ও পাশে যেকোনো সংখ্যক 0 সহ)"। প্রতিটি (10*10*) ব্লক ঠিক দুটি নতুন 1 যোগ করে — তাই মোট 1-এর সংখ্যা সবসময় জোড় থাকে, ঠিক DFA-র মতোই।

Python

import re

pattern = r'0*(10*10*)*'

for s in ["1010", "111", "0", "11011"]:
    matched = bool(re.fullmatch(pattern, s))
    print(f"'{s}' -> regex match: {matched}")

# L34-এর DFA-র সাথে তুলনা (একই ফলাফল আসা উচিত)
delta = {
    ('q_even', '0'): 'q_even', ('q_even', '1'): 'q_odd',
    ('q_odd', '0'): 'q_odd',   ('q_odd', '1'): 'q_even',
}
def run_dfa(s):
    state = 'q_even'
    for ch in s:
        state = delta[(state, ch)]
    return state == 'q_even'

print()
for s in ["1010", "111", "0", "11011"]:
    dfa_result = run_dfa(s)
    regex_result = bool(re.fullmatch(pattern, s))
    print(f"'{s}': DFA={dfa_result}, regex={regex_result}, একমত={dfa_result == regex_result}")

Python-এর re মডিউল, grep, এবং প্রতিটি টেক্সট এডিটরের "find & replace" আসলে এই একই তত্ত্বের একটি সমৃদ্ধতর, বাস্তবিক (extended) বাস্তবায়ন — যদিও বাস্তব regex ইঞ্জিনে backreference-এর মতো কিছু ফিচার যোগ করা হয়েছে যা কঠোরভাবে regular নয়, মূল ইঞ্জিনের ভিত্তি এই একই DFA/NFA তত্ত্ব।

৪ · সব ভাষা regular নয়

একটি গুরুত্বপূর্ণ সীমাবদ্ধতা: সব ভাষা DFA/regex দিয়ে বর্ণনা করা যায় না। ক্লাসিক উদাহরণ — balanced parentheses (যেমন "(()())" বৈধ, কিন্তু "(()" নয়) — এই ভাষা চেনার জন্য "এখন পর্যন্ত কতগুলো খোলা bracket আছে" তা গণনা করতে হয়, এবং এই গণনা যেকোনো সীমা ছাড়িয়ে বাড়তে পারে। কিন্তু একটি DFA-র স্টেট সংখ্যা সসীম ও ফিক্সড — তাই এটি অসীম সংখ্যক ভিন্ন "কাউন্ট" আলাদা করতে পারে না।

একটি ভাষা non-regular তা প্রমাণ করার একটি প্রমিত টুল আছে — Pumping LemmaPumping Lemmaএকটি ভাষা non-regular তা প্রমাণ করার জন্য ব্যবহৃত একটি টেকনিক্যাল টুল — এই কোর্সে শুধু এর অস্তিত্বের কথা উল্লেখ করা হলো, বিস্তারিত ডেরিভেশন কভার করা হয়নি। — এই কোর্সে আমরা এর বিস্তারিত ডেরিভেশনে যাচ্ছি না, শুধু এতটুকু জেনে রাখুন যে এই সীমাবদ্ধতা প্রমাণ করার একটি আনুষ্ঠানিক পদ্ধতি বিদ্যমান।

মূল কথা · Key takeaway

DFA, NFA ও regex — তিনটি সম্পূর্ণ ভিন্ন দেখতে বর্ণনা পদ্ধতি — আসলে একই সীমারেখার (regular languages) তিনটি মুখ। L34-L35 একসাথে দেখায় কীভাবে একটি বিমূর্ত গাণিতিক মডেল (DFA) সরাসরি একটি ব্যবহারিক টুলে (regex) রূপান্তরিত হয়, যা প্রতিদিন কোটি কোটি প্রোগ্রামার ব্যবহার করেন — প্রায়ই না জেনেই যে তারা ১৯৫০-এর দশকের অটোমাটা তত্ত্ব ব্যবহার করছেন।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ regex 0*(10*10*)*-এ শুরুর 0*-টি না থাকলে কী সমস্যা হতো?

শুরুর 0* ছাড়া প্যাটার্নটি হতো (10*10*)*, যা এখনো খালি স্ট্রিং এবং "1" দিয়ে শুরু হওয়া বৈধ স্ট্রিং মেলে, কিন্তু "0" দিয়ে শুরু হওয়া কোনো স্ট্রিং মেলাতে পারবে না যদি না তার আগে অন্তত একটি সম্পূর্ণ (10*10*) ব্লক থাকে। যেমন ইনপুট "0" (একাই) মিলবে না, যদিও এতে শূন্যটি 1 আছে (জোড়) — DFA অনুযায়ী এটি accept হওয়া উচিত।

তাই শুরুর 0* জরুরি — এটি নিশ্চিত করে যে স্ট্রিং যেকোনো সংখ্যক 0 দিয়ে শুরু হতে পারে, প্রথম 1 আসার আগে। কোড সেলে "0"-এর জন্য regex ও DFA উভয়ে True দেয়, যা এই সঠিকতা যাচাই করে।

প্র ০২ Kleene's theorem বলে DFA, NFA ও regex সমতুল্য — তাহলে কেন প্রোগ্রামাররা DFA না লিখে regex লেখেন?

এক্সপ্রেসিভনেস তত্ত্বে সমান হলেও, ergonomics-এ সমান নয়। একটি regex একটি কমপ্যাক্ট, মানুষের পড়ার-উপযোগী নোটেশন — 0*(10*10*)* একলাইনে লেখা যায়, কিন্তু এর সমতুল্য DFA বর্ণনা করতে স্টেট, ট্রানজিশন টেবিল ইত্যাদি অনেক বেশি জায়গা নেয়।

বাস্তবে, regex ইঞ্জিন (যেমন Python-এর re) পর্দার পেছনে regex-কে NFA বা DFA-তে কম্পাইল করে চালায় — প্রোগ্রামার শুধু উচ্চ-স্তরের নোটেশন (regex) লেখেন, নিম্ন-স্তরের স্টেট মেশিন কম্পাইলার/ইন্টারপ্রেটার স্বয়ংক্রিয়ভাবে তৈরি করে। এটি ঠিক তেমন যেমন প্রোগ্রামাররা অ্যাসেম্বলি না লিখে উচ্চ-স্তরের ভাষা লেখেন।

প্র ০৩ "balanced parentheses" কেন non-regular কিন্তু "জোড় সংখ্যক 1" regular — দুটোই তো একধরনের গণনা মনে হয়?

পার্থক্যটি সূক্ষ্ম কিন্তু গুরুত্বপূর্ণ — "জোড় সংখ্যক 1"-এ শুধু প্যারিটি (জোড়/বিজোড়, মাত্র ২টি সম্ভাব্য অবস্থা) মনে রাখলেই যথেষ্ট, যা একটি সসীম DFA-তে ২টি স্টেট দিয়ে ধারণ করা যায়।

কিন্তু "balanced parentheses"-এ শুধু জোড়/বিজোড় জানলেই যথেষ্ট নয় — ঠিক কতগুলো খোলা bracket এখনো বন্ধ হয়নি তা জানতে হবে, এবং এই সংখ্যা ইনপুট যত লম্বা হয় তত আনবাউন্ডেডভাবে বাড়তে পারে (যেমন "((((("-এ পাঁচটি খোলা bracket আছে, আরও লম্বা ইনপুটে আরও বেশি হতে পারে)। একটি সসীম DFA-র স্টেট সংখ্যা ফিক্সড, তাই এটি অসীম সংখ্যক ভিন্ন "কাউন্ট" ধারণ করতে পারে না — এখানেই "সসীম" (finite) এবং "আনবাউন্ডেড" (unbounded) গণনার মধ্যে মৌলিক পার্থক্য।

অনুশীলন

হাতে যাচাই করুন: regex 0*(10*10*)* স্ট্রিং "1100"-এর সাথে মেলে কি না হাতে-কলমে বিশ্লেষণ করুন, তারপর কোড চালিয়ে মিলিয়ে দেখুন।

"1100"-এ দুটি 1 আছে (জোড়) — DFA অনুযায়ী accept হওয়া উচিত। বিশ্লেষণ: শুরুর 0* এখানে শূন্যবার প্রয়োগ হয় (কোনো leading 0 নেই), তারপর (10*10*) ব্লকটি "1", "1", তারপর "00" মেলায় (দ্বিতীয় 0* "00" ধরে নেয়) — পুরো স্ট্রিং মিলে যায়। কোড চালিয়ে re.fullmatch সত্যিই True দেয় কি না যাচাই করুন।
ডিজাইন করুন: "শুধু 0 দিয়ে শুরু হওয়া বাইনারি স্ট্রিং" (অর্থাৎ প্রথম ক্যারেক্টার অবশ্যই 0, বাকিটা যেকোনো কিছু) চেনার একটি regex লিখুন।

0(0|1)* — প্রথমে ঠিক একটি 0, তারপর 0 বা 1-এর যেকোনো সংখ্যক পুনরাবৃত্তি। লক্ষ্য করুন খালি স্ট্রিং এখানে মেলে না (কারণ প্রথম 0 বাধ্যতামূলক), এবং শুধু "1..." দিয়ে শুরু হওয়া কোনো স্ট্রিংও মেলে না।