آلة لاحقة

"السياق الصحيح" للكلمة${\displaystyle \omega }$فيما يتعلق باللغة${\displaystyle L}$هي مجموعة${\displaystyle [\omega ]_{R}=\{\alpha$ :\omega \alpha \in L\}} أي مجموعة من الكلمات${\displaystyle \alpha }$بحيث يكون تسلسلها مع${\displaystyle \omega }$يشكل كلمة من${\displaystyle L}$تؤدي السياقات الصحيحة إلى علاقة تكافؤ طبيعية${\displaystyle [\alpha ]_{R}=[\beta ]_{R}}$على مجموعة جميع الكلمات. إذا كانت اللغة${\displaystyle L}$إذا تم التعرف على لغة معينة بواسطة آلة حتمية محدودة، فإنه يوجد آلة فريدة، حتى التماثل ، تتعرف على نفس اللغة ولها أقل عدد ممكن من الحالات. وتسمى هذه الآلة بالآلة الدنيا للغة المعطاة.${\displaystyle L}$تسمح نظرية مايهيل-نيرود بتعريفها بشكل صريح من حيث السياقات الصحيحة : ^{[ 11 ] [ 12 ]}

وبهذا المعنى، فإن "آلة اللواحق" هي آلة حتمية محدودة دنيا تتعرف على لغة لواحق الكلمات${\displaystyle S=s_{1}s_{2}\dots s_{n}}$السياق الصحيح للكلمة${\displaystyle \omega }$فيما يتعلق بهذه اللغة، فهي تتكون من كلمات${\displaystyle \alpha }$بحيث${\displaystyle \omega \alpha }$هو لاحقة من${\displaystyle S}$يسمح ذلك بصياغة اللمة التالية التي تحدد تقابلاً بين السياق الصحيح للكلمة ومجموعة المواضع الصحيحة لظهورها في${\displaystyle S}$[ ^{13 ] [ 14 ]​}

على سبيل المثال، بالنسبة للكلمة${\displaystyle S=abacaba}$وكلمتها الفرعية${\displaystyle \omega =ab}$، وهو يحمل${\displaystyle endpos(ab)=\{2,6\}}$و${\displaystyle [ab]_{R}=\{a,acaba\}}$بشكل غير رسمي،${\displaystyle [ab]_{R}}$تتكون من كلمات تلي حالات حدوث${\displaystyle ab}$حتى نهاية${\displaystyle S}$و${\displaystyle endpos(ab)}$يتكون من المواضع الصحيحة لتلك التكرارات. في هذا المثال، العنصر${\displaystyle x=2\in endpos(ab)}$يتوافق مع الكلمة${\displaystyle s_{3}s_{4}s_{5}s_{6}s_{7}=acaba\in [ab]_{R}}$بينما الكلمة${\displaystyle a\in [ab]_{R}}$يتوافق مع العنصر${\displaystyle 7-|a|=6\in endpos(ab)}$.

وهذا يستلزم العديد من خصائص بنية حالات الأوتوماتون اللاحقة. لنفترض${\displaystyle |\alpha |\leq |\beta |}$ثم: ^{[ 14 ]}

• لو${\displaystyle [\alpha ]_{R}}$و${\displaystyle [\beta ]_{R}}$يشتركان في عنصر واحد على الأقل${\displaystyle x}$، ثم${\displaystyle endpos(\alpha )}$و${\displaystyle endpos(\beta )}$يوجد عنصر مشترك أيضًا. وهذا يعني ضمناً${\displaystyle \alpha }$هو لاحقة من${\displaystyle \beta }$وبالتالي${\displaystyle endpos(\beta )\subset endpos(\alpha )}$و${\displaystyle [\beta ]_{R}\subset [\alpha ]_{R}}$في المثال المذكور آنفاً،${\displaystyle a\in [ab]_{R}\cap [cab]_{R}}$، لذا${\displaystyle ab}$هو لاحقة من${\displaystyle cab}$وبالتالي${\displaystyle [cab]_{R}=\{a\}\subset \{a,acaba\}=[ab]_{R}}$و${\displaystyle endpos(cab)=\{6\}\subset \{2,6\}=endpos(ab)}$؛
• لو${\displaystyle [\alpha ]_{R}=[\beta ]_{R}}$، ثم${\displaystyle endpos(\alpha )=endpos(\beta )}$، هكذا${\displaystyle \alpha }$يحدث في${\displaystyle S}$فقط كلاحقة لـ${\displaystyle \beta }$على سبيل المثال، لـ${\displaystyle \alpha =b}$و${\displaystyle \beta =ab}$وهذا يعني أن${\displaystyle [b]_{R}=[ab]_{R}=\{a,acaba\}}$و${\displaystyle endpos(b)=endpos(ab)=\{2,6\}}$؛
• لو${\displaystyle [\alpha ]_{R}=[\beta ]_{R}}$و${\displaystyle \gamma }$هو لاحقة من${\displaystyle \beta }$بحيث${\displaystyle |\alpha |\leq |\gamma |\leq |\beta |}$، ثم${\displaystyle [\alpha ]_{R}=[\gamma ]_{R}=[\beta ]_{R}}$في المثال أعلاه${\displaystyle [c]_{R}=[bac]_{R}=\{aba\}}$وينطبق ذلك على اللاحقة "الوسيطة".${\displaystyle \gamma =ac}$الذي - التي${\displaystyle [ac]_{R}=\{aba\}}$.

أي ولاية${\displaystyle q=[\alpha ]_{R}}$يتعرف نظام اللاحقات الآلي على سلسلة متصلة من اللواحق المتداخلة لأطول كلمة تم التعرف عليها بواسطة هذه الحالة. ^{[ 14 ]}

"امتداد يساري"${\displaystyle {\overset {\scriptstyle {\leftarrow }}{\gamma }}}$من السلسلة${\displaystyle \gamma }$هي أطول سلسلة${\displaystyle \omega }$وهذا له نفس السياق الصحيح مثل${\displaystyle \gamma }$. طول${\displaystyle |{\overset {\scriptstyle {\leftarrow }}{\gamma }}|}$أطول سلسلة يتم التعرف عليها بواسطة${\displaystyle q=[\gamma ]_{R}}$يُرمز إليه بـ${\displaystyle len(q)}$. ينص على ما يلي: ^{[ 15 ]}

"رابط لاحق"${\displaystyle link(q)}$من الدولة${\displaystyle q=[\alpha ]_{R}}$هو المؤشر إلى الحالة${\displaystyle p}$التي تحتوي على أكبر لاحقة من${\displaystyle \alpha }$ذلك غير معترف به من قبل${\displaystyle q}$.

وبهذا المعنى يمكن القول${\displaystyle q=[\alpha ]_{R}}$يتعرف بدقة على جميع اللواحق من${\displaystyle {\overset {\scriptstyle {\leftarrow }}{\alpha }}}$هذا أطول من${\displaystyle len(link(q))}$ولا تتجاوز مدة${\displaystyle len(q)}$وينطبق عليه أيضاً ما يلي: ^{[ 15 ]}

شجرة البادئة (أو "شجرة البادئة") هي شجرة موجهة ذات جذر، حيث يتم تمييز الأقواس بأحرف بطريقة لا يوجد فيها رأس${\displaystyle v}$تحتوي هذه الشجرة على قوسين خارجيين يحملان نفس الحرف. بعض رؤوس الشجرة تُصنّف على أنها نهائية. يُقال إن الشجرة تتعرف على مجموعة من الكلمات المُحددة بمسارات من جذرها إلى رؤوسها النهائية. وبهذه الطريقة، تُعد أشجار البادئات نوعًا خاصًا من الأوتوماتا المحدودة الحتمية إذا اعتبرنا جذرها رأسًا ابتدائيًا. ^{[ 16 ]} "شجرة اللاحقة" للكلمة${\displaystyle S}$هي شجرة بادئات تتعرف على مجموعة من لواحقها. " شجرة اللواحق " هي شجرة يتم الحصول عليها من شجرة اللواحق عبر إجراء الضغط، حيث يتم دمج الحواف المتتالية إذا كانت درجة الرأس بينهما تساوي اثنين. ^{[ 15 ]}

بحسب تعريفها، يمكن الحصول على آلة لاحقة من خلال تصغير شجرة اللواحق. ويمكن إثبات أن آلة لاحقة مضغوطة تُحصل عليها من خلال تصغير شجرة اللواحق (بافتراض أن كل سلسلة على حافة شجرة اللواحق هي حرف صلب من الأبجدية) وضغط آلة اللواحق. ^{[ 17 ]} بالإضافة إلى هذه العلاقة بين شجرة اللواحق وآلة اللواحق لنفس السلسلة، توجد أيضًا علاقة بين آلة اللواحق للسلسلة${\displaystyle S=s_{1}s_{2}\dots s_{n}}$وشجرة اللواحق للسلسلة المعكوسة${\displaystyle S^{R}=s_{n}s_{n-1}\dots s_{1}}$[ ^{18 ]​}

وبالمثل، يمكن تقديم "سياقات يسارية" كما هو الحال مع السياقات اليمنى.${\displaystyle [\omega ]_{L}=\{\beta \in \Sigma ^{*}:\beta \omega \in L\}}$، "امتدادات اليمين"${\displaystyle {\overset {\scriptstyle {\rightarrow }}{\omega ~}}}$بما يتوافق مع أطول سلسلة لها نفس السياق الأيسر مثل${\displaystyle \omega }$وعلاقة التكافؤ${\displaystyle [\alpha ]_{L}=[\beta ]_{L}}$إذا نظرنا إلى الامتدادات الصحيحة فيما يتعلق باللغة${\displaystyle L}$من "بادئات" السلسلة${\displaystyle S}$يمكن الحصول عليه من خلال: ^{[ 15 ]}

وهذا يعني شجرة روابط اللواحق للسلسلة${\displaystyle S}$وشجرة اللواحق للسلسلة${\displaystyle S^{R}}$متماثلة: ^{[ 18 ]}

وبالمثل لحالة الامتدادات اليسرى، فإن اللمة التالية تنطبق على الامتدادات اليمنى: ^{[ 15 ]}

آلة لاحقة للسلسلة${\displaystyle S}$من الطول${\displaystyle n>1}$لديه على الأكثر${\displaystyle 2n-1}$الولايات وعلى الأكثر${\displaystyle 3n-4}$الانتقالات. يتم الوصول إلى هذه الحدود على السلاسل النصية${\displaystyle abb\dots bb=ab^{n-1}}$و${\displaystyle abb\dots bc=ab^{n-2}c}$وبالمثل. ^{[ 13 ]} يمكن صياغة ذلك بطريقة أكثر دقة على النحو التالي${\displaystyle |\delta |\leq |Q|+n-2}$أين${\displaystyle |\delta |}$و${\displaystyle |Q|}$^{[ 14 ]} تمثل أعداد الانتقالات والحالات في الأوتوماتون على التوالي.

بعد إضافة حرف جديد إلى السلسلة، تتغير بعض فئات التكافؤ. لنفترض${\displaystyle [\alpha ]_{R_{\omega }}}$كن السياق الصحيح لـ${\displaystyle \alpha }$فيما يتعلق بلغة${\displaystyle \omega }$اللواحق. ثم الانتقال من${\displaystyle [\alpha ]_{R_{\omega }}}$ل${\displaystyle [\alpha ]_{R_{\omega x}}}$بعد${\displaystyle x}$يُلحق بـ${\displaystyle \omega }$يتم تعريفها بواسطة اللمة: ^{[ 14 ]}

بعد الإضافة${\displaystyle x}$إلى الكلمة الحالية${\displaystyle \omega }$السياق الصحيح لـ${\displaystyle \alpha }$قد يتغير بشكل كبير فقط إذا${\displaystyle \alpha }$هو لاحقة من${\displaystyle \omega x}$وهذا يعني وجود علاقة تكافؤ.${\displaystyle \equiv _{R_{\omega x}}}$هو تحسين لـ${\displaystyle \equiv _{R_{\omega }}}$بمعنى آخر، إذا${\displaystyle [\alpha ]_{R_{\omega x}}=[\beta ]_{R_{\omega x}}}$، ثم${\displaystyle [\alpha ]_{R_{\omega }}=[\beta ]_{R_{\omega }}}$بعد إضافة حرف جديد، لا يوجد على الأكثر فئتان مكافئتان من${\displaystyle \equiv _{R_{\omega }}}$سيتم تقسيمها، وقد ينقسم كل منها إلى فئتين جديدتين على الأكثر. أولاً، يتم دائمًا تقسيم فئة التكافؤ المقابلة للسياق الأيمن الفارغ إلى فئتين من فئات التكافؤ، إحداهما مقابلة لـ${\displaystyle \omega x}$نفسها وامتلاكها${\displaystyle \{\varepsilon \}}$كسياق صحيح. تحتوي فئة التكافؤ الجديدة هذه بالضبط${\displaystyle \omega x}$وجميع لواحقها التي لم تظهر في${\displaystyle \omega }$، حيث كان السياق الصحيح لمثل هذه الكلمات فارغًا من قبل، ويحتوي الآن على كلمة فارغة فقط. ^{[ 14 ]}

بالنظر إلى التطابق بين حالات آلة اللواحق ورؤوس شجرة اللواحق، فمن الممكن تحديد الحالة الثانية التي قد تنقسم بعد إضافة حرف جديد. الانتقال من${\displaystyle \omega }$ل${\displaystyle \omega x}$يتوافق ذلك مع الانتقال من${\displaystyle \omega ^{R}}$ل${\displaystyle x\omega ^{R}}$في السلسلة المعكوسة. من حيث أشجار اللواحق، يتوافق ذلك مع إدخال أطول لاحقة جديدة${\displaystyle x\omega ^{R}}$في شجرة اللواحق لـ${\displaystyle \omega ^{R}}$قد يتشكل رأسان جديدان على الأكثر بعد هذا الإدخال: أحدهما يتوافق مع${\displaystyle x\omega ^{R}}$بينما يتوافق الآخر مع سلفه المباشر في حالة وجود تفرع. وبالعودة إلى آلات اللواحق، فهذا يعني أن الحالة الجديدة الأولى التي يتم التعرف عليها${\displaystyle \omega x}$والثاني (إن وُجدت حالة جديدة ثانية) هو رابطها اللاحق. ويمكن صياغته على شكل مبرهنة: ^{[ 14 ]}

وهذا يعني أنه إذا${\displaystyle \alpha =\beta }$(على سبيل المثال، عندما)${\displaystyle x}$لم يحدث في${\displaystyle \omega }$على الإطلاق و${\displaystyle \alpha =\beta =\varepsilon }$)، عندئذٍ يتم تقسيم فئة التكافؤ المقابلة للسياق الأيمن الفارغ فقط. ^{[ 14 ]}

إلى جانب روابط اللواحق، من الضروري أيضًا تحديد الحالات النهائية للآلة. ويترتب على خصائص البنية أن جميع لواحق الكلمة${\displaystyle \alpha }$معترف بها من قبل${\displaystyle q=[\alpha ]_{R}}$يتم التعرف عليها بواسطة بعض الرؤوس على مسار اللاحقة${\displaystyle (q,link(q),link^{2}(q),\dots )}$ل${\displaystyle q}$أي اللواحق التي يزيد طولها عن${\displaystyle len(link(q))}$استرخي${\displaystyle q}$، اللواحق التي يزيد طولها عن${\displaystyle len(link(link(q))}$لكن ليس أكبر من${\displaystyle len(link(q))}$استرخي${\displaystyle link(q)}$وهكذا دواليك. وبالتالي، إذا كانت الدولة تعترف${\displaystyle \omega }$يُرمز إليه بـ${\displaystyle last}$ثم جميع الحالات النهائية (أي التعرف على لواحق من${\displaystyle \omega }$) تشكيل التسلسل${\displaystyle (last,link(last),link^{2}(last),\dots )}$[ ^{19 ]​}

بعد الشخصية${\displaystyle x}$يُلحق بـ${\displaystyle \omega }$الحالات الجديدة المحتملة لآلة اللواحق هي${\displaystyle [\omega x]_{R_{\omega x}}}$و${\displaystyle [\alpha ]_{R_{\omega x}}}$رابط لاحق من${\displaystyle [\omega x]_{R_{\omega x}}}$يذهب إلى${\displaystyle [\alpha ]_{R_{\omega x}}}$ومن${\displaystyle [\alpha ]_{R_{\omega x}}}$يذهب إلى${\displaystyle link([\alpha ]_{R_{\omega }})}$كلمات من${\displaystyle [\omega x]_{R_{\omega x}}}$يحدث في${\displaystyle \omega x}$فقط كلاحقاتها، لذلك لا ينبغي أن تكون هناك أي انتقالات على الإطلاق من${\displaystyle [\omega x]_{R_{\omega x}}}$بينما ينبغي أن تتم الانتقالات إليه من لواحق من${\displaystyle \omega }$بطول لا يقل عن${\displaystyle \alpha }$وأن يتم تمييزها بالحرف${\displaystyle x}$. ولاية${\displaystyle [\alpha ]_{R_{\omega x}}}$تتكون من مجموعة فرعية من${\displaystyle [\alpha ]_{R_{\omega }}}$وهكذا ينتقل من${\displaystyle [\alpha ]_{R_{\omega x}}}$ينبغي أن يكون هو نفسه كما هو من${\displaystyle [\alpha ]_{R_{\omega }}}$في غضون ذلك، تؤدي التحولات إلى${\displaystyle [\alpha ]_{R_{\omega x}}}$ينبغي أن تنتقل من لواحق من${\displaystyle \omega }$طوله أقل من${\displaystyle |\alpha |}$وعلى الأقل${\displaystyle len(link([\alpha ]_{R_{\omega }}))}$حيث أدت هذه التحولات إلى${\displaystyle [\alpha ]_{R_{\omega }}}$قبل ذلك، كانت تُقابل الجزء المنفصل من هذه الولاية. ويمكن تحديد الولايات التي تُقابل هذه اللواحق من خلال اجتياز مسار رابط اللاحقة لـ${\displaystyle [\omega ]_{R_{\omega }}}$[ ^{19 ]​}

بناء آلة لاحقة للكلمة abbcbc
∅ → أ بعد إضافة الحرف الأول، يتم إنشاء حالة واحدة فقط في آلة اللواحق. وبالمثل، تتم إضافة ورقة واحدة فقط إلى شجرة اللواحق.	أ → أب يتم استخلاص الانتقالات الجديدة من جميع الحالات النهائية السابقة لأن b لم يظهر من قبل. وللسبب نفسه، تُضاف ورقة أخرى إلى جذر شجرة اللواحق.
ab → abb تتعرف الحالة 2 على الكلمتين ab و b ، ولكن b فقط هي اللاحقة الجديدة، لذلك يتم فصل هذه الكلمة إلى الحالة 4. في شجرة اللواحق، يتوافق ذلك مع انقسام الحافة المؤدية إلى الرأس 2.	abb → abbc يظهر الحرف c لأول مرة، لذلك يتم رسم الانتقالات من جميع الحالات النهائية السابقة. شجرة اللواحق للسلسلة المعكوسة تحتوي على ورقة أخرى مضافة إلى الجذر.
abbc → abbcb تتكون الحالة 4 من الكلمة الوحيدة b ، وهي لاحقة، وبالتالي فإن الحالة غير مقسمة. وبالمثل، يتم تعليق الورقة الجديدة على الرأس 4 في شجرة اللواحق.	abbcB → abbcbc تتعرف الحالة 5 على الكلمات abbc و bbc و bc و c ، ولكن الكلمتين الأخيرتين فقط هما لاحقتان لكلمة جديدة، لذلك يتم فصلهما في الحالة 8 الجديدة. وبالمثل، يتم تقسيم الحافة المؤدية إلى الرأس 5 ويتم وضع الرأس 8 في منتصف الحافة.

تؤدي النتائج النظرية المذكورة أعلاه إلى الخوارزمية التالية التي تأخذ الحرف x وتعيد بناء آلة اللواحق الخاصة بـ ω إلى آلة اللواحق الخاصة بـ${\displaystyle \omega x}$[ ^{19 ]​}

1. يتم الاحتفاظ بالحالة المقابلة للكلمة ω كآخر حالة ؛
2. بعد إضافة x ، يتم تخزين القيمة السابقة لـ last في المتغير p، ويتم إعادة تعيين last نفسه إلى الحالة الجديدة المقابلة لـ${\displaystyle \omega x}$؛
3. يتم تحديث الحالات المقابلة لللاحقات ω بالانتقالات إلى الحالة الأخيرة . وللقيام بذلك، يجب المرور عبر${\displaystyle p,link(p),link^{2}(p),\dots }$، إلى أن تكون هناك حالة قد حدثت فيها بالفعل عملية انتقال بمقدار x ؛
4. بمجرد انتهاء الحلقة المذكورة أعلاه، توجد 3 حالات:
   1. إذا لم تشهد أي من الحالات على مسار اللاحقة انتقالًا بواسطة x ، فإن x لم يظهر أبدًا في ω من قبل، ويجب أن يؤدي رابط اللاحقة من الأخير إلى${\displaystyle q_{0}}$؛
   2. إذا تم العثور على الانتقال بواسطة x والذي يؤدي من الحالة p إلى الحالة q ، بحيث${\displaystyle len(p)+1=len(q)}$، عندئذٍ لا يلزم تقسيم q وهو رابط لاحق لـ last ؛
   3. إذا تم العثور على الانتقال ولكن${\displaystyle len(q)>len(p)+1}$ثم الكلمات من q التي لا يتجاوز طولها${\displaystyle len(p)+1}$ينبغي فصلها إلى حالة "استنساخ" جديدة cl ؛
5. إذا تم الانتهاء من الخطوة السابقة بإنشاء cl ، فيجب أن تنسخ الانتقالات منه ورابط اللاحقة الخاص به تلك الخاصة بـ q ، وفي نفس الوقت يتم تعيين cl ليكون رابط لاحقة مشترك لكل من q و last ؛
6. الانتقالات التي أدت إلى q من قبل ولكنها تتوافق مع كلمات لا يتجاوز طولها${\displaystyle len(p)+1}$يتم إعادة توجيهها إلى cl . وللقيام بذلك، يستمر المرء في المرور عبر مسار اللاحقة لـ p حتى يتم العثور على الحالة التي لا يؤدي الانتقال بواسطة x منها إلى q .

يتم وصف الإجراء بأكمله بواسطة الشفرة الزائفة التالية: ^{[ 19 ]}

دالة إضافة_حرف(x) : تعريف p = last تعيين last = new_state() تعيين len(last) = len(p) + 1 طالما أن δ(p, x) غير معرف: تعيين δ(p, x) = last، p = link(p) تعريف q = δ(p, x) إذا كان q = last : تعيين link(last) = q 0 وإلا إذا كان len(q) = len(p) + 1 : تعيين link(last) = q وإلا : تعريف cl = new_state() تعيين len(cl) = len(p) + 1 تعيين δ(cl) = δ(q)، link(cl) = link(q) تعيين link(last) = link(q) = cl طالما أن δ(p, x) = q : تعيين δ(p, x) = cl، p = link(p)

هنا${\displaystyle q_{0}}$تمثل الحالة الابتدائية للآلة، و new_state()هي دالة تُنشئ حالة جديدة لها. يُفترض أن قيم lastو lenو linkمخزنة δكمتغيرات عامة. ^{[ 19 ]} وللتسهيل، تُعرَّف بأنهاlink(q0)${\displaystyle q_{0}}$.

قد تختلف درجة تعقيد الخوارزمية تبعًا للبنية الأساسية المستخدمة لتخزين انتقالات الأوتوماتون. ويمكن تنفيذها في${\displaystyle O(n\log |\Sigma |)}$مع${\displaystyle O(n)}$أو في تكلفة الذاكرة${\displaystyle O(n)}$مع${\displaystyle O(n|\Sigma |)}$زيادة الحمل على الذاكرة إذا افترضنا أن تخصيص الذاكرة يتم في${\displaystyle O(1)}$للحصول على هذا القدر من التعقيد، يجب استخدام أساليب التحليل المُستهلك . قيمة${\displaystyle len(p)}$يتناقص هذا المقدار بشكل صارم مع كل تكرار للدورة، بينما قد يزيد بمقدار واحد فقط بعد التكرار الأول للدورة عند استدعاء الدالة add_letter التالي . القيمة الإجمالية لـ${\displaystyle len(p)}$لا يتجاوز أبداً${\displaystyle n}$ولا يزيد إلا بمقدار واحد بين كل تكرار لإضافة أحرف جديدة، مما يشير إلى أن التعقيد الكلي خطي على الأكثر. وقد تم إثبات خطية الدورة الثانية بطريقة مماثلة. ^{[ 19 ]}

كما ذُكر سابقًا، يُمكن الحصول على آلة لاحقة مضغوطة من خلال ضغط آلة لاحقة عادية (عن طريق إزالة الحالات غير النهائية والتي لها قوس خروج واحد فقط) وتقليل شجرة لاحقة. وعلى غرار آلة اللاحقة العادية، يُمكن تعريف حالات آلة اللاحقة المضغوطة بشكل صريح. امتداد ثنائي الاتجاه${\displaystyle {\overset {\scriptstyle {\longleftrightarrow }}{\gamma }}}$كلمة${\displaystyle \gamma }$هي أطول كلمة${\displaystyle \omega =\beta \gamma \alpha }$بحيث يكون كل ظهور لـ${\displaystyle \gamma }$في${\displaystyle S}$يسبقه${\displaystyle \beta }$وخلفه${\displaystyle \alpha }$أما فيما يتعلق بالامتدادات اليسرى واليمنى، فهذا يعني أن الامتداد ثنائي الاتجاه هو الامتداد الأيسر للامتداد الأيمن، أو ما يعادله، الامتداد الأيمن للامتداد الأيسر.${\textstyle {\overset {\scriptstyle \longleftrightarrow }{\gamma }}={\overset {\scriptstyle \leftarrow }{\overset {\rightarrow }{\gamma }}}={\overset {\rightarrow }{\overset {\scriptstyle \leftarrow }{\gamma }}}}$. من حيث الامتدادات ثنائية الاتجاه، يتم تعريف الأوتومات المضغوط على النحو التالي: ^{[ 15 ]}

تؤدي الامتدادات ثنائية الاتجاه إلى علاقة تكافؤ${\textstyle {\overset {\scriptstyle \longleftrightarrow }{\alpha }}={\overset {\scriptstyle \longleftrightarrow }{\beta }}}$والتي تحدد مجموعة الكلمات التي تتعرف عليها نفس حالة الآلة المضغوطة. علاقة التكافؤ هذه هي إغلاق متعدٍ للعلاقة المحددة بواسطة${\textstyle ({\overset {\scriptstyle {\rightarrow }}{\alpha \,}}={\overset {\scriptstyle {\rightarrow }}{\beta \,}})\vee ({\overset {\scriptstyle {\leftarrow }}{\alpha }}={\overset {\scriptstyle {\leftarrow }}{\beta }})}$مما يسلط الضوء على حقيقة أنه يمكن الحصول على آلة مضغوطة عن طريق لصق رؤوس شجرة اللواحق المتكافئة عبر${\displaystyle {\overset {\scriptstyle {\leftarrow }}{\alpha }}={\overset {\scriptstyle {\leftarrow }}{\beta }}}$العلاقة (تقليل شجرة اللواحق) ولصق حالات آلة اللواحق المتكافئة عبر${\displaystyle {\overset {\scriptstyle {\rightarrow }}{\alpha \,}}={\overset {\scriptstyle {\rightarrow }}{\beta \,}}}$العلاقة (ضغط آلة اللواحق). ^{[ 23 ]} إذا كانت الكلمات${\displaystyle \alpha }$و${\displaystyle \beta }$لها نفس الامتدادات الصحيحة، والكلمات${\displaystyle \beta }$و${\displaystyle \gamma }$إذا كانت لها نفس الامتدادات اليسرى، فإن جميع السلاسل تتراكم.${\displaystyle \alpha }$،${\displaystyle \beta }$و${\displaystyle \gamma }$لها نفس الامتدادات ثنائية الاتجاه. في الوقت نفسه، قد يحدث ألا يكون للامتدادات اليسرى أو اليمنى لـ${\displaystyle \alpha }$و${\displaystyle \gamma }$يتزامن. على سبيل المثال، يمكن للمرء أن يأخذ${\displaystyle S=\beta =ab}$،${\displaystyle \alpha =a}$و${\displaystyle \gamma =b}$، والتي تكون امتداداتها اليسرى واليمنى كما يلي:${\displaystyle {\overset {\scriptstyle {\rightarrow }}{\alpha \,}}={\overset {\scriptstyle {\rightarrow }}{\beta \,}}=ab={\overset {\scriptstyle {\leftarrow }}{\beta }}={\overset {\scriptstyle {\leftarrow }}{\gamma }}}$، لكن${\displaystyle {\overset {\scriptstyle {\rightarrow }}{\gamma \,}}=b}$و${\displaystyle {\overset {\scriptstyle {\leftarrow }}{\alpha }}=a}$مع ذلك، فبينما تتشكل علاقات التكافؤ للامتدادات أحادية الاتجاه من خلال سلسلة متصلة من البادئات أو اللواحق المتداخلة، فإن علاقات التكافؤ للامتدادات ثنائية الاتجاه أكثر تعقيدًا، والشيء الوحيد الذي يمكن استنتاجه على وجه اليقين هو أن السلاسل التي لها نفس الامتداد ثنائي الاتجاه هي سلاسل فرعية من أطول سلسلة لها نفس الامتداد ثنائي الاتجاه، ولكن قد يحدث حتى ألا يكون لها أي سلسلة فرعية غير فارغة مشتركة. لا يتجاوز العدد الإجمالي لفئات التكافؤ لهذه العلاقة${\displaystyle n+1}$وهذا يعني أن آلة اللاحقة المضغوطة للسلسلة ذات الطول${\displaystyle n}$لديه على الأكثر${\displaystyle n+1}$الحالات. عدد الانتقالات في مثل هذه الآلة هو على الأكثر${\displaystyle 2n-2}$[ ^{15 ]​}

لنفترض مجموعة من الكلمات${\displaystyle T=\{S_{1},S_{2},\dots ,S_{k}\}}$من الممكن بناء تعميم لآلة اللواحق بحيث تتعرف على اللغة المكونة من لواحق جميع الكلمات من المجموعة. وستبقى قيود عدد الحالات والانتقالات في هذه الآلة كما هي بالنسبة لآلة الكلمة الواحدة إذا وضعنا${\displaystyle n=|S_{1}|+|S_{2}|+\dots +|S_{k}|}$[ ^{23 ]} تشبه الخوارزمية بناء آلة الكلمات المفردة باستثناء أنه بدلاً ^من${\displaystyle last}$ستعمل الدالة add_letter مع الحالة التي تتوافق مع الكلمة${\displaystyle \omega _{i}}$بافتراض الانتقال من مجموعة الكلمات${\displaystyle \{\omega _{1},\dots ,\omega _{i},\dots ,\omega _{k}\}}$إلى المجموعة${\displaystyle \{\omega _{1},\dots ,\omega _{i}x,\dots ,\omega _{k}\}}$[ ^{24 ] [ 25 ]​}

تُعمم هذه الفكرة بشكل أكبر لتشمل الحالة عندما${\displaystyle T}$لا يتم تحديدها بشكل صريح، بل يتم تحديدها بواسطة شجرة بادئة مع${\displaystyle Q}$أظهر موهري وآخرون أن مثل هذه الآلة سيكون لها على الأكثر رؤوس.${\displaystyle 2Q-2}$ويمكن بناؤها في وقت خطي انطلاقاً من حجمها. وفي الوقت نفسه، قد يصل عدد الانتقالات في هذه الآلة إلى${\displaystyle O(Q|\Sigma |)}$على سبيل المثال، بالنسبة لمجموعة الكلمات${\displaystyle T=\{\sigma _{1},a\sigma _{1},a^{2}\sigma _{1},\dots ,a^{n}\sigma _{1},a^{n}\sigma _{2},\dots ,a^{n}\sigma _{k}\}}$على الأبجدية${\displaystyle \Sigma =\{a,\sigma _{1},\dots ,\sigma _{k}\}}$يبلغ الطول الإجمالي للكلمات ما يلي:${\textstyle O(n^{2}+nk)}$عدد الرؤوس في شجرة اللاحق المقابلة يساوي${\displaystyle O(n+k)}$وتتكون الآلة اللاحقة المقابلة من${\displaystyle O(n+k)}$الولايات و${\displaystyle O(nk)}$الانتقالات. الخوارزمية التي اقترحها موهري تُكرر بشكل أساسي الخوارزمية العامة لبناء آلة من عدة سلاسل نصية، ولكن بدلاً من إضافة الكلمات واحدة تلو الأخرى، فإنها تجتاز شجرة البحث بترتيب بحث العرض أولاً ، وتُضيف الأحرف الجديدة عند مصادفتها أثناء الاجتياز، مما يضمن تعقيدًا خطيًا مُستهلكًا. ^{[ 26 ]}

قد تستفيد بعض خوارزميات الضغط ، مثل LZ77 و RLE، من تخزين آلة لاحقة أو بنية مشابهة ليس للسلسلة بأكملها، بل للجزء الأخير فقط.${\displaystyle k}$يتم تحديث أحرفها أثناء تحديث السلسلة. وذلك لأن ضغط البيانات عادة ما يكون كبيرًا بشكل ملحوظ، واستخدام${\displaystyle O(n)}$الذاكرة غير مرغوب فيها. في عام 1985، طورت جانيت بلومر خوارزمية للحفاظ على آلة لاحقة على نافذة منزلقة بحجم${\displaystyle k}$في${\displaystyle O(nk)}$أسوأ الحالات و${\displaystyle O(n\log k)}$في المتوسط، بافتراض أن الشخصيات موزعة بشكل مستقل ومتساوٍ . كما أظهرت أيضًا${\displaystyle O(nk)}$لا يمكن تحسين التعقيد: إذا اعتبرنا الكلمات بمثابة سلسلة من عدة${\displaystyle (ab)^{m}c(ab)^{m}d}$الكلمات، حيث${\displaystyle k=6m+2}$ثم عدد الحالات لنافذة بحجم${\displaystyle k}$سيتغير بشكل متكرر مع قفزات الترتيب${\displaystyle m}$مما يجعل حتى التحسين النظري لـ${\displaystyle O(nk)}$بالنسبة لآلات اللواحق المنتظمة، يكون ذلك مستحيلاً. ^{[ 27 ]}

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

إحدى طرق التغلب على هذه العقبة هي السماح بعرض النافذة بالتغير قليلاً مع البقاء${\displaystyle O(k)}$يمكن تحقيق ذلك باستخدام خوارزمية تقريبية اقترحها إينيناغا وآخرون في عام 2004. ولا يُضمن أن تكون النافذة التي يُبنى عليها آلة اللواحق في هذه الخوارزمية بطول${\displaystyle k}$لكن من المؤكد أن يكون على الأقل${\displaystyle k}$وعلى الأكثر${\displaystyle 2k+1}$مع توفير تعقيد خطي إجمالي للخوارزمية. ^{[ 32 ]}