گرامر ماتریسی

یک گرامر ماتریسی (انگلیسی:Matrix grammar), یک گرامر منظم است که در آن به جای قانون‌های تکی، قانون‌ها در دنباله‌های متناهی باهم گروه شده‌اند. یک قانون نمی‌تواند به صورت مجزا اعمال شود، بلکه هر قانون به صورت دنباله‌ای از قانون‌ها اعمال می‌شود. به عنوان مثال برای اعمال یک قانون چندین بار باید بازنویسی انجام شود، به این صورت که ابتدا قانون اول انجام می‌شود سپس قانون دوم و به همین ترتیب تا آخرین قانون پیش می‌رود. این دنباله از قانون‌ها در یک ماتریس نمایش داده می‌شود.

گرامر ماتریسی گسترشی از گرامر بدون محتوا است.

تعریف دقیق

یک گرامر ماتریسی یک پنج‌تایی مرتب به صورت زیر است: الگو:چپ‌چین

$G=(N,T,M,S,F).$

الگو:پایان چپ‌چین که دارای خاصیت‌های زیر می‌باشد:

• $N$ مجموعه همه ناپایانه‌ها است.
• $T$ مجموعه همه پایانه‌ها است.
• $S$ سمبل شروعی است که تمام متن از آن حاصل می‌شود و باید در [مجموعه] N حضور داشته باشد.
• $M=\{m_1,m_2,...,m_n\}$ یک مجموعه از دنباله‌های متناهی از قوانین زبان بدون محتوا است.
• $F$ یک زیرمجموعه از قوانینی است که در ماتریس‌ها وجود دارند.

خصیصه‌ها

فرض کنید $MA{T}^{\lambda }$ مجموعه زبان‌هایی باشد که با گرامر ماتریسی تولید می‌شود و $MAT$ مجموعه زبان‌هایی باشد که با گرامر ماتریسی بدون $\lambda$ تولید می‌شود.

خصیصه های زیر وجود دارد:

• به طور کلی، $MAT$ زیر مجموعه‌ای از $MA{T}^{\lambda }$ است.
• همه زبان‌های موجود در $MAT$ می‌توانند با یک گرامر حساس به محتوا تولید شوند.
• همه‌ی زبان‌های بدون محتوا در $MAT$ هستند.
• $MAT$ نسبت به اجتماع، اشتراک و به دنبال هم چسباندن برای زبان‌های منظم بسته است.
• هر زبانی که با گرامر ماتریسی تولید می‌شود که فقط یک پایانه دارد، منظم است.

مثال

گرامر $G=(\{S,X,Y\},\{a,b,c\},M,S,F)$ را در نظر بگیرید که در آن M مجموعه ماتریس‌های زیر است:

الگو:چپ‌چین [S → XY], [X → aXb, Y → cY], [X → ab, Y → c] الگو:پایان چپ‌چین این ماتریس‌ها که شامل قوانین زبان بدون محتوا می‌شوند، زبان زیر را تولید می‌کنند: الگو:چپ‌چین $L=\{a^n{b}^n{c}^n|n>0\}$ الگو:پایان چپ‌چین این مثال از اقتباس شده است.

مسئله حل‌نشده

دوتا مسئله در زمینه این‌گونه گرامرها همچنان به صورت حل‌نشده باقی مانده است.

• آیا زبانی وجود دارد که در $MA{T}^{\lambda }$ باشد اما در $MAT$ نباشد؟
• آیا $MA{T}^{\lambda }$ شامل همه‌ی زبان‌های غیرحساس به محتوا می‌شود؟

منابع

• Simple Matrix Languages OSCAR H. IBARmالگو:پیوند مرده