قواعد نحوية غير مقيدة

في نظرية الأتمتة ، فإن فئة القواعد النحوية غير المقيدة (والتي تسمى أيضًا قواعد شبه ثوي أو قواعد النوع 0 أو قواعد بنية العبارة ) هي الفئة الأكثر عمومية من القواعد النحوية في هرم تشومسكي . لا يتم فرض أي قيود على إنتاج قواعد نحوية غير مقيدة، بخلاف كون كل جانب من جوانبها اليسرى غير فارغ. ^{[1] : 220} يمكن لهذه الفئة النحوية توليد لغات قابلة للعد بشكل متكرر .

القواعد النحوية غير المقيدة هي قواعد نحوية رسمية ، حيث ${\textstyle G=(N,T,P,S)}$

• ${\displaystyle N}$هي مجموعة محدودة من الرموز غير النهائية ،
• ${\displaystyle T}$هي مجموعة محدودة من الرموز الطرفية مع و منفصلة ، ^{​​[ملاحظة 1]}${\displaystyle N}$${\displaystyle T}$
• ${\displaystyle P}$هي مجموعة محدودة من قواعد الإنتاج من النموذج حيث و هي سلاسل من الرموز في و ليست السلسلة الفارغة، و${\displaystyle \alpha \to \beta ,}$${\displaystyle \alpha }$${\displaystyle \beta }$${\displaystyle N\cup T}$${\displaystyle \alpha }$

• ${\displaystyle S\in N}$هو رمز بداية مخصص خصيصًا. ^{[1] : 220}

كما يوحي الاسم، لا توجد قيود حقيقية على أنواع قواعد الإنتاج التي يمكن أن تمتلكها القواعد النحوية غير المقيدة. ^{[ملاحظة 2]}

تتميز القواعد النحوية غير المقيدة باللغات القابلة للعد بشكل متكرر. وهذا يشبه القول بأنه لكل قواعد نحوية غير مقيدة توجد آلة تورينج قادرة على التعرف والعكس صحيح. وفي حالة القواعد النحوية غير المقيدة، فإن مثل هذه الآلة التورينجية بسيطة بما يكفي لبنائها، مثل آلة تورينج غير حتمية ذات شريطين . ^{[1] : 221} يحتوي الشريط الأول على الكلمة المدخلة التي سيتم اختبارها، ويستخدم الشريط الثاني بواسطة الآلة لتوليد أشكال الجملة من . ثم تقوم آلة تورينج بما يلي: ${\displaystyle G}$${\displaystyle L(G)}$${\displaystyle w}$${\displaystyle G}$

1. ابدأ من يسار الشريط الثاني واختر بشكل متكرر التحرك إلى اليمين أو تحديد الموضع الحالي على الشريط.
2. اختر بشكل غير حتمي إنتاجًا من الإنتاجات الموجودة في .${\displaystyle \beta \to \gamma }$${\displaystyle G}$
3. إذا ظهر في موضع ما على الشريط الثاني، فاستبدله بـ في تلك النقطة، مع إمكانية تحريك الرموز على الشريط إلى اليسار أو اليمين اعتمادًا على الأطوال النسبية لـ و (على سبيل المثال، إذا كان أطول من ، حرك رموز الشريط إلى اليسار).${\displaystyle \beta }$${\displaystyle \beta }$${\displaystyle \gamma }$${\displaystyle \beta }$${\displaystyle \gamma }$${\displaystyle \beta }$${\displaystyle \gamma }$
4. قارن بين صيغة الجملة الناتجة على الشريط 2 والكلمة على الشريط 1. إذا تطابقت، فإن آلة تورينج تقبل الكلمة. وإذا لم تتطابق، فإن آلة تورينج ستعود إلى الخطوة 1.

من السهل أن نرى أن آلة تورينج هذه سوف تولد جميع أشكال الجملة فقط على شريطها الثاني بعد تنفيذ الخطوة الأخيرة عددًا عشوائيًا من المرات، وبالتالي يجب أن تكون اللغة قابلة للترقيم بشكل متكرر. ${\displaystyle G}$${\displaystyle L(G)}$

البناء العكسي ممكن أيضًا. بالنظر إلى بعض آلات تورينج، من الممكن إنشاء قواعد نحوية غير مقيدة مكافئة ^{[1] : 222} والتي تستخدم حتى الإنتاجات التي تحتوي على رمز واحد أو أكثر غير نهائي على جانبها الأيسر. لذلك، يمكن دائمًا تحويل قواعد نحوية غير مقيدة تعسفية بشكل مكافئ لتطيع الشكل الأخير، عن طريق تحويلها إلى آلة تورينج والعكس صحيح. يستخدم بعض المؤلفين ^{[ بحاجة لمصدر ]} الشكل الأخير كتعريف لقواعد نحوية غير مقيدة .

إن مشكلة القرار بشأن ما إذا كان من الممكن إنشاء سلسلة معينة بواسطة قواعد نحوية غير مقيدة معينة تعادل مشكلة ما إذا كان من الممكن قبولها بواسطة آلة تورينج المكافئة للقواعد النحوية. تسمى المشكلة الأخيرة مشكلة التوقف وهي غير قابلة للحسم. ${\displaystyle s}$

اللغات القابلة للعد بشكل متكرر تكون مغلقة تحت نجمة كليين ، والتسلسل ، والاتحاد ، والتقاطع ، ولكن ليس تحت فرق المجموعة ؛ راجع اللغات القابلة للعد بشكل متكرر#خصائص الإغلاق .

إن تكافؤ القواعد النحوية غير المقيدة مع آلات تورينج يعني وجود قواعد نحوية غير مقيدة عالمية، قواعد نحوية قادرة على قبول أي لغة قواعد نحوية غير مقيدة أخرى مع إعطاء وصف للغة. ولهذا السبب، من الممكن نظريًا بناء لغة برمجة تعتمد على قواعد نحوية غير مقيدة (على سبيل المثال Thue).

• حساب لامدا
• نظام شبه ثو – لا يميز بين الرموز الطرفية وغير الطرفية، ويسمح بوجود جوانب فارغة على الجانب الأيسر