نظریه زبان‌ها - ویکی‌پدیا، دانشنامهٔ آزاد

این مقاله دقیق، کامل و صحیح ترجمه نشده و نیازمند ترجمه به فارسی است. کل یا بخشی از این مقاله به زبانی به‌جز زبان فارسی نوشته شده‌است. اگر مقصود ارائهٔ مقاله برای مخاطبان آن زبان است، باید در نسخه‌ای از ویکی‌پدیا به همان زبان نوشته شود (فهرست ویکی‌پدیاها را ببینید). در غیر این صورت، خواهشمند است ترجمهٔ این مقاله را با توجه به متن اصلی و با رعایت سیاست ویرایش، دستور خط فارسی و برابر سازی به زبان فارسی بهبود دهید و سپس این الگو را از بالای صفحه بردارید. همچنین برای بحث‌های مرتبط، مدخل این مقاله در فهرست صفحه‌های نیازمند ترجمه به فارسی را ببینید. اگر این مقاله به زبان فارسی بازنویسی نشود، تا دو هفتهٔ دیگر نامزد حذف می‌شود و/یا به نسخهٔ زبانی مرتبط ویکی‌پدیا منتقل خواهد شد. اگر شما اخیراً این مقاله را به‌عنوان صفحهٔ نیازمند ترجمه برچسب زده‌اید، لطفاً عبارت {{جا:نیاز به ترجمه|صفحه=نظریه زبان‌ها |زبان=نامشخص |نظر= }} ~~~~ را به پایین این بخش از فهرست صفحه‌های نیازمند ترجمه به فارسی بیفزایید. لطفاً {{جا:هبک-ترجمه به فارسی|1=نظریه زبان‌ها}} ~~~~ را نیز در صفحهٔ بحث نگارنده قرار دهید.

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

نظریهٔ زبان‌ها به عنوان راهی برای درک قوانین نحوی زبان‌های طبیعی از زبان شناسی سرچشمه گرفت و نوام چامسکی در پیشرفت آن نقش مؤثری داشت. در علوم کامپیوتر، زبان‌های صوری به عنوان مبنایی برای تعریف دستور زبان‌های برنامه‌نویسی استفاده می‌شوند. در نظریهٔ پیچیدگی محاسباتی، مسائل تصمیم معمولاً به عنوان زبان‌های صوری تعریف می‌شوند و کلاس‌های پیچیدگی به عنوان مجموعه‌ای از زبان‌های صوری تعریف می‌شوند که می‌توانند توسط ماشین‌های تجزیه‌گر تجزیه شوند. در منطق، فرمالیسم ریاضی و مبانی ریاضی، از زبان‌های صوری برای تعریف دقیق نحو دستگاه‌های صوری همچون نظریهٔ مجموعه‌ها استفاده می‌شود.^[۱]

یک زبان صوری (به انگلیسی: formal language) شامل کلماتی است متشکل از حروف یک الفبا که بر اساس قوانینی به صورت خوش‌ساخت شکل بگیرند.^[۲]

در علوم کامپیوتر و ریاضیات که معمولاً با زبان‌های طبیعی سروکار ندارند، صفت «صوری» حذف می شود.^[۳] مفهوم گرامر صوری شباهت بیشتری به تصور انسانی از یک زبان دارد. زبانی که با قواعد نحوی محدود شده باشد.

تعاریف پایه[ویرایش]

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

زبان صوری[ویرایش]

هر مجموعه‌ای از رشته‌ها (یا کلمات) از یک الفبای خاص ${\displaystyle \Sigma }$ را یک زبان صوری ${\displaystyle L}$ در ${\displaystyle \Sigma }$ (یا بر روی ${\displaystyle \Sigma }$) می‌نامیم. به عبارتی دیگر ${\displaystyle L\subseteq \Sigma ^{*}}$ است.^[۱]

با این تعریف مجموعهٔ تهی نیز یک زبان (زبان تهی بر روی هر ${\displaystyle \Sigma }$ دلخواه) محسوب می‌شود. در یک زبان لزومی ندارد که از همهٔ حروف الفبا استفاده شود.^[۲]

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

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

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

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

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

• الحاق ${\displaystyle L_{1}\circ L_{2}}$^[۳] مجموعهٔ تمام رشته‌های حاصل از الحاق اعضای این دو است: ${\displaystyle L_{1}\cdot L_{2}=L_{1}L_{2}=\{vw:v\in L_{1}\land w\in L_{2}\}}$
• توان ${\displaystyle L^{n}}$ با ${\displaystyle n}$ بار الحاق ${\displaystyle L}$ در خودش به دست می‌آید: ${\displaystyle L^{n}=\overbrace {LL\cdots L} ^{n}}$همچنین ${\displaystyle L^{0}=\{\epsilon \}}$ تعریف می‌کنیم. توجه کنید که ${\displaystyle \{\epsilon \}\neq \varnothing }$.^[۲]
• معکوس ${\displaystyle L^{\mathcal {R}}}$ مجموعهٔ معکوس تمام رشته‌های زبان مذکور است: ${\displaystyle L^{\mathcal {R}}=\{w^{\mathcal {R}}\mid w\in L\}}$
• بستار کلین ${\displaystyle L^{*}}$ به صورت ${\displaystyle L^{*}=\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.