Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۹:تئوری:سوال ۱۱

عبارت منظم

منظور از یک کلمه، یک دنباله‌ی متناهی از نویسه‌های a و b و c است. همچنین یک دنباله به طول صفر را نیز به عنوان یک کلمه در نظر می‌گیریم و با e نمایش می‌دهیم. برای مثال مجموعه کلمه‌های به طول یک، {a,b,c} است.

یک عبارت منظم، عبارتی استکه یک مجموعه از کلمه‌ها را مشخص می‌کند و به این صورت تعریف می‌شود:

۱) e یک عبارت منظم است که مجموعه‌ی {e} را مشخص می‌کند.

۲) a‌ و b‌ و c هر کدام یک عبارت منظم هستند که به ترتیب مجموعه‌های {a}، {b} و {c}‌را مشخص می‌کنند.

۳) اگر R‌یک عبارت منظم باشد که مجموعه‌ی S‌ را مشخص می‌کند، آن‌گاه:

  • (R) نیز یک عبارت منظم است که مجموعه‌ی S را مشخص می‌کند.
  • R نیز یک عبارت منظم است که مجموعه‌ی {w1w2...wk|wiS,k0} را مشخص می‌کند. توجه کنید که در تعریف فوق، k می‌تواند صفر باشد، بنابراین همواره eR.

۴) اگر R1 و R2 دو عبارت منظم باشند که به ترتیب مجموعه‌های S1 و S2 را مشخص می‌کنند آن‌گاه:

  • R1+R2 یک عبارت منظم است که مجموعه‌ی S1S2 را مشخص می‌کند.
  • R1R2 یک عبارت منظم است که مجموعه‌ی {w1w2|w1S1,w2S2} رامشخص می‌کند.

برای مثال، عبارت منظم (abc) مجموعه‌ی{bc,abc,aabc,...} را مشخص می‌کند.

مجموعه‌ی V از کلمه‌ها را مجموعه‌ای در نظر بگیرید که جمع تعداد a ها و تعداد b ها و دو برابر تعداد c‌ ها در آن بر ۳ بخش‌پذیر باشد.

عبارت منظمی بنویسید که مجموعه‌ی V را مشخص کند.


ابزار صفحه