✖

রেগুলার এক্সপ্রেশন

রেগুলার এক্সপ্রেশন (regular expression) হলো এমন একটি টেক্সট স্ট্রিং, যা দিয়ে স্ট্রিংয়ের কোনো একটি সেট বর্ণনা করা যায়। রেগুলার এক্সপ্রেশনকে আমরা সসীম অটোমেটন বর্ণনা করার একটি সহজ উপায় হিসেবেও দেখতে পারি।

রেগুলার এক্সপ্রেশন কী

পাটিগণিতে আমরা · ও + এর মতো প্রতীক দিয়ে রাশি গঠন করি, যেমন (2 + 3) · 4। এই রাশির মান নির্ণয় করলে একটি সংখ্যা পাই। রেগুলার এক্সপ্রেশন হলো অক্ষর ও কয়েকটি বিশেষ প্রতীকের একটি অনুক্রম, যেমন a(x ∪ y), যার মান নির্ণয় করলে পাই একটি (আনুষ্ঠানিক) ভাষা। রাশি (2 + 3) · 4 এর ফল সংখ্যা 20, আর রেগুলার এক্সপ্রেশন a(x ∪ y) এর ফল দুইটি স্ট্রিং “ax”, “ay” এর সেট।

আগের রেগুলার এক্সপ্রেশন a(x ∪ y) এর মান কীভাবে নির্ণয় করব? প্রত্যেক বর্ণ আসলে সেই বর্ণটি নিয়ে গঠিত এক উপাদানের সেটের সংক্ষিপ্ত রূপ, আর লুকানো গুণ হলো স্ট্রিং সংযুক্তি। রেগুলার এক্সপ্রেশনটিকে “পূর্ণ রূপে” এভাবে লেখা যেত:

{a}∘({x}∪{y})

এরপর মান নির্ণয় করতাম এভাবে: সংযোগ {x} ∪ {y} থেকে পাই ভাষা {x,y}। ভাষা {a} ও {x,y} এর সংযুক্তিতে পাই ভাষা {ax, ay}।

প্রোগ্রামিংয়ে রেগুলার এক্সপ্রেশন খুব বেশি ব্যবহৃত হয়, আর বেশির ভাগ প্রোগ্রামিং ভাষায় কোনো না কোনোভাবে রেগুলার এক্সপ্রেশন আছে। যেমন, ব্যবহারকারীর দেওয়া টেক্সট নির্দিষ্ট শর্ত পূরণ করে কি না (যেমন বৈধ ইমেইল, বৈধ তারিখ ইত্যাদি কি না), তা যাচাই করতে রেগুলার এক্সপ্রেশন ব্যবহার করা হয়। টেক্সট প্রতিস্থাপনেও এর ব্যবহার আছে (যেমন, টেক্সটে থাকা সব URL কে ক্লিকযোগ্য লিংকে বদলে দিতে চাইতে পারি)।

রেগুলার এক্সপ্রেশনের বাস্তব প্রয়োগগুলো সাধারণত এখানে বর্ণিত রেগুলার এক্সপ্রেশনের চেয়ে শক্তিশালী, আর এদের সিনট্যাক্স কিছুটা আলাদা, তবে প্রধানত বেশি জটিল।

রেগুলার এক্সপ্রেশনের সংজ্ঞা

রেগুলার এক্সপ্রেশনকে আমরা কোনো একটি বর্ণমালা Σ এর উপর সংজ্ঞায়িত করব। তাহলে আমরা বলি, রেগুলার এক্সপ্রেশন হলো:

  1. a, যেখানে a ∈ Σ। অর্থাৎ বর্ণমালার একটি অক্ষর নিজেই একটি রেগুলার এক্সপ্রেশন।
  2. ϵ: ফাঁকা স্ট্রিং, প্রোগ্রামিংয়ে একে খালি উদ্ধৃতিচিহ্ন “” দিয়েও লেখা হয়।
  3. ∅: রেগুলার এক্সপ্রেশনকে ফাঁকা ভাষাও বর্ণনা করতে পারতে হবে, তাই ফাঁকা ভাষা একটি রেগুলার এক্সপ্রেশন।
  4. (R1 ∪ R2), যেখানে R1, R2 রেগুলার এক্সপ্রেশন।
  5. (R1 ∘ R2), যেখানে R1, R2 রেগুলার এক্সপ্রেশন।
  6. (R∗), যেখানে R রেগুলার এক্সপ্রেশন।

চতুর্থ নিয়মের প্রতীক ∪ এর বদলে উল্লম্ব রেখার প্রতীক | ব্যবহার করাও চলে। প্রতীক ∘ এর বদলে কিছু না লিখলেও চলে। যেমন আমরা সাধারণত গুণের প্রতীক, অর্থাৎ মাঝের বিন্দু · সরাসরি লিখি না, তেমনি সংযুক্তির প্রতীক ∘ সাধারণত লিখিই না। তাই এই রেগুলার এক্সপ্রেশন দুইটি অভিন্ন: a ∘ (b ∪ c) ও a(b|c)।

আলাদা আলাদা অপারেটরের অর্থ কী?

  • ∪ বা | হলো ভাষার সংযোগ।
  • ∘ হলো ভাষার সংযুক্তি।
  • ∗ হলো ভাষার ক্লোজার।

উদাহরণ:

  • a হলো সরল ভাষা {a}।
  • a|b হলো দুইটি স্ট্রিং দিয়ে গঠিত ভাষা {a, b}।
  • a ∘ b হলো ভাষা {ab}।
  • a(b|c)d হলো ভাষা {abd, acd}।
  • a(b∗) হলো সেইসব স্ট্রিংয়ের ভাষা, যেগুলো বর্ণ “a” দিয়ে শুরু হয় এবং এরপর যেকোনো সংখ্যক বর্ণ “b” আসে।
  • (ab)∗ হলো সব স্ট্রিংয়ের ভাষা {ϵ, ab, abab, ababab, …}।
  • 0∗10∗ হলো সেইসব দ্বিমিক স্ট্রিংয়ের ভাষা, যাতে ঠিক একটি 1 আছে। (লক্ষ কর, আরও নিখুঁতভাবে এক্সপ্রেশনটি লেখা উচিত ছিল এভাবে: (0∗)1(0∗), কিন্তু বন্ধনী ছাড়াও লেখাটি পরিষ্কার বোঝা গেলে বন্ধনী বাদ দেওয়া যায়।)
  • Σ∗1Σ∗ হলো অন্তত একটি 1 আছে এমন সব স্ট্রিংয়ের ভাষা।
  • (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)∗ হলো সব স্বাভাবিক সংখ্যার ভাষা।

এরপর আমরা দেখাব যে রেগুলার এক্সপ্রেশন ও সসীম অটোমেটন সমতুল্য। অর্থাৎ কোনো রেগুলার এক্সপ্রেশনের মান যদি ভাষা R হয়, তবে এমন একটি সসীম অটোমেটন A আছে, যেন L(A) = R; উল্টোটাও সত্য।

তথ্যসূত্র

সূচিপত্র: রেগুলার এক্সপ্রেশন, রেগুলার এক্সপ্রেশন থেকে অটোমেটনে রূপান্তর, সাধারণীকৃত অনির্ধারণমূলক সসীম অটোমেটন, অটোমেটন থেকে রেগুলার এক্সপ্রেশনে রূপান্তর