نظریه زبان‌ها

الفبای صوری مجموعهٔ حروفی (مثل الف، ب، پ و ...) به نام نماد است که با قرارگیری آنها در کنار هم (الحاقشان) کلماتی به نام رشته پدید می‌آیند. هر کلمهٔ صوری از به هم پیوستن حروف این الفبا به دست می‌آید. مثلاً کلمهٔ «آب» (با حروف آ + ب) به زبان فارسی تعلق دارد ولی در عربی معنا ندارد (با این وجود الفبای آنها یکسان است). گاهی کلماتی که به یک زبان صوری خاص تعلق دارند جمله یا فرمول‌های خوش‌فرم نامیده می شوند.

هر مجموعه‌ای از رشته‌ها (یا کلمات) از یک الفبای خاص ${\displaystyle \mathrm{\Sigma }}$

با این تعریف مجموعهٔ تهی نیز یک زبان (زبان تهی بر روی هر ${\displaystyle \mathrm{\Sigma }}$

گاهی برای توصیف زبان‌ها از دستور زبان صوری استفاده می‌شود و در این مواقع یک زبان را مجهز به یک گرامر فرض می‌کنیم: ${\displaystyle \mathcal{L}=(L,G)}$

اعمال روی زبان‌ها

ماهیت زبان‌ها مجموعه است؛ در نتیجه اعمال مجموعه‌ها (تفاضل، اجتماع، اشتراک و تفاضل متقارن) روی آنها نیز تعریف می‌شود:

• کاردینالیتی (تعداد اعضای) اکثر زبان‌ها بی‌نهایت است.
• متمم یک زبان ${\displaystyle L}$
  روی الفبای ${\displaystyle \mathrm{\Sigma }}$
  برابر است با ${\displaystyle \overline{L}={\mathrm{\Sigma }}^{\ast }\mathrm{\setminus }L}$
  .

همچنین اعمال روی رشته‌ها و الفبا نیز روی زبان‌ها قابل تعمیم است:

• الحاق ${\displaystyle L_1\circ L_2}$
  مجموعهٔ تمام رشته‌های حاصل از الحاق اعضای این دو است: ${\displaystyle L_1\cdot L_2=L_1{L}_2=\{vw:v\in L_1\wedge w\in L_2\}}$
• توان ${\displaystyle L^n}$
  با ${\displaystyle n}$
  بار الحاق ${\displaystyle L}$
  در خودش به دست می‌آید: ${\displaystyle L^n=\stackrel{n}{\overbrace{LL\cdots L}}}$
  همچنین ${\displaystyle L^0=\{ϵ\}}$
  تعریف می‌کنیم. توجه کنید که ${\displaystyle \{ϵ\}\ne \varnothing }$
  .
• معکوس ${\displaystyle L^{\mathcal{R}}}$
  مجموعهٔ معکوس تمام رشته‌های زبان مذکور است: ${\displaystyle L^{\mathcal{R}}=\{w^{\mathcal{R}}\mid w\in L\}}$
• بستار کلین ${\displaystyle L^{\ast }}$
  به صورت ${\displaystyle L^{\ast }=\bigcup _{n\in \mathbb{N}}{L}^n=L^0\cup L^1\cup L^2\cup \cdots }$
  تعریف می‌کنیم.
• همچنین بستار مثبت ${\displaystyle L^{+}}$
  را به این شکل تعریف می‌کنیم: ${\displaystyle L^{+}=\bigcup _{n\in {\mathbb{N}}^{\star }}{L}^n=L^1\cup L^2\cup \cdots }$

برای تولید یا توصیف یک زبان از گرامر صوری، اتوماتا، عبارات باقاعده (به انگلیسی: regex) یا مدل‌های محاسباتی استفاده می‌شود.

مسئلهٔ تصمیم معادل عضویت در یک زبان صوری است. مجموعهٔ همهٔ رشته‌هایی که یک اتوماتا می‌پذیرد (یا یک گرامر تولید می‌کند یا با یک عبارت باقاعده تطابق دارند) یک زبان است. همچنین پذیرش یک رشته توسط یک ماشین معادل عضویت آن در زبان مذکور است. بنابراین نظریه زبان‌ها بسیار با نظریهٔ ماشین‌ها مرتبط است و همچنین یک حوزه کاربردی اصلی در نظریه رایانش‌پذیری و نظریهٔ پیچیدگی محاسباتی است.

زبان‌های صوری را می‌توان به کمک وراثت چامسکی بر اساس قدرت مولد (گرامر) آنها و یا پیچیدگی اتوماتای تصمیم آنها طبقه بندی کرد.

• نظریه زبان
• رشته (علوم رایانه)
• تحلیل واژگان
• تجزیه‌کننده
• نظریه (منطق ریاضی)
• دستگاه صوری

1. ↑ An Introduction to Formal Languages and Automata (Sixth Edition). به کوشش Peter Linz.
2. ↑ Introduction to Automata Theory, Languages, and Computation (Third Edition). به کوشش John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman.
3. ↑ Introduction to the Theory of Computation (Third Edition). به کوشش Michael Sipser.