گرامر حساس به متن
این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. (ژانویه ۲۰۱۵) |
گرامر حساس به متن گرامری است که سمت چ‍‍پ و سمت راست هر قوانین آن ممکن است توسط نمادهای پایانی و غیر پایانی احاطه شده باشد. گرامرهای حساس به متن نسبت به گرامرهای مستقل از متن عمومی تر هستند چرا که بعضی از زبان‌ها شاید نتوان با گرامر مستقل از متن نشان داده شوند اما با گرامر حساس به متن بیان می‌توان بیان کرد. گرامر حساس به متن نسبت به گرامر نامحدود کمتر حالت عمومی دارد؛ یعنی CSGها موقعیت میانی بین گرامرهای مستقل از متن و نامحدود در سلسه مراتب چامسکی را پر می‌کنند. زبان رسمی که توسط گرامرحساس به متن نشان داده می‌شود - به‌طور معادل (هم ارز) , توسط آتاماتای خطی کران‌دار-زبان حساس به متن نامیده می‌شود. بعضی از کتاب‌ها CSGها را به صورت گرامر غیر متعامد نیز تعریف می‌کنند. این مدل تعریف کردن هیچ تفاوتی در نظریه زبان‌ها به وجود نمی‌آورد (یعنی هر دو تعریف هم ارز بسیار ضعیفی دارند) اما این تفاوت را در نظریه اینکه کدام گرامرها به‌طور ساختاری حساس به متن در نظر گرفته شده‌است وجود دارد. در ادامه متن آنالیز چامسکی در سال ۱۹۶۳ گفته می‌شود.[۱][۲][۳] والتر ساویچ اصطلاح حساس به متن را گمراه کننده خوانند و اصطلاح غیر پاک شونده را پیشنهاد کرد که بهتر تفاوت بین CSG و گرامر نامحدود را مشخص کند. اگر چه اینکه ویژگی‌ها خاصی از زبان (مانند وابستگی متقابل سریال) مستقل از متن نیستند؛ اما یک سؤال پژوهشی وجود دارد که گرامر مستقل از متن چه مقدار قدرت بیان لازم را دارد تا حساسیت متن موجود در زبان طبیعی را بیابد. تحقیقات بعدی در این منطقه بیشتر روی محاسبات زبان ملایم حساس به متن تمرکز دارد.
تعریف رسمی
ویرایشگرامر G به این صورت تعریف می‌شود که G = (N, Σ, P, S)که در آن N مجموعه متغیرهای گرامر و Ʃ مجموعه ترمیتال‌ها و P مجموعه قوانین و Sنماد آغاز گر گرامر است. در گرامر حساس به متن تمام قوانین در P به صورت زیر است: αAβ → αγβ
که
A ∈ N α,β ∈ (N∪Σ)* and γ ∈ (N∪Σ)+. زبان گرامر G مجموعه ایی از همهٔ رشته‌های با نماد ترمینال‌ها که از نماد شروع مشتق می‌شود است. L(G) = { w ∈ Σ*: S ⇒* w }.
تنها تفاوت بین این تعریف از چامسکی و گرامر بدون محدودیت آن است که γ می‌تواند در گرامر بدون محدودیت تهی باشد. اسم حساس به متن αو β که فرم A را نشان می‌دهند بیان می‌شود؛ و تعیین می‌کند آیا A می‌تواند با γ جایگزین شود یا خیر. این قاعده متفاوت ازگرامر مستقل از متن است که در آن متن از غیر ترمینال‌ها مورد توجه قرار گرفته‌است. در واقع هر قاعده تولید از گرامر مستقل از متن به فرم است که v یک نماد تک غیر ترمینال است و w یک رشته از ترمینال‌ها است؛ w می‌تواند خالی باشد.
مثال
ویرایشگرامر زیر با نماد s شروع شده و استاندارد زبان غیر مستقل از متن زیر را ساخته است. { anbncn: n ≥ ۱ }
| 1. | S | → | a | b | c | ||
| 2. | S | → | a | S | B | c | |
| 3. | c | B | → | W | B | ||
| 4. | W | B | → | W | X | ||
| 5. | W | X | → | B | X | ||
| 6. | B | X | → | B | c | ||
| 7. | b | B | → | b | b |
قواعد ۱ و ۲ s را به
قواعد ۱و ۲
s
را به
an(Bc)n تبدیل می‌کند
قاعده ۷ برای آن است B را با b جایگزین کند. یک زنجیره تولید برای aaabbbccc به صورت زیر است:
S →2 aSBc →2 aaSBcBc →1 aaabcBcBc →3 aaabWBcBc →4 aaabWXcBc →5 aaabBXcBc →6 aaabBccBc →3 aaabBcWBc →4 aaabBcWXc →5 aaabBcBXc →6 aaabBcBcc →3 aaabBWBcc →4 aaabBWXcc →5 aaabBBXcc →6 aaabBBccc →7 aaabbBccc →7 aaabbbccc
پا نوشته‌ها
ویرایش- ↑ Peter Linz (2011). An Introduction to Formal Languages and Automata. Jones & Bartlett Publishers. p. 291. ISBN 978-1-4496-1552-9.
- ↑ Alexander Meduna (2000). Automata and Languages: Theory and Applications. Springer Science & Business Media. p. 730. ISBN 978-1-85233-074-3.
- ↑ Martin Davis; Ron Sigal; Elaine J. Weyuker (1994). Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science (2nd ed.). Morgan Kaufmann. p. 189. ISBN 978-0-08-050246-5.
جستارهای وابسته
ویرایش