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

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

که دارای خاصیت‌های زیر می‌باشد:

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

فرض کنید ${\displaystyle MA{T}^{\lambda }}$

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

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

گرامر ${\displaystyle G=(\{S,X,Y\},\{a,b,c\},M,S,F)}$

این ماتریس‌ها که شامل قوانین زبان بدون محتوا می‌شوند، زبان زیر را تولید می‌کنند:

این مثال از اقتباس شده است.

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

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