■ رشته و زبان
فرض کنید Σ یک مجموعه ناتهی باشد. پس از تعیین این مجموعه، آن را الفبا و اعضای آن را حروف الفبا نامیده. بناشده بر Σ مجموعه دیگری را معرفی می‌کنیم و اعضای آن را رشته می‌نامیم. بنای مجموعه اخیر را در دو گام به شرحی که در پی می‌آید انجام می‌دهیم.
در گام اول دنباله:
<Σ, Σ۱, ..., Σn , ...>
را بر پایه Σ ساخته. در گام دوم تعریف مجموعه موردنظر را تمام می‌کنیم.
گام یکم:
| Σ۱=Σ Σ۲={xy|x∈Σ, y∈Σ۱} Σ۳={xy|x∈Σ, y∈Σ۲} ................ ................ Σn={xy|x∈Σ, y∈Σn-۱} ................ ................ | Σ={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. ................ ................ | مثال: |
گام دوم:
اجتماع مجموعه‌های Σ, Σ۱, . . ., Σn , . . . را +Σ نامیده و اعضای آن را رشته می‌گوییم:
Σ+ = Σ∪ Σ۱∪ . . .∪Σn ∪. . .
مثال: اگر Σ را ارقام ۱ تا ۹ بگیریم آنگاه Σ+ (یا رشته‌ها) اعداد طبیعی بدون رقم صفر خواهند بود. اگر Σ را حروف فارسی بگیریم آنگاه Σ+ عبارات ممکن (بامعنی و بی‌معنی، محدود و نامحدود) فارسی خواهد بود. و سرانجام اگر Σ مجموعه:
Σ={p, q, ~, •, ∨,⊃, ≡, (, )}
باشد آنگاه:
p∨r ; ~pq))))))(q•∨⊃ ; p⊃(p∨q)
هریک رشته‌های حاصل از الفبای Σ هستند.
◄ . مجموعه +Σ همیشه نامتناهی است؛ حتی اگر Σ فقط یک عضو داشته باشد.
◄ . اگر Σ شمارا باشد با توجه به خواص شمارایی ، +Σ و نیز هر زیرمجموعه +Σ شمارا است.
◄ . مرسوم است نماد 'Λ' به‌عنوان یک حرف الفبا به نام حرف خالی برای هر Σ (الفبا) در نظر بگیرند.
نشان می‌دهند. بنابراین:
