Tagged Deterministic Finite Automaton
آٹومیٹا تھیوری میں، ٹیگ شدہ ڈیٹرمینیسٹک فائنٹ آٹومیٹن (ٹی ڈی ایف اے) ڈیٹرمینیٹک فائنٹ آٹومیٹن (ڈی ایف اے) کی توسیع ہے۔ باقاعدہ زبانوں کے لیے پہچان کے مسئلے کو حل کرنے کے علاوہ، ٹی ڈی ایف اے ذیلی میچ نکالنے اور تجزیہ کرنے کی بھی صلاحیت رکھتا ہے۔ جبکہ کینونکل ڈی ایف اے یہ معلوم کر سکتا ہے کہ آیا کوئی سٹرنگ باقاعدہ اظہار کی طرف سے بیان کردہ زبان سے تعلق رکھتی ہے، ٹی ڈی ایف اے مخصوص ذیلی تاثرات سے ملنے والی سبسٹرنگ بھی نکال سکتا ہے۔ زیادہ عام طور پر، ٹی ڈی ایف اے ان پٹ سٹرنگ میں پوزیشنوں کی شناخت کر سکتا ہے جو باقاعدہ اظہار میں ٹیگ شدہ پوزیشنوں سے میل کھاتے ہیں (ٹیگز میٹا علامت ہوتے ہیں جو قوسین پر قبضہ کرنے کی طرح ہوتے ہیں، لیکن جوڑی کی ضرورت کے بغیر)۔ تاریخ ٹی ڈی ایف اے کو سب سے پہلے 2000 میں ولی لوریکری نے بیان کیا تھا۔ اس سے پہلے یہ معلوم نہیں تھا کہ آیا ایک مقررہ محدود ریاستی آٹومیٹن پر ایک پاس میں ذیلی میچ نکالنا ممکن ہے، لہذا یہ مقالہ ایک اہم پیشرفت تھی۔ لوریکاری نے ٹی ڈی ایف اے کی تعمیر کو بیان کیا اور اس بات کا ثبوت دیا کہ تعین کا عمل ختم ہو جاتا ہے، تاہم الگورتھم نے ابہام کو صحیح طریقے سے نہیں سنبھالا۔ 2007 میں کرس کوکلیوز نے ہاسکل لائبریری ریجیکس-ٹی ڈی ایف اے میں ٹی ڈی ایف اے کو پوزیکس طویل ترین میچ سیمنٹکس کے ساتھ نافذ کیا۔ کوکلیوز نے الگورتھم کی ایک غیر رسمی تفصیل دی اور اس بنیادی سوال کا جواب دیا کہ آیا ٹی ڈی ایف اے پوزیکس کے طویل ترین میچ کے ابہام کی صلاحیت رکھتا ہے، جس پر دوسرے محققین کو شک تھا۔ 2017 میں الیہ ٹریفیمووچ نے ٹی ڈی ایف اے کو ایک علامتی شکل کے ساتھ بیان کیا۔ لک ہیڈ علامت کا استعمال ٹی ڈی ایف اے میں رجسٹروں اور رجسٹر آپریشنز کی تعداد کو کم کرتا ہے، جو اسے لوریکری ٹی ڈی ایف اے سے تیز اور اکثر چھوٹا بناتا ہے۔ ٹریفیموویچ نے ایل آر پارسرز ایل آر (1) اور ایل آر (0) کے ساتھ مشابہت کے ذریعے ٹی ڈی ایف اے کی مختلف اقسام کو ٹی ڈی ایف اے (1) اور ٹی ڈی ایف اے (0) کے ساتھ اور بغیر نظر کے کہا۔ الگورتھم کو اوپن سورس لیکسر جنریٹر RE2C میں لاگو کیا گیا تھا۔ ٹریفیمووچ نے کوکلیوز کے ابہام الگورتھم کو باقاعدہ بنایا۔ 2018 میں اینجلو بورسوٹی نے ٹی ڈی ایف اے کے تجرباتی جاوا نفاذ پر کام کیا۔ یہ بعد میں 2021 میں شائع ہوا۔ 2019 میں بورسوٹی اور ٹریفیموویچ نے اوکوئی اور سوزوکی کے ذریعہ پوزیکس ابہام الگورتھم کو ٹی ڈی ایف اے میں ڈھال لیا۔ انہوں نے نئے الگورتھم کی درستگی کا باضابطہ ثبوت دیا اور دکھایا کہ یہ عملی طور پر کوکلیوز الگورتھم سے تیز ہے۔ 2020 میں ٹریفیمووچ نے آر ای 2 سی میں ٹی ڈی ایف اے کے نفاذ کے بارے میں ایک مضمون شائع کیا۔ 2022 میں بورسوٹی اور ٹریفیمووچ نے ٹی ڈی ایف اے کی تعمیر کی تفصیلی وضاحت کے ساتھ ایک مقالہ شائع کیا۔ مقالے میں ان کی ماضی کی تحقیق کو شامل کیا گیا اور ملٹی پاس ٹی ڈی ایف اے پیش کیا گیا جو صرف وقت پر تعین کے لیے بہتر موزوں ہیں۔ انہوں نے ٹی ڈی ایف اے کا موازنہ دوسرے الگورتھم سے بھی کیا اور معیارات فراہم کیے۔ رسمی تعریف ٹی ڈی ایف اے کا بنیادی ڈھانچہ عام ڈی ایف اے جیسا ہی ہے: منتقلی سے منسلک ریاستوں کا ایک محدود مجموعہ۔ اس کے علاوہ، ٹی ڈی ایف اے کے پاس رجسٹروں کا ایک مقررہ سیٹ ہوتا ہے جو ٹیگ ویلیوز رکھتا ہے، اور ٹرانزیشن پر آپریشنز رجسٹر کرتا ہے جو رجسٹر ویلیوز سیٹ یا کاپی کرتا ہے۔ اقدار اسکیلر آفسیٹ، یا ٹیگز کے لیے آفسیٹ فہرستیں ہو سکتی ہیں جو بار بار ملتی ہیں (مؤخر الذکر کو ٹرائی ڈھانچے کا استعمال کرتے ہوئے مؤثر طریقے سے پیش کیا جا سکتا ہے)۔ ٹی ڈی ایف اے میں باقاعدہ اظہار اور رجسٹروں میں ٹیگز کے درمیان کوئی ون ٹو ون میپنگ نہیں ہے: ایک ہی ٹیگ کے لیے بہت سے رجسٹروں کی ضرورت پڑ سکتی ہے، اور ایک ہی رجسٹر میں مختلف ٹیگز کی اقدار ہو سکتی ہیں۔ مندرجہ ذیل تعریف ٹریفیمووچ اور بورسوٹی کے مطابق ہے۔ لوریکاری کی اصل تعریف قدرے مختلف ہے۔ ٹیگ کیا گیا ڈیٹرمینیسٹک فائنٹ آٹومیٹن ایک ٹپل ہے، جہاں: علامتوں کا ایک محدود مجموعہ ہے (حروف تہجی) ٹیگز کا ایک محدود مجموعہ ابتدائی حالت کے ساتھ ریاستوں کا ایک محدود مجموعہ ہے اور فائنل اسٹیٹس کا ایک ذیلی مجموعہ رجسٹروں کا ایک محدود مجموعہ ہے جس کے ساتھ فائنل رجسٹروں کا ایک ذیلی مجموعہ (ایک فی ٹیگ) ایک ٹرانزیشن فنکشن ہے، جہاں درج ذیل اقسام کے رجسٹر آپریشنز کا ایک مجموعہ ہے: رجسٹر کو صفر پر یا موجودہ پوزیشن پر سیٹ کریں:، جہاں رجسٹر کرنے کے لیے کاپی رجسٹر: رجسٹر کو رجسٹر کرنے اور تاریخ کو شامل کرنے کے لیے کاپی کریں:، جہاں مثال شکل 0 پر ایک سٹرنگ ہے، حروف تہجی کے ساتھ باقاعدہ اظہار کے لیے ایک مثال ٹی ڈی ایف اے اور ٹیگز کا ایک مجموعہ دکھاتا ہے جو کم از کم ایک علامت کے ساتھ فارم کے سٹرنگز سے میل کھاتا ہے۔ ٹی ڈی ایف اے کی چار ریاستیں ہیں جن میں سے تین حتمی ہیں۔ رجسٹروں کا سیٹ حتمی رجسٹروں کے ذیلی سیٹ کے ساتھ ہوتا ہے جہاں رجسٹر-th ٹیگ سے مطابقت رکھتا ہے۔ ٹرانزیشنز میں افعال کی طرف سے متعین کارروائیاں ہوتی ہیں، اور حتمی حالتوں میں افعال کی طرف سے متعین کارروائیاں ہوتی ہیں (وسیع ٹپ والے تیر سے نشان زد)۔ مثال کے طور پر، سٹرنگ سے مماثل ہونے کے لیے، ایک شخص اسٹیٹ 0 سے شروع ہوتا ہے، پہلے سے میل کھاتا ہے اور اسٹیٹ 1 پر چلا جاتا ہے (رجسٹروں کو غیر متعین اور موجودہ پوزیشن 0 پر ترتیب دینا)، دوسرے سے میل کھاتا ہے اور لوپس کو اسٹیٹ 1 سے ملاتا ہے (رجسٹر ویلیوز اب ہیں)، میچ کرتا ہے اور اسٹیٹ 2 پر چلا جاتا ہے (رجسٹر ویلیوز اب ہیں)، اسٹیٹ 2 میں حتمی کارروائیوں کو انجام دیتا ہے (رجسٹر ویلیوز اب ہیں) اور آخر میں ٹی ڈی ایف اے سے باہر نکل جاتا ہے۔ پیچیدگی کینونکل ڈی ایف اے شناخت کے مسئلے کو لکیری وقت میں حل کرتا ہے۔ ٹی ڈی ایف اے کے لیے بھی ایسا ہی ہے، کیونکہ رجسٹروں اور رجسٹر آپریشنز کی تعداد طے شدہ ہوتی ہے اور اس کا انحصار صرف باقاعدہ اظہار پر ہوتا ہے، لیکن ان پٹ کی لمبائی پر نہیں۔ سب میچ نکالنے پر اوور ہیڈ کا انحصار باقاعدہ اظہار میں ٹیگ کی کثافت اور ہر ٹیگ کی غیر تعیناتی ڈگری (ایک ہی ٹی ڈی ایف اے ریاست میں ٹیگ کی تمام ممکنہ اقدار کو ٹریک کرنے کے لیے درکار رجسٹروں کی زیادہ سے زیادہ تعداد) پر ہوتا ہے۔ ایک انتہا پر، اگر کوئی ٹیگز نہیں ہیں، تو ٹی ڈی ایف اے کینونکل ڈی ایف اے سے ملتا جلتا ہے۔ دوسری طرف، اگر ہر ذیلی اظہار کو ٹیگ کیا جاتا ہے، تو ایک ٹی ڈی ایف اے مؤثر طریقے سے مکمل تجزیہ انجام دیتا ہے اور ہر منتقلی پر اس کے بہت سے آپریشن ہوتے ہیں۔ عملی طور پر چند ذیلی میچ گروپوں کے ساتھ حقیقی دنیا کے باقاعدہ تاثرات کے لیے کینونکل ڈی ایف اے کے ساتھ مماثلت کے مقابلے میں اوور ہیڈ نہ ہونے کے برابر ہے۔ ٹی ڈی ایف اے کی تعمیر چند مراحل میں کی جاتی ہے۔ سب سے پہلے، ایک باقاعدہ اظہار کو ٹیگ شدہ غیر متعین محدود آٹومیٹن (ٹی این ایف اے) میں تبدیل کیا جاتا ہے۔ دوسرا، ایک ٹی این ایف اے کو تعین کے طریقہ کار کا استعمال کرتے ہوئے ٹی ڈی ایف اے میں تبدیل کیا جاتا ہے۔ اس مرحلے میں ابہام بھی شامل ہے جو مبہم ٹی این ایف اے راستوں کے درمیان تنازعات کو حل کرتا ہے۔ اس کے بعد، ایک ٹی ڈی ایف اے اختیاری طور پر متعدد اصلاحات سے گزر سکتا ہے جو رجسٹروں اور کارروائیوں کی تعداد کو کم کرتے ہیں، بشمول کم سے کم کرنا جو ریاستوں کی تعداد کو کم کرتا ہے۔ سیڈو کوڈ کے ساتھ ٹی ڈی ایف اے کی تعمیر کے تمام مراحل کے لیے الگورتھم بورسوٹی اور ٹریفیمووچ کے ذریعے کاغذ میں دیے گئے ہیں۔ یہ سیکشن باقاعدہ اظہار کی مثال پر ٹی ڈی ایف اے کی تعمیر کی وضاحت کرتا ہے، جہاں ایک ٹیگ ہے اور حروف تہجی کی علامتیں ہیں۔ ٹیگ شدہ این ایف اے ٹی این ایف اے ٹیگ شدہ ε-ٹرانزیشن کے ساتھ ایک غیر متعین محدود آٹومیٹن ہے۔ اسے سب سے پہلے لوریکاری نے بیان کیا تھا، حالانکہ اسی طرح کی تعمیرات کو بہت پہلے میلی مشینوں اور غیر متعین محدود ریاستی ٹرانسڈیوسر کے نام سے جانا جاتا تھا۔ ٹی این ایف اے کی تعمیر تھامسن کی تعمیر سے بہت ملتی جلتی ہے: یہ باقاعدہ اظہار کی ساخت کی عکاسی کرتی ہے۔ اہم بات یہ ہے کہ ٹی این ایف اے باقاعدہ اظہار میں ابہام کو برقرار رکھتا ہے: اگر کسی سٹرنگ کو دو مختلف طریقوں سے ملانا ممکن ہے، تو اس باقاعدہ اظہار کے لیے ٹی این ایف اے کے پاس اس سٹرنگ کے لیے دو مختلف قبولیت کے راستے ہیں۔ بورسوٹی اور ٹریفیمووچ کی طرف سے ٹی این ایف اے کی تعریف لوریکری کی طرف سے اصل سے مختلف ہے جس میں ٹی این ایف اے میں ٹرانزیشن پر منفی ٹیگ ہو سکتے ہیں: جب ٹیگ شدہ ٹرانزیشن کے لیے بائی پاس ہوتا ہے تو ان صورتوں میں میچ کی عدم موجودگی کو واضح کرنے کی ضرورت ہوتی ہے۔ شکل 1 ٹی این ایف اے کو باقاعدہ اظہار کی مثال کے طور پر دکھاتا ہے۔ اس میں تین قسم کی منتقلی ہوتی ہے: حروف تہجی کی علامتوں پر منتقلی (گہرا نیلا)، ٹیگ شدہ ε-منتقلی (ریاست 4 سے ریاست 12 میں ٹیگ کے ساتھ اور ریاست 10 سے ریاست 11 میں منفی ٹیگ، روشن سبز کے ساتھ)، اور غیر ٹیگ شدہ ε-منتقلی (ہلکا نیلا)۔ ٹی این ایف اے میں ایک واحد اسٹارٹ اسٹیٹ 0 اور ایک واحد فائنل اسٹیٹ 11 ہے۔ ٹی این ایف اے کے تعین کو سمجھنے کے لیے، یہ پہلے ٹی این ایف اے کے تخروپن کو سمجھنے میں مدد کرتا ہے۔ کینونکل ε-NFA تخروپن کو یاد کریں: یہ ابتدائی حالت کے ε-بندش کے طور پر فعال حالتوں کے ذیلی سیٹ کی تعمیر کرتا ہے، اور پھر ایک لوپ میں بار بار اگلے ان پٹ علامت پر قدم رکھتا ہے اور فعال حالت سیٹ کے ε-بندش کی تعمیر کرتا ہے۔ آخر کار لوپ ختم ہو جاتا ہے: یا تو فعال سیٹ خالی ہو جاتا ہے (جس کا مطلب ہے ناکامی)، یا تمام ان پٹ علامتیں ختم ہو جاتی ہیں (جس کا مطلب ہے کامیابی اگر فعال سیٹ میں حتمی حالت ہو، بصورت دیگر ناکامی)۔ ٹی این ایف اے تخروپن اسی طرح کا ہے، لیکن یہ اضافی طور پر ٹیگ کی اقدار کو ٹریک کرتا ہے۔ ہر بار جب تخروپن کا سامنا ٹیگ شدہ منتقلی سے ہوتا ہے، تو یہ ٹیگ ویلیو کو موجودہ آفسیٹ میں اپ ڈیٹ کرتا ہے۔ چونکہ تخروپن بیک وقت متعدد غیر متعین راستوں کا سراغ لگاتا ہے، اس لیے ان راستوں پر ٹیگ کی اقدار مختلف ہو سکتی ہیں اور انہیں الگ سے ٹریک کیا جانا چاہیے۔ ایک اور مشکل ابہام کی ضرورت ہے: کینونکل این ایف اے تخروپن کے برعکس، ٹی این ایف اے تخروپن کو مبہم راستوں میں فرق کرنے کی ضرورت ہے، کیونکہ ان میں ٹیگ کی مختلف اقدار ہو سکتی ہیں۔ شکل 2 ایک سٹرنگ پر ٹی این ایف اے تخروپن کی ایک مثال دکھاتا ہے: مبہم مبہم کا مطلب ایک ہی ان پٹ کے لیے متعدد مختلف پارس درختوں کا وجود ہے۔ یہ ایک باقاعدہ اظہار کی خاصیت ہے ؛ ابہام کو ٹی این ایف اے کی تعمیر کے ذریعے محفوظ رکھا جاتا ہے اور ٹی این ایف اے کے تخروپن یا تعین کے دوران حل ہو جاتا ہے۔ ابہام کو حل کرنے کا ایک طریقہ یہ ہے کہ ابہام کی پالیسی کا استعمال کیا جائے، جس کی سب سے قابل ذکر مثال بائیں طرف کی لالچی اور طویل ترین میچ (پوزیکس) پالیسیاں ہیں۔ سب سے بائیں طرف کی لالچی پالیسی کی تعریف باقاعدہ اظہار کے ڈھانچے کے لحاظ سے کی گئی ہے ؛ یہ ایک سادہ اور موثر نفاذ کو تسلیم کرتی ہے۔ دوسری طرف پوزیکس پالیسی کو تجزیہ کے نتائج کے ڈھانچے کے لحاظ سے بیان کیا گیا ہے۔ اس پر عمل درآمد کرنا زیادہ مشکل ہے اور کمپیوٹیشنل طور پر بائیں طرف کی لالچی پالیسی سے زیادہ پیچیدہ ہے۔ ٹی ڈی ایف اے دونوں پالیسیوں کے ساتھ کام کر سکتا ہے، اور ابہام پر کوئی رن ٹائم اوور ہیڈ نہیں ہے، کیونکہ یہ تعین کے دوران ہوتا ہے اور ٹی ڈی ایف اے ڈھانچے میں بن جاتا ہے۔ دوسری طرف، ٹی این ایف اے تخروپن کے لیے، ابہام پر گزارا گیا وقت رن ٹائم میں شامل ہوتا ہے۔ باقاعدہ اظہار کی مثال جان بوجھ کر مبہم ہے، کیونکہ یہ کسی کو دو مختلف طریقوں سے تجزیہ کرنے کی اجازت دیتی ہے: یا تو بائیں متبادل کے طور پر، یا دائیں متبادل کے طور پر۔ اس بات پر منحصر ہے کہ کس متبادل کو ترجیح دی جاتی ہے، ٹیگ کی یا تو قدر ہونی چاہیے (علامتوں اور کے درمیان پوزیشن پر آفسیٹ)، یا (غیر متعین)۔ پوزیکس اور بائیں طرف کی لالچی ابہام کی پالیسیاں دونوں اس بات پر متفق ہیں کہ اس معاملے میں پہلا متبادل بہتر ہے۔ تعین ٹی این ایف اے کا تعین کینونکل پاور سیٹ کنسٹرکشن الگورتھم پر مبنی ہے جو این ایف اے کو ڈی ایف اے میں تبدیل کرتا ہے۔ الگورتھم تمام ممکنہ تاروں پر این ایف اے کی تقلید کرتا ہے۔ تخروپن کے ہر مرحلے پر، این ایف اے ریاستوں کا فعال مجموعہ ایک نئی ڈی ایف اے ریاست بناتا ہے۔ اگر نئی ریاست موجودہ ڈی ایف اے ریاست سے ملتی جلتی ہے، تو اسے مسترد کر دیا جاتا ہے اور موجودہ کے ساتھ تبدیل کر دیا جاتا ہے، اور تخروپن کی موجودہ شاخ ختم ہو جاتی ہے۔ بصورت دیگر نئی ریاست کو ڈی ایف اے ریاستوں کے بڑھتے ہوئے سیٹ میں شامل کیا جاتا ہے اور اس ریاست سے تخروپن جاری رہتا ہے۔ بالآخر تعین ختم ہو جاتا ہے: اگرچہ تمام ممکنہ تاروں کا مجموعہ لامحدود ہے، مختلف ڈی ایف اے ریاستوں کا مجموعہ محدود ہے، اور کسی وقت تمام نئی ریاستیں موجودہ ریاستوں سے ملتی جلتی ہو جاتی ہیں۔ ٹی ڈی ایف اے کے معاملے میں سادہ پاور سیٹ کی تعمیر کو ایک مسئلے کا سامنا کرنا پڑتا ہے: ٹی ڈی ایف اے ریاستوں میں ٹیگ کی معلومات ہوتی ہیں، جو تخروپن کے ہر مرحلے پر تبدیل ہوتی ہیں (جیسے جیسے آفسیٹ بڑھتے ہیں)۔ یہ ٹی ڈی ایف اے ریاستوں کو نقشہ سازی سے روکتا ہے: ریاستوں کا ایک جوڑا جس میں ایک جیسی ٹی این ایف اے ریاستیں ہوتی ہیں لیکن مختلف ٹیگ آفسیٹ ایک جیسے نہیں ہوتے ہیں اور ان کا نقشہ نہیں بنایا جا سکتا۔ نتیجے کے طور پر، تخروپن غیر معینہ مدت تک جاری رہتا ہے، ٹی ڈی ایف اے ریاستوں کا مجموعہ بڑھتا ہے، اور تعین ختم نہیں ہوتا ہے۔ اس مسئلے کو حل کرنے کے لیے، لوریکری نے ان ڈائرکشن کے خیال کو لاگو کیا: ٹی ڈی ایف اے ریاستوں میں فوری ٹیگ ویلیوز کو محفوظ کرنے کے بجائے، انہوں نے انہیں بالواسطہ طور پر رجسٹروں میں محفوظ کرنے کا مشورہ دیا۔ رجسٹر میں ٹیگ کی اقدار مختلف ہو سکتی ہیں، لیکن اس سے کوئی فرق نہیں پڑتا جب تک کہ رجسٹر ایک جیسے ہوں۔ یہ اختتامی مسئلہ کو حل کرتا ہے: یہاں تک کہ اگر ٹی ڈی ایف اے ریاستوں کے مختلف رجسٹر ہوں، تو انہیں متعلقہ رجسٹر ویلیوز کی نقل کرنے والی کارروائیوں کو شامل کرکے یکساں (ایک دوسرے کے ساتھ نقشہ بند) بنایا جا سکتا ہے۔ ہدایت مفت نہیں ہے: اس کے لیے ٹرانزیشن پر رن ٹائم رجسٹر آپریشنز کو شامل کرنے کی ضرورت ہوتی ہے جو رجسٹر ویلیوز کو اپ ڈیٹ کرتے ہیں۔ رن ٹائم اوور ہیڈ کو کم کرنے کے لیے، ٹریفیمووچ نے لک ہیڈ آپٹیمائزیشن کا استعمال کیا۔ خیال یہ ہے کہ رجسٹر آپریشنز کو ٹی ڈی ایف اے ریاست میں آنے والی منتقلی سے اس ریاست سے باہر جانے والی منتقلی میں منتقل کیا جائے۔ اس طرح آپریشنز لک ہیڈ کی علامت پر تقسیم ہو جاتے ہیں، جس سے رجسٹر لائف ٹائمز کے درمیان اوورلیپ کم ہو جاتا ہے اور اس کے نتیجے میں تیز تر ٹی ڈی ایف اے ہوتا ہے۔ اس اصلاح کو استعمال کرنے کے لیے، زیر تعمیر ہر ٹی ڈی ایف اے ریاست میں لک ہیڈ ٹیگز کو ٹریک کرنا اور ٹی ڈی ایف اے ریاستوں کی نقشہ سازی کرتے وقت انہیں مدنظر رکھنا ضروری ہے۔ شکل 3 چل رہی مثال کے لیے تعین کے عمل کو ظاہر کرتی ہے۔ شکل 4 نتیجے میں آنے والے ٹی ڈی ایف اے کو دکھاتا ہے۔ اصلاح کا مقصد ٹی ڈی ایف اے کے سائز اور رجسٹروں کی تعداد اور ٹرانزیشن پر کارروائیوں کو کم کرنا ہے۔ یہ سیکشن کچھ اصلاحات کی وضاحت کرتا ہے جو عملی ٹی ڈی ایف اے کے نفاذ میں استعمال ہوتے ہیں۔ ان میں سے کوئی بھی اصلاح ٹی ڈی ایف اے آپریشن کے لیے خاص طور پر پیچیدہ یا اہم نہیں ہے، لیکن جب ایک ساتھ اور صحیح ترتیب میں لاگو کیا جائے تو وہ ٹی ڈی ایف اے کو کافی تیز اور چھوٹا بنا سکتے ہیں۔ فکسڈ ٹیگز آپٹیمائزیشن کا اطلاق باقاعدہ اظہار کی سطح پر (ٹی این ایف اے کی تعمیر سے پہلے) کیا جاتا ہے۔ خیال یہ ہے کہ اگر ٹیگز کا ایک جوڑا ایک دوسرے سے مقررہ فاصلے کے اندر ہوتا ہے تو ان دونوں کو ٹریک کرنے کی ضرورت نہیں ہے: ایک ٹیگ کی قیمت کا حساب دوسرے ٹیگ کی قیمت سے ایک فکسڈ آفسیٹ شامل کرکے کیا جا سکتا ہے۔ مثال کے طور پر، باقاعدہ اظہار ٹیگز میں اور ایک دوسرے سے ایک علامت کے فاصلے کے اندر ہیں، لہذا اس کا حساب اس طرح لگایا جا سکتا ہے۔ یہ اصلاح ٹی ڈی ایف اے کی تعمیر کے وقت (کیونکہ فکسڈ ٹیگز کو ٹی این ایف اے کی تعمیر اور تعین سے خارج کر دیا گیا ہے) اور مماثل وقت (کیونکہ رجسٹر آپریشنز کم ہیں) دونوں کو کم کر سکتی ہے۔ ٹی ڈی ایف اے کی تعمیر کے بعد رجسٹر کی اصلاح کا اطلاق ہوتا ہے۔ ٹی ڈی ایف اے رجسٹروں پر کنٹرول فلو گراف (سی ایف جی) کو شامل کرتا ہے: ٹرانزیشن پر کارروائیاں بنیادی بلاکس بناتی ہیں، اور دو بلاکس کے درمیان ایک آرک ہوتا ہے اگر ان میں سے ایک دوسرے سے ٹی ڈی ایف اے ٹرانزیشن کے ذریعے قابل رسائی ہو، دوسرے رجسٹر آپریشنز سے گزرے بغیر۔ سی ایف جی رجسٹروں پر ایک پروگرام کو متغیر کے طور پر پیش کرتا ہے، لہذا معمول کے مرتب کی اصلاح اس پر لاگو کی جا سکتی ہے (جیسے زندہ تجزیہ، ڈیڈ کوڈ کا خاتمہ اور رجسٹر الاٹمنٹ)۔ ٹی ڈی ایف اے کم سے کم کرنا ڈی ایف اے کم سے کم کرنے سے بہت ملتا جلتا ہے، سوائے ایک اضافی پابندی کے: ٹی ڈی ایف اے منتقلی پر رجسٹر کے اقدامات کو مدنظر رکھنا ضروری ہے۔ لہذا، ٹی ڈی ایف اے کا کہنا ہے کہ جو ایک جیسے ہیں، لیکن ایک ہی علامت پر آنے والی منتقلی پر مختلف رجسٹر ایکشن ہیں، انہیں ضم نہیں کیا جا سکتا۔ ڈی ایف اے کم سے کم کرنے کے لیے تمام معمول کے الگورتھم کو ٹی ڈی ایف اے کم سے کم کرنے کے لیے ڈھالا جا سکتا ہے، مثال کے طور پر مور کا الگورتھم آر ای 2 سی لیکسر جنریٹر میں استعمال ہوتا ہے۔ شکل 5 باقاعدہ اظہار کے لیے ایک بہتر ٹی ڈی ایف اے دکھاتی ہے۔ نوٹ کریں کہ یہ حقیقت میں لفظی طور پر مساوی باقاعدہ اظہار کے لیے ٹی ڈی ایف اے کی طرح ہے، جہاں ابہام کو ہٹا دیا گیا ہے۔ تعین کے دوران ابہام کو حل کیا جاتا ہے، اور شکل 4 پر غیر مرضی کے مطابق ٹی ڈی ایف اے غیر واضح ہے، لیکن اس میں کچھ بلٹ ان فالتو پن ہے جسے اصلاح کے ذریعے دور کیا جا سکتا ہے۔ رجسٹر کے ساتھ ملٹی پاس ٹی ڈی ایف اے ٹی ڈی ایف اے وقت سے پہلے تعین کے لیے اچھی طرح سے موزوں ہے، جب ٹی ڈی ایف اے کی تعمیر پر خرچ ہونے والا وقت رن ٹائم میں شامل نہیں ہوتا ہے (جیسے۔ لیکسر جنریٹرز میں)۔ لیکن صرف وقت پر تعین کے لیے (مثال کے طور پر۔ باقاعدہ اظہار لائبریریوں میں) ٹی ڈی ایف اے کی تعمیر کے وقت کو کم کرنا مطلوب ہے۔ ایک اور تشویش باقاعدہ اظہار میں ٹیگ کی کثافت ہے: اگر ٹیگز کی تعداد نسبتا کم ہے تو رجسٹر کے ساتھ ٹی ڈی ایف اے موثر ہے۔ لیکن بہت زیادہ ٹیگ کیے گئے باقاعدہ تاثرات کے لیے رجسٹر کے ساتھ ٹی ڈی ایف اے سب آپٹیمل ہیں: ٹرانزیشن آپریشنز کے ساتھ بے ترتیب ہو جاتی ہیں، جس سے ٹی ڈی ایف اے پر عمل درآمد سست ہو جاتا ہے۔ لائیونیس اور مداخلت کی معلومات کے سائز کی وجہ سے رجسٹر آپٹیمائزیشن بھی پریشانی کا باعث بن جاتی ہے۔ ملٹی پاس ٹی ڈی ایف اے دونوں مسائل کو حل کرتا ہے: وہ ٹی ڈی ایف اے کی تعمیر کے وقت کو کم کرتے ہیں، اور وہ گھنے ذیلی میچ نکالنے کے لیے بہتر موزوں ہیں۔ کینونکل ٹی ڈی ایف اے کے ساتھ بنیادی فرق یہ ہے کہ ملٹی پاس ٹی ڈی ایف اے کا کوئی رجسٹر آپریشن نہیں ہے۔ اس کے بجائے ان کے پاس متعدد پاس ہوتے ہیں: ایک فارورڈ پاس جو ان پٹ سٹرنگ سے میل کھاتا ہے اور ٹی ڈی ایف اے ریاستوں کی ترتیب کو ریکارڈ کرتا ہے، اور ایک یا زیادہ بیکورڈ پاس جو ریکارڈ شدہ ریاستوں سے گزرتے ہیں اور سب میچ کی معلومات جمع کرتے ہیں۔ ایک بیکورڈ پاس کافی ہے، لیکن ایک اضافی پاس استعمال کیا جا سکتا ہے۔ ذیلی میچ کے نتائج کے لیے میموری کی ضروری مقدار کا اندازہ لگانا۔ ٹی ڈی ایف اے ریاستوں کے سلسلے سے مماثل ٹی این ایف اے راستے کا سراغ لگانے کے لیے، ملٹی پاس ٹی ڈی ایف اے ٹرانزیشن اور حتمی حالتوں میں بیک لنکس کا استعمال کرتا ہے۔ بیک لنک ایک جوڑا ہے، جہاں پہلا جزو پچھلی منتقلی پر بیک لنک صفوں میں ایک انڈیکس ہے، اور دوسرا جزو ٹی ڈی ایف اے ریاستوں کے درمیان ٹی این ایف اے راستے کے ایک ٹکڑے کے لیے ٹیگز کا ایک سلسلہ ہے۔ شکل 6 سٹرنگ پر باقاعدہ اظہار کے ملاپ کے لیے ملٹی پاس ٹی ڈی ایف اے کی ایک مثال دکھاتا ہے (اس کا موازنہ شکل 0 سے کریں جو ٹی ڈی ایف اے کو اسی باقاعدہ اظہار کے لیے رجسٹروں کے ساتھ دکھاتا ہے): فارورڈ پاس ریاستوں کی ترتیب 0، 1، 1، 2 جمع کرتا ہے۔ بیکورڈ پاس اسٹیٹ 2 سے اسٹیٹ 0 تک بیک لنکس کا سراغ لگاتا ہے اور ٹیگ کے سلسلے اور ان پٹ علامتوں کو جوڑتا ہے۔ یہ بیک لنک سے شروع ہوتا ہے۔ ٹیگ شدہ سٹرنگ ہے۔ انڈیکس 0 ریاست 1 سے ریاست 2 میں پچھلی منتقلی پر بیک لنک کا انتخاب کرتا ہے (اس منتقلی پر واحد)۔ ٹیگ شدہ سٹرنگ بن جاتی ہے۔ انڈیکس 0 ریاست 1 سے ریاست 1 میں پچھلی لوپنگ منتقلی پر بیک لنک کا انتخاب کرتا ہے۔ ٹیگ شدہ سٹرنگ بن جاتی ہے۔ انڈیکس 0 ریاست 0 سے ریاست 1 میں پچھلی منتقلی پر بیک لنک کا انتخاب کرتا ہے۔ نتیجے میں ٹیگ کی گئی سٹرنگ ہے۔ اس میں ہر ٹیگ کے لیے آخری آفسیٹ یا آفسیٹ فہرستیں دوبارہ بنانے کے لیے تمام ضروری معلومات شامل ہیں۔ محمد عمران چودھری کی طرف سے بیان کردہ متعلقہ آٹومیٹا اسٹیڈفا ٹی ڈی ایف اے سے بہت ملتا جلتا ہے، سوائے اس کے کہ ان کے رجسٹرڈ آپریشن ریاستوں میں ہیں، ٹرانزیشن پر نہیں۔ ڈی ایس ایس ٹی (ڈیٹرمینیسٹک اسٹریمنگ سٹرنگ ٹرانسڈیوسرز) جو گراتھول کے ذریعے بیان کیے گئے ہیں، ٹی ڈی ایف اے کے زیادہ دور کے رشتہ دار ہیں، جو ذیلی میچ نکالنے کے مقابلے میں مکمل تجزیہ کے لیے بہتر موزوں ہیں۔ ڈی ایس ایس ٹی ریاستوں میں ε-بندش کے ذریعے بنائے گئے راستے کے درخت ہوتے ہیں، جبکہ ٹی ڈی ایف اے ریاستوں میں ایک سڑی ہوئی شکل (رجسٹر ورژن اور لک ہیڈ ٹیگز) میں اسی طرح کی معلومات ہوتی ہیں۔ حوالہ جات فائنائٹ آٹومیٹا