✖

রেগুলার ভাষার ক্লোজার

আমাদের আছে একটি রেগুলার ভাষা L। আমরা প্রমাণ করব যে ভাষা L এর ক্লোজার আবার একটি রেগুলার ভাষা।

ভাষার ক্লোজার কী

ভাষা L এর ক্লোজারকে (ক্লিনি ক্লোজার, Kleene closure) আমরা লিখি L∗। ক্লোজারে আছে সেইসব স্ট্রিং, যা ভাষা L এর সসীম সংখ্যক স্ট্রিং জুড়ে বানানো যায়। ক্লোজারের সংজ্ঞা দেওয়া যায় এভাবে:

L∗={a1∘a2∘⋯∘an|ai∈L,n∈N0},

যেখানে ∘ হলো সংযুক্তি প্রক্রিয়া। ক্লোজারে ফাঁকা স্ট্রিংও আছে, অর্থাৎ ϵ।

আনুষ্ঠানিক পদ্ধতি

আমরা প্রায় ভাষার সংযুক্তির মতোই এগোব। পার্থক্য শুধু এই যে দুইটি ভিন্ন অটোমেটন না জুড়ে আমরা একটি অটোমেটনকেই নিজের সঙ্গে জুড়ব: অটোমেটনের চূড়ান্ত স্টেটগুলো থেকে অটোমেটনের প্রারম্ভিক স্টেটে এপসিলন ট্রানজিশন টানব। তবে ক্লোজারে ফাঁকা স্ট্রিংও থাকতে হবে। তা কীভাবে নিশ্চিত করব? প্রারম্ভিক স্টেটকে চূড়ান্ত স্টেট বানানো যেত। তখন অটোমেটন ফাঁকা স্ট্রিং গ্রহণ করত, কিন্তু আরও কোনো স্ট্রিংও গ্রহণ করে ফেলতে পারত। তাই এর বদলে আমরা একটি নতুন প্রারম্ভিক স্টেট তৈরি করি এবং এই নতুন প্রারম্ভিক স্টেট থেকে আগের প্রারম্ভিক স্টেটে একটি এপসিলন ট্রানজিশন টানি।

আমাদের আছে একটি রেগুলার ভাষা L1 এবং এই ভাষা গ্রহণকারী একটি অটোমেটন:

A1=⟨Q1,Σ1,δ1,q0,F1⟩

আমরা একটি অনির্ধারণমূলক অটোমেটন A = ⟨Q, Σ, δ, qs, F⟩ গঠন করি, যার জন্য:

  • Q = Q1 ∪ {qs}
  • Σ= Σ1
  • F = F1 ∪ {qs}

ট্রানজিশন ফাংশন δ এর সংজ্ঞা:

δ(q,a)={δ1(q,a)যদিq∈Q1∧q∉F1δ1(q,a)যদিq∈F1∧a≠ϵδ1(q,a)∪{q0}যদিq∈F1∧a=ϵ{q0}যদিq=qs∧a=ϵ∅যদিq=qs∧a≠ϵ

উদাহরণ

ধরি অটোমেটন A1 গ্রহণ করে স্ট্রিং 00 বা 11:

তাহলে ভাষা L(A1) এর ক্লোজার হলো 00 ও 11 জোড়া দিয়ে গঠিত সব স্ট্রিংয়ের ভাষা, যেমন 0000, 110011, 11110000 ইত্যাদি। এই ক্লোজার গ্রহণকারী অটোমেটন গঠন করতে আমরা একটি নতুন প্রারম্ভিক স্টেট qs তৈরি করতাম, যেখান থেকে আগের প্রারম্ভিক স্টেট q0 এ একটি এপসিলন ট্রানজিশন যায়, এবং স্টেট q3 ও q4 থেকে স্টেট q0 এ এপসিলন ট্রানজিশন যোগ করতাম:

যাচাই করে দেখতে পার, এই অটোমেটন সত্যিই 0000, 110011, 11110000 স্ট্রিংগুলো গ্রহণ করে, কিন্তু 1010 এর মতো স্ট্রিং গ্রহণ করে না।

তথ্যসূত্র

সূচিপত্র: রেগুলার ভাষার আবদ্ধতা ধর্ম, রেগুলার ভাষার সংযোগ, রেগুলার ভাষার ছেদ, রেগুলার ভাষার অন্তর, রেগুলার ভাষার পূরক, রেগুলার ভাষার সংযুক্তি, রেগুলার ভাষার ক্লোজার