القواعد النحوية المتكررة

في علم الحاسوب ، يُطلق على القواعد النحوية اسم القواعد النحوية التكرارية إذا احتوت على قواعد إنتاج تكرارية ، أي أن توسيع رمز غير طرفي وفقًا لهذه القواعد يمكن أن يؤدي في النهاية إلى سلسلة تتضمن نفس الرمز غير الطرفي مرة أخرى. وإلا فإنها تُسمى قواعد نحوية غير تكرارية . ^{[ 1 ]}

على سبيل المثال، تكون قواعد اللغة الخالية من السياق ذات استدعاء ذاتي يساري إذا وُجد رمز غير طرفي A يمكن تطبيقه على قواعد الإنتاج لإنتاج سلسلة نصية يكون A فيها (كأقصى رمز على اليسار). ^{[ 2 ] [ 3 ]} جميع أنواع القواعد في تسلسل تشومسكي الهرمي قابلة للاستدعاء الذاتي، والاستدعاء الذاتي هو ما يسمح بإنتاج مجموعات لا نهائية من الكلمات. ^{[ 1 ]}

لا يمكن للقواعد النحوية غير الاسترجاعية أن تُنتج إلا لغةً محدودة؛ ويمكن لكل لغة محدودة أن تُنتج بواسطة قواعد نحوية غير استرجاعية. ^{[ 1 ]} على سبيل المثال، تُنتج القواعد النحوية الخطية كلمةً واحدةً فقط.

إن القواعد النحوية التكرارية الخالية من السياق والتي لا تحتوي على قواعد غير ضرورية تُنتج بالضرورة لغةً لانهائية. وتشكل هذه الخاصية أساسًا لخوارزمية يمكنها اختبار ما إذا كانت القواعد النحوية الخالية من السياق تُنتج لغةً محدودة أم لانهائية بكفاءة. ^{[ 4 ]}