معضلة الضخ للغات الخالية من السياق

في علوم الحاسوب ، وخاصة في نظرية اللغة الرسمية ، فإن مبرهنة الضخ للغات الخالية من السياق ، والمعروفة أيضًا باسم مبرهنة بار-هيلل ، ^{[ 1 ]} هي مبرهنة تعطي خاصية مشتركة بين جميع اللغات الخالية من السياق وتعمم مبرهنة الضخ للغات المنتظمة .

يمكن استخدام معضلة الضخ لبناء دحض بالتناقض مفاده أن لغة معينة ليست خالية من السياق. في المقابل، لا تكفي معضلة الضخ لضمان أن اللغة خالية من السياق؛ فهناك شروط ضرورية أخرى، مثل معضلة أوجدن ، أو معضلة التبادل .

إذا كانت لغة${\displaystyle L}$إذا كانت خالية من السياق، فإنه يوجد عدد صحيح ما${\displaystyle p\geq 1}$(يُطلق عليه "طول الضخ") ^{[ 2 ]} بحيث يكون كل وتر${\displaystyle s}$في${\displaystyle L}$الذي يبلغ طوله${\displaystyle p}$أو رموز أكثر (أي مع${\displaystyle |s|\geq p}$يمكن كتابة ) على النحو التالي

$${\displaystyle s=uvwxy}$$

مع السلاسل الفرعية${\displaystyle u,v,w,x}$و${\displaystyle y}$بحيث

1. ${\displaystyle |vx|\geq 1}$،
2. ${\displaystyle |vwx|\leq p}$، و
3. ${\displaystyle uv^{n}wx^{n}y\in L}$للجميع${\displaystyle n\geq 0}$.

فيما يلي تعبير رسمي عن معضلة الضخ.

$${\displaystyle {\begin{array}{l}(\forall L\subseteq \Sigma ^{*})\\\quad ({\mbox{context free}}(L)\Rightarrow \\\quad ((\exists p\geq 1)((\forall s\in L)((|s|\geq p)\Rightarrow \\\quad ((\exists u,v,w,x,y\in \Sigma ^{*})(s=uvwxy\land |vx|\geq 1\land |vwx|\leq p\land (\forall n\geq 0)(uv^{n}wx^{n}y\in L)))))))\end{array}}}$$

تصف نظرية الضخ للغات الخالية من السياق (والتي تسمى فقط "نظرية الضخ" لبقية هذه المقالة) خاصية تضمن وجودها في جميع اللغات الخالية من السياق.

تنطبق هذه الخاصية على جميع السلاسل النصية في اللغة التي يبلغ طولها على الأقل${\displaystyle p}$، أين${\displaystyle p}$هو ثابت - يسمى طول الضخ - يختلف بين اللغات الخالية من السياق.

يقول${\displaystyle s}$هي سلسلة طولها على الأقل${\displaystyle p}$هذا موجود في اللغة.

تنص نظرية الضخ على أن${\displaystyle s}$يمكن تقسيمها إلى خمس سلاسل فرعية،${\displaystyle s=uvwxy}$، أين${\displaystyle vx}$غير فارغة وطولها${\displaystyle vwx}$هو على الأكثر${\displaystyle p}$بحيث يتكرر${\displaystyle v}$و${\displaystyle x}$نفس عدد المرات (${\displaystyle n}$) في${\displaystyle s}$ينتج سلسلة نصية لا تزال ضمن اللغة. من المفيد غالبًا تكرارها صفر مرة، مما يزيل${\displaystyle v}$و${\displaystyle x}$من السلسلة (وهذا ما يُسمى "الضخ للأسفل"). عملية "الضخ للأعلى" هذه${\displaystyle s}$مع نسخ إضافية من${\displaystyle v}$و${\displaystyle x}$وهذا ما أعطى نظرية الضخ اسمها.

تخضع اللغات المحدودة (وهي لغات منتظمة وبالتالي خالية من السياق) لفرضية الضخ بشكل بديهي من خلال امتلاكها${\displaystyle p}$يساوي أقصى طول للسلسلة في${\displaystyle L}$بالإضافة إلى واحد. وبما أنه لا توجد خيوط بهذا الطول، فإن معضلة الضخ تصبح بلا معنى .

تُستخدم نظرية الضخ غالبًا لإثبات أن لغة معينة L غير خالية من السياق، من خلال إظهار أن السلاسل الطويلة s موجودة في L ولا يمكن "ضخها" دون إنتاج سلاسل خارج L.

على سبيل المثال، إذا${\displaystyle S\subset \mathbb {N} }$إذا كانت لا نهائية ولكنها لا تحتوي على متتالية حسابية (لا نهائية) ، فـ${\displaystyle L=\{a^{n}:n\in S\}}$ليست خالية من السياق. على وجه الخصوص، لا الأعداد الأولية ولا الأعداد المربعة خالية من السياق.

على سبيل المثال، اللغة${\displaystyle L=\{a^{n}b^{n}c^{n}|n>0\}}$يمكن إثبات أن اللغة L غير خالية من السياق باستخدام مبرهنة الضخ في برهان بالتناقض . أولًا، نفترض أن L خالية من السياق. وفقًا لمبرهنة الضخ، يوجد عدد صحيح p يمثل طول الضخ للغة L. لنعتبر السلسلة${\displaystyle s=a^{p}b^{p}c^{p}}$في L. تخبرنا نظرية الضخ أنه يمكن كتابة s على الصورة${\displaystyle s=uvwxy}$حيث u و v و w و x و y هي سلاسل فرعية، بحيث${\displaystyle |vx|\geq 1}$،${\displaystyle |vwx|\leq p}$، و${\displaystyle uv^{i}wx^{i}y\in L}$لكل عدد صحيح${\displaystyle i\geq 0}$باختيار s وحقيقة أن${\displaystyle |vwx|\leq p}$يتضح بسهولة أن السلسلة الفرعية vwx لا يمكن أن تحتوي على أكثر من رمزين مختلفين. أي أن لدينا واحدة من خمس احتمالات لـ vwx :

1. ${\displaystyle vwx=a^{j}}$بالنسبة للبعض${\displaystyle j\leq p}$.
2. ${\displaystyle vwx=a^{j}b^{k}}$بالنسبة لبعض j و k مع${\displaystyle j+k\leq p}$
3. ${\displaystyle vwx=b^{j}}$بالنسبة للبعض${\displaystyle j\leq p}$.
4. ${\displaystyle vwx=b^{j}c^{k}}$بالنسبة لبعض j و k مع${\displaystyle j+k\leq p}$.
5. ${\displaystyle vwx=c^{j}}$بالنسبة للبعض${\displaystyle j\leq p}$.

في كل حالة،${\displaystyle uv^{i}wx^{i}y}$لا يحتوي على أعداد متساوية من كل حرف لأي${\displaystyle i\neq 1}$. هكذا،${\displaystyle uv^{2}wx^{2}y}$لا يمتلك الشكل${\displaystyle a^{i}b^{i}c^{i}}$وهذا يتناقض مع تعريف L. لذلك، فإن افتراضنا الأولي بأن L خالية من السياق يجب أن يكون خاطئًا.

في عام 1960، أثبت شاينبرغ أن${\displaystyle L=\{a^{n}b^{n}a^{n}|n>0\}}$لا يعتمد على السياق باستخدام مقدمة لفرضية الضخ. ^{[ 3 ]}

على الرغم من أن نظرية الضخ غالبًا ما تكون أداة مفيدة لإثبات أن لغة معينة ليست خالية من السياق، إلا أن هناك لغات ليست خالية من السياق، ولكنها لا تزال تستوفي الشرط الذي تحدده نظرية الضخ، على سبيل المثال $${\displaystyle L=\{b^{j}c^{k}d^{l}|j,k,l\in \mathbb {N} \}\cup \{a^{i}b^{j}c^{j}d^{j}|i,j\in \mathbb {N} ,i\geq 1\}}$$ بالنسبة لـ s = b ^j c ^k d ^l مع eg j ≥1، اختر vwx بحيث تتكون فقط من b 's ، وبالنسبة لـ s = a ⁱ b ^j c ^j d ^j، اختر vwx بحيث تتكون فقط من a 's ؛ في كلتا الحالتين ، تظل جميع السلاسل المُضخّمة في L. ^{[ 4 ]} لإثبات أن لغة معينة خالية من السياق، يكفي إنشاء آلة دفع لأسفل تقبلها.