For faster navigation, this Iframe is preloading the Wikiwand page for
تعمیم دستور بافتآزاد.
تعمیم دستور بافتآزاد
تعمیم دستور زبان مستقل از متن (GCFC) گرامری است که با اضافه کردن توابع ترکیب که به صورت بالقوه غیر مستقل هستند، گرامر مستقل از متن را تعمیم میدهد. گرامر هد (و معادلهای ضعیف آن) نمونههای از این نوع GCFC هستند که به صورت خاص برای پرداختن به انواع مختلفی از خصوصیات غیر CF زبان طبیعی به کار میرود.
GCFC شامل دو مؤلفه است: مجموعهای از توابع ترکیب که تاپلهای رشتهای را باهم ترکیب میکنند و مجموعهای از قوانین بازنویسی. توابع ترکیب همگی به فرم هستند که در آن تاپل رشتهای تکی یا استفاده خاصی از تابع ترکیب (به صورت بالقوه متفاوتی) است که به تاپل رشته کاهش مییابد. قوانین بازنویسی به صورت هستند که در آن Y، Z و ... تاپلهای رشتهای یا نمادهای غیر پایانی هستند. سمانتیک بازنویسی GCFCها نسبتاً ساده است. وقوع نماد غیرپایانی با استفاده از قوانین بازنویسی مثل گرامر مستقل از متن بازنویسی میشود و در نهایت تنها ترکیبات را میدهد (توابع ترکیب اعمال شده به تاپلهای رشته یا ترکیبات دیگر). سپس توابع ترکیب اعمال شده، بعد از آن کاهش مییابند و تاپلها هم به یک تاپل کاهش مییابند.
ترجمه ساده گرامر مستقل از متن به GCFC را میتوان به صورت زیر انجام داد. با داشتن گرامر در (۱) که زبان دو طرفه را ایجاد میکند که در آن رشته معکوس است، میتوان تابع ترکیب conc را به صورت (۲- الف) تعریف و قوانین را به صورت (۲-ب) بازنویسی کرد.
wier دو خصوصیت توابع ترکیب را بیان کرد: خطی بودن و منظم بودن. تابعی که به صورت تعریف شده خطی است اگر و تنها اگر هر متغیر حداکثر یکبار در هر سمت = ظاهر شود و را خطی میکند اما را خطی نمیکند. تابع تعریف شده به صورت منظم است اگر سمت چپ و سمت راست دقیقاً متغیرهای یکسانی داشته باشند این کار را منظم میکند اما یا را منظم نمیکند.
گرامری که در آن همه توابع ترکیب هم خطی و هم منظم هستند سیستم بازنویسی مستقل از متن خطی (LCFRS) نامیده میشود. LCFRS زیرکلاس مناسبی از GCFGهاست یعنی در کل دقیقاً توان محاسباتی کمتری نسبت به GCFGها دارد.
از سوی دیگر، LCFRSها اکیداً رساتر از گرامرهای اندیس شده خطی و معادل ضعیف آنها گرامرهای اتصال درختی (TAGها) هستند. گرامر هد مثال دیگری از LCFRS است که در کل اکیداً قدرت کمتری نسبت به کلاس LCFRSها دارد.
LCFRS به صورت ضعیف معادل با TAGهای چند ترکیبی (MCTAGها) و همچنین با گرامر مستقل از متن چندگانه (MCFGها (۱)) و گرامرهای مینیمالیست
(MGها) است. زبانهای ایجاد شده با LCFRS (و معادلهای ضعیف آنها) را میتوان به چند جملهای زمانی تجزیه کرد.
هر دستهای از زبانها، به جز آنهایی که با علامت ستاره علامتگذاری شدهاند، زیرمجموعه مناسبی از دستهای است که مستقیماً در بالای آن قرار دارد. هر زبانی، در هر دسته، به وسیله یک دستور زبان و یک اتومیشن در آن دسته و در سطر مشابه تولید میشود.
This browser is not supported by Wikiwand :( Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience. Please download and use one of the following browsers:
Your input will affect cover photo selection, along with input from other users.
X
Get ready for Wikiwand 2.0 🎉! the new version arrives on September 1st! Don't want to wait?
Oh no, there's been an error
Please help us solve this error by emailing us at support@wikiwand.com
Let us know what you've done that caused this error, what browser you're using, and whether you have any special extensions/add-ons installed.
Thank you!