توجه:

عناصر نظریه مجموعه‌ها:  رشته و زبان  آخرین ویرایش: ۱۳۹۵/۰۷/۰۱ 

عناصر نظریه مجموعه‌ها

۲۱.۱ رشته و زبان:

فرض کنید Σ یک مجموعه ناتهی باشد. پس از تعیین این مجموعه، آن را الفبا و اعضای آن را حروف الفبا نامیده. بناشده بر Σ مجموعه دیگری را معرفی می‌کنیم و اعضای آن را رشته می‌نامیم. بنای مجموعه اخیر را در دو گام به شرحی که در پی می‌آید انجام می‌دهیم.

هم‌افزایی
هم‌افزایی

در گام اول دنباله:

 <Σ, Σ1, ..., Σn , ...>

را بر پایه Σ ساخته. در گام دوم تعریف مجموعه موردنظر را تمام می‌کنیم.

گام یکم:

Σ۱                             
Σ۲={xy|x∈Σ, y∈Σ۱}
Σ۳={xy|x∈Σ, y∈Σ۲}
................
................
Σn={xy|x∈Σ, y∈Σn-1}
................
................
Σ={0, 1} 
Σ۱={0, 1}
Σ۲={ 00, 01, 10, 11}
Σ۳={000,001,010,011,100,101,000,001}
................
Σn={00...0,00...1, . . ., 11...1}; |Σn|=۲n.
................
................
مثال:

گام دوم:

اجتماع مجموعه‌های  Σ, Σ1, . . ., Σn , . . .  را +Σ نامیده و  اعضای آن را  رشته‌  می‌گوییم:

Σ+ = Σ Σ1 . . .Σn . . .

مثال: اگر Σ را ارقام ۱ تا ۹ بگیریم آنگاه Σ+ (یا رشته‌ها) اعداد طبیعی بدون رقم صفر خواهند بود. اگر Σ را حروف فارسی بگیریم آنگاه Σ+ عبارات ممکن (بامعنی و بی‌معنی، محدود و نامحدود) فارسی خواهد بود. و سرانجام اگر Σ مجموعه:

 Σ={p, q, ~, •, ,, ≡, (, )}

باشد آنگاه:

 p∨r   ;  ~pq))))))(q•∨⊃  ;  p⊃(p∨q)

هریک رشته‌های حاصل از الفبای Σ هستند.

 . مجموعه +Σ همیشه نامتناهی است؛ حتی اگر Σ فقط یک عضو داشته ‌باشد.

 . اگر Σ شمارا باشد با توجه به خواص شمارایی ، +Σ و نیز هر زیرمجموعه +Σ شمارا است.

 . مرسوم است نماد  'Λ' به‌عنوان یک حرف الفبا به نام حرف خالی برای هر Σ (الفبا) در نظر بگیرند.


مجموعه‌های بازگشتی

۱.۲۱.۱   پاره‌(یا قطعه) آغازی رشته:

اگر  S=s۱s۲...sn یک رشته‌ باشد، آنگاه به S'=s۱s۲...sm که در آن ۰≤m≤n یک پاره آغازی S می‌گوییم. اگر ۰<m<n به S' یک پاره آغازی سره  S و اگر m=۰ به S' پاره آغازین خالی S' می‌گوییم. بنابراین می‌توان از یک رشته با پاره آغازین خاصی نام برد.


۲.۲۱.۱   پاره‌ پایانی رشته:

اگر S=s۱s۲...sn یک رشته‌ باشد، آنگاه به S'=smsm+۱...sn که در آن ۰mn یک پاره پایانی S می‌گوییم. اگر  ۰<m<n به S' یک پاره پایانی سره S و اگر m=۰ به S' پاره پایانی خالی S' می‌گوییم. بنابراین می‌توان از یک رشته با پاره پایانی خاصی نام برد.


۳.۲۱.۱  الحاق رشته‌ها:

اگر S=s۱s۲...sn و  S'=s'۱s'۲...s'n رشته‌ باشند، به s۱s۲...sns'۱s'۲...s'm رشته حاصل از الحاق رشته S با S' گفته می‌شود. معمولاً عملگر الحاق را با  نشان می‌دهند. بنابراین:

SS'=s۱s۲...sns'۱s'۲...s'm


۴.۲۱.۱  عبارت و طول عبارت:

به رشته‌های‌‌ متناهی عبارت می‌گویند. اگر t یک عبارت باشد آنگاه طول عبارت را برابر تعداد حروف الفبای به‌کاررفته در آن می‌گیریم. طول رشته t را با |t| نشان می‌دهیم. بنابراین در آخرین مثال داریم؛ |p∨r|.

 .طول Λ (حرف خالی) را همیشه برابر صفر فرض می‌کنیم و نباید آن را با فاصله خالی (در صورت آنکه الفبا چنین حرفی را داشته باشد) یکی فرض کرد. برای مثال داریم:  |aΛbΛ|=|ab|=۲. ولی |aΛb Λ|=|ab|=۳.


 

۵.۲۱.۱  زبان:

در تمام آنچه در این بند آمد اگر به‌جای واژه الفبا عبارت واژگان ابتدایی را به‌کاربرده آنگاه به +Σ  یک زبان با واژگان ابتدایی Σ گفته می‌شود.


ادامه:

 

© 1987 - 2017 KHcc Sc.