تعمیم دستور زبان مستقل‌ازمتن

تعمیم دستور زبان مستقل از متن (GCFC) گرامری است که با اضافه کردن توابع ترکیب که به صورت بالقوه غیر مستقل هستند، گرامر مستقل از متن را تعمیم می‌دهد. گرامر هد (و معادل‌های ضعیف آن) نمونه‌های از این نوع GCFC هستند که به صورت خاص برای پرداختن به انواع مختلفی از خصوصیات غیر CF زبان طبیعی به کار می‌رود.

توصیف ویرایش

GCFC شامل دو مؤلفه است: مجموعه‌ای از توابع ترکیب که تاپل‌های رشته‌ای را باهم ترکیب می‌کنند و مجموعه‌ای از قوانین بازنویسی. توابع ترکیب همگی به فرم $f(\langle x_{1},...,x_{m}\rangle ,\langle y_{1},...,y_{n}\rangle ,...)=\gamma$ هستند که در آن $\gamma$ تاپل رشته‌ای تکی یا استفاده خاصی از تابع ترکیب (به صورت بالقوه متفاوتی) است که به تاپل رشته کاهش می‌یابد. قوانین بازنویسی به صورت $X\to f(Y,Z,...)$ هستند که در آن Y، Z و ... تاپل‌های رشته‌ای یا نمادهای غیر پایانی هستند. سمانتیک بازنویسی GCFCها نسبتاً ساده است. وقوع نماد غیرپایانی با استفاده از قوانین بازنویسی مثل گرامر مستقل از متن بازنویسی می‌شود و در نهایت تنها ترکیبات را می‌دهد (توابع ترکیب اعمال شده به تاپل‌های رشته یا ترکیبات دیگر). سپس توابع ترکیب اعمال شده، بعد از آن کاهش می‌یابند و تاپل‌ها هم به یک تاپل کاهش می‌یابند.

مثال ویرایش

ترجمه ساده گرامر مستقل از متن به GCFC را می‌توان به صورت زیر انجام داد. با داشتن گرامر در (۱) که زبان دو طرفه $\{ww^{R}:w\in \{a,b\}^{*}\}$ را ایجاد می‌کند که در آن $w^{R}$ رشته معکوس $w$ است، می‌توان تابع ترکیب conc را به صورت (۲- الف) تعریف و قوانین را به صورت (۲-ب) بازنویسی کرد.

$S\to \epsilon ~|~aSa~|~bSb$
1. 1. $conc(\langle x\rangle ,\langle y\rangle ,\langle z\rangle )=\langle xyz\rangle$
2. $S\to conc(\langle \epsilon \rangle ,\langle \epsilon \rangle ,\langle \epsilon \rangle )~|~conc(\langle a\rangle ,S,\langle a\rangle )~|~conc(\langle b\rangle ,S,\langle b\rangle )$

حاصلضرب CF از abbbba به صورت زیر است:

S

aSa

abSba

abbSbba

abbbba

و حاصلضرب GCFC متناظر به صورت زیر است:

$S\to conc(\langle a\rangle ,S,\langle a\rangle )$

$conc(\langle a\rangle ,conc(\langle b\rangle ,S,\langle b\rangle ),\langle a\rangle )$

$conc(\langle a\rangle ,conc(\langle b\rangle ,conc(\langle b\rangle ,S,\langle b\rangle ),\langle b\rangle ),\langle a\rangle )$

$conc(\langle a\rangle ,conc(\langle b\rangle ,conc(\langle b\rangle ,conc(\langle \epsilon \rangle ,\langle \epsilon \rangle ,\langle \epsilon \rangle ),\langle b\rangle ),\langle b\rangle ),\langle a\rangle )$

$conc(\langle a\rangle ,conc(\langle b\rangle ,conc(\langle b\rangle ,\langle \epsilon \rangle ,\langle b\rangle ),\langle b\rangle ),\langle a\rangle )$

$conc(\langle a\rangle ,conc(\langle b\rangle ,\langle bb\rangle ,\langle b\rangle ),\langle a\rangle )$

$conc(\langle a\rangle ,\langle bbbb\rangle ,\langle a\rangle )$

$\langle abbbba\rangle$

سیستم‌های بازنویسی مستقل از متن خطی (LCFRSها) ویرایش

wier دو خصوصیت توابع ترکیب را بیان کرد: خطی بودن و منظم بودن. تابعی که به صورت $f(x_{1},...,x_{n})=...$ تعریف شده خطی است اگر و تنها اگر هر متغیر حداکثر یکبار در هر سمت = ظاهر شود و $f(x)=g(x,y)$ را خطی می‌کند اما $f(x)=g(x,x)$ را خطی نمی‌کند. تابع تعریف شده به صورت $f(x_{1},...,x_{n})=...$ منظم است اگر سمت چپ و سمت راست دقیقاً متغیرهای یکسانی داشته باشند این کار $f(x,y)=g(y,x)$ را منظم می‌کند اما $f(x)=g(x,y)$ یا $f(x,y)=g(x)$ را منظم نمی‌کند. گرامری که در آن همه توابع ترکیب هم خطی و هم منظم هستند سیستم بازنویسی مستقل از متن خطی (LCFRS) نامیده می‌شود. LCFRS زیرکلاس مناسبی از GCFGهاست یعنی در کل دقیقاً توان محاسباتی کمتری نسبت به GCFGها دارد. از سوی دیگر، LCFRSها اکیداً رساتر از گرامرهای اندیس شده خطی و معادل ضعیف آنها گرامرهای اتصال درختی (TAGها) هستند. گرامر هد مثال دیگری از LCFRS است که در کل اکیداً قدرت کمتری نسبت به کلاس LCFRSها دارد.