نظریه زبان‌ها: تفاوت میان نسخه‌ها

محتوای حذف‌شده محتوای افزوده‌شده

درخط

نسخهٔ ‏۸ مهٔ ۲۰۱۵، ساعت ۲۱:۵۹

زبان صوری در ریاضیات، منطق و دانش رایانه، به زبانی که با فرمول‌های دقیقِ ریاضیاتی و قابل پردازش برای ماشین تعریف شده‌اند، زبان‌های فُرمال یا زبان‌های صوری گفته می‌شود.

به‌طورکلی در این رشته‌ها، زبان‌ها به دو دستهٔ فرمال و طبیعی تقسیم‌بندی می‌شوند. زبان‌های فرمال زبان‌هایی هستند که توسط گرامرها تولید می‌شوند یا ماشینی برای ارزیابی آنها وجود دارد.

تعاریف پایه

نماد: کوچک‌ترین و بنیادی‌ترین عضو یک زبان است. برخی مواقع به نمادها حرف هم گفته می‌شود. نمادها را معمولاً با حروف لاتین کوچک مثل a b و... نشان می‌دهند.
الفبا: یک مجموعه متناهی از نمادها که در یک زبان تعریف شده‌اند. الفبای زبان توسط Σ نشان داده می‌شود.
رشته: دنباله‌ای از نمادهای یک مجموعه الفباست که با عمل الحاق به هم پیوسته‌اند.

رشته ممکن است متناهی یا غیر متناهی باشد. طول یک رشته برابر است با تعداد نمادهایی که رشته را تشکیل می‌دهند. طول رشته را با قدر مطلق آن نمایش می‌دهند. مثلاً:

اگر w=aabbbbc آنگاه طول رشته ( |w| ) برابر است با هفت. زیرا این رشته با هفت نماد ساخته شده‌است.

زبان: مجموعه‌ای از رشته‌هاست. این مجموعه می‌تواند متناهی، نامتناهی شمارا یا نامتناهی ناشمارا باشد.

زبان بدون رشته را با Ø نشان می‌دهند.

رشته‌ای به طول صفر را با λ یا ε نشان می‌دهند. آن را رشتهٔ تهی می‌نامند.

دسته‌بندی زبان‌های فرمال

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

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

زبان مجموعه‌ای از رشته‌هاست. بنابر این ماهیت زبان‌ها، مجموعه است. همهٔ عملگرهایی که روی مجموعه‌ها تعریف شده اند مانند اجتماع، اشتراک، متمم، تفاضل و... روی زبان‌ها قابل تعریف هستند.

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

عملگرهای دیگری مانند عمل معکوس‌سازی (Reverse) نیز روی رشته‌های زبان قابل تعریف است.

تعریف

یک زبان صوری $L\!$ برروی یک الفبای $\Sigma \!$ عبارت است از یک زیرمجموعه از $\Sigma ^{*}\!$

پانوشته‌ها

منابع

An Introduction to Formal Languages and Automata، Peter Linz

Sudkamp, T. A., An Introduction to the Theory of Computer Science, Languages and Machines, 3rd ed., Pearson Education, Inc., 2006. ISBN 0-321-32221-5 [۱]

الگو:زبان‌ها و گرامرهای صوری

@@ خط ۱: / خط ۱: @@
-در [[ریاضیات]]، [[منطق]] و دانش [[رایانه]]، به زبانی که با فرمول‌های دقیق ریاضیاتی و قابل پردازش برای ماشین تعریف شداند، '''زبان‌های فُرمال''' یا '''زبان‌های صوری''' گفته می‌شود.
+'''زبان صوری''' در [[ریاضیات]]، [[منطق]] و دانش [[رایانه]]، به زبانی که با فرمول‌های دقیقِ ریاضیاتی و قابل پردازش برای ماشین تعریف شده‌اند، '''زبان‌های فُرمال''' یا '''زبان‌های صوری''' گفته می‌شود.
-به طور کلی در این رشته‌ها، زبان‌ها به دو دسته فرمال و طبیعی تقسیم بندی می‌شوند . زبان‌های فرمال زبان هایی هستند که توسط گرامرها تولید می‌شوند یا ماشینی برای ارزیابی آنها وجود دارد .
+به‌طورکلی در این رشته‌ها، زبان‌ها به دو دستهٔ فرمال و طبیعی تقسیم‌بندی می‌شوند. زبان‌های فرمال زبان‌هایی هستند که توسط گرامرها تولید می‌شوند یا ماشینی برای ارزیابی آنها وجود دارد.
 == تعاریف پایه ==
-* [[نماد]] : کوچک‌ترین و بنیادی‌ترین عضو یک زبان است . برخی مواقع به نمادها حرف هم گفته می‌شود . نمادها را معمولاً با حروف لاتین کوچک مثل a ، b و ... نشان می‌دهند .
+* [[نماد]]: کوچک‌ترین و بنیادی‌ترین عضو یک زبان است. برخی مواقع به نمادها حرف هم گفته می‌شود. نمادها را معمولاً با حروف لاتین کوچک مثل a  b و... نشان می‌دهند.
-* الفبا : یک مجموعه متناهی از نمادها که در یک زبان تعریف شده‌اند . الفبای زبان توسط Σ نشان داده می‌شود .
+* الفبا: یک مجموعه متناهی از نمادها که در یک زبان تعریف شده‌اند. الفبای زبان توسط Σ نشان داده می‌شود.
-* رشته : دنباله‌ای از نمادهای یک مجموعه الفباست که با عمل الحاق به هم پیوسته‌اند .
+* رشته: دنباله‌ای از نمادهای یک مجموعه الفباست که با عمل الحاق به هم پیوسته‌اند.
-رشته ممکن است متناهی یا غیر متناهی باشد . طول یک رشته برابر است با تعداد نمادهایی که رشته را تشکیل می‌دهند . طول رشته را با قدر مطلق آن نمایش می‌دهند . مثلاً :
+رشته ممکن است متناهی یا غیر متناهی باشد. طول یک رشته برابر است با تعداد نمادهایی که رشته را تشکیل می‌دهند. طول رشته را با قدر مطلق آن نمایش می‌دهند. مثلاً:
-اگر w=aabbbbc آنگاه طول رشته ( |w| ) برابر است با هفت . زیرا این رشته با هفت نماد ساخته شده است .
+اگر w=aabbbbc آنگاه طول رشته ( |w| ) برابر است با هفت. زیرا این رشته با هفت نماد ساخته شده‌است.
-* زبان : مجموعه‌ای از رشته‌ها است . این مجموعه می‌تواند متناهی، نامتناهی شمارا یا نامتناهی ناشمارا باشد .
+* زبان: مجموعه‌ای از رشته‌هاست. این مجموعه می‌تواند متناهی، نامتناهی شمارا یا نامتناهی ناشمارا باشد.
-زبان بدون رشته را با Ø نشان می‌دهند .
+زبان بدون رشته را با Ø نشان می‌دهند.
-رشته‌ای به طول صفر را با λ یا ε نشان می‌دهند . آن را [[رشته تهی]] می نامند .
+رشته‌ای به طول صفر را با λ یا ε نشان می‌دهند. آن را [[رشته تهی|رشتهٔ تهی]] می‌نامند.
 == دسته‌بندی زبان‌های فرمال ==
-زبان‌های فرمال به چهار دسته تقسیم می‌شوند :
+زبان‌های فرمال به چهار دسته تقسیم می‌شوند:
 * [[زبان‌های منظم]]
 * [[زبان‌های مستقل از متن]]
@@ خط ۲۷: / خط ۲۷: @@
 == عملگرهای روی زبان‌های فرمال ==
-زبان مجموعه‌ای از رشته هاست . بنابر این ماهیت زبان‌ها، مجموعه است . همه عملگر هایی که روی مجموعه‌ها تعریف شده اند مانند اجتماع، اشتراک، متمم، تفاضل و ... روی زبان‌ها قابل تعریف هستند .
+زبان مجموعه‌ای از رشته‌هاست. بنابر این ماهیت زبان‌ها، مجموعه است. همهٔ عملگرهایی که روی مجموعه‌ها تعریف شده اند مانند اجتماع، اشتراک، متمم، تفاضل و... روی زبان‌ها قابل تعریف هستند.
-[[الحاق (نظریه ماشین‌ها)|عملگر الحاق]] که روی رشته‌ها تعریف شده است، روی زبان‌ها نیز قابل تعریف است .
+[[الحاق (نظریه ماشین‌ها)|عملگر الحاق]] که روی رشته‌ها تعریف شده‌است، روی زبان‌ها نیز قابل تعریف است.
-عملگرهای دیگری مانند عمل معکوس سازی ( Reverse ) نیز روی رشته‌های زبان قابل تعریف است .
+عملگرهای دیگری مانند عمل معکوس‌سازی (Reverse) نیز روی رشته‌های زبان قابل تعریف است.
 == تعریف ==
-یک زبان صوری <math>L \!</math> برروی یک الفبای <math>\Sigma \!</math> عبارت است از یک زیر مجموعه از <math>\Sigma^{*} \!</math>
+یک زبان صوری <math>L \!</math> برروی یک الفبای <math>\Sigma \!</math> عبارت است از یک زیرمجموعه از <math>\Sigma^{*} \!</math>
 == پانوشته‌ها ==