Tagged Deterministic Finite Automaton
অটোমাটা তত্ত্বে, একটি ট্যাগ করা ডিটারমিনিস্টিক ফাইনাইট অটোমেটন (টি. ডি. এফ. এ) হল ডিটারমিনিস্টিক ফাইনাইট অটোমেটন (ডি. এফ. এ)-এর একটি সম্প্রসারণ। নিয়মিত ভাষার স্বীকৃতির সমস্যা সমাধানের পাশাপাশি, টি. ডি. এফ. এ সাবম্যাচ এক্সট্রাকশন এবং পার্সিং করতেও সক্ষম। যদিও ক্যানোনিকাল ডি. এফ. এ একটি স্ট্রিং নিয়মিত এক্সপ্রেশন দ্বারা সংজ্ঞায়িত ভাষার অন্তর্গত কিনা তা খুঁজে বের করতে পারে, টি. ডি. এফ. এ নির্দিষ্ট সাব-এক্সপ্রেশনগুলির সাথে মেলে এমন সাবস্ট্রিংও বের করতে পারে। আরও সাধারণভাবে, টি. ডি. এফ. এ ইনপুট স্ট্রিং-এ এমন অবস্থানগুলি সনাক্ত করতে পারে যা নিয়মিত অভিব্যক্তিতে ট্যাগ করা অবস্থানগুলির সাথে মেলে (ট্যাগগুলি বন্ধনী ক্যাপচার করার মতো মেটা-প্রতীক, তবে জুটির প্রয়োজনীয়তা ছাড়াই)। 2000 সালে ভিল লরিকারি প্রথম টি. ডি. এফ. এ-র ইতিহাস বর্ণনা করেন। এর আগে এটি অজানা ছিল যে একটি নির্ধারিত সীমাবদ্ধ-অবস্থা স্বয়ংক্রিয় পদ্ধতিতে একটি পাসে সাবম্যাচ নিষ্কাশন করা সম্ভব কিনা, তাই এই কাগজটি একটি গুরুত্বপূর্ণ অগ্রগতি ছিল। লৌরিকারি টি. ডি. এফ. এ নির্মাণের বর্ণনা দিয়েছেন এবং প্রমাণ দিয়েছেন যে নির্ধারণ প্রক্রিয়াটি শেষ হয়ে গেছে, তবে অ্যালগরিদম দ্ব্যর্থতা নিরসনকে সঠিকভাবে পরিচালনা করেনি। 2007 সালে ক্রিস কুক্লেউইজ একটি হাস্কেল লাইব্রেরি রেগেক্স-টি. ডি. এফ. এ-তে পি. ও. এস. আই. এক্স-এর দীর্ঘতম-ম্যাচ শব্দার্থবিদ্যা সহ টি. ডি. এফ. এ প্রয়োগ করেন। কুক্লেউইজ অ্যালগরিদমটির একটি অনানুষ্ঠানিক বিবরণ দিয়েছেন এবং প্রধান প্রশ্নের উত্তর দিয়েছেন যে টি. ডি. এফ. এ পোসিক্স দীর্ঘতম-ম্যাচ দ্ব্যর্থতা নিরসন করতে সক্ষম কিনা, যা অন্যান্য গবেষকদের দ্বারা সন্দেহ করা হয়েছিল। 2017 সালে উলিয়া ট্রাফিমোভিচ টি. ডি. এফ. এ-কে এক-প্রতীকী চেহারা দিয়ে বর্ণনা করেছেন। লুকহেড প্রতীকের ব্যবহার টি. ডি. এফ. এ-তে রেজিস্টার এবং রেজিস্টার ক্রিয়াকলাপের সংখ্যা হ্রাস করে, যা এটিকে লরিকারি টি. ডি. এফ. এ-এর চেয়ে দ্রুত এবং প্রায়শই ছোট করে তোলে। ট্রাফিমোভিচ এলআর পার্সার এলআর (1) এবং এলআর (0)-এর সাথে সাদৃশ্য রেখে লুকহেড টিডিএফএ (1) এবং টিডিএফএ (0) সহ এবং ছাড়াই টিডিএফএ রূপগুলি ডাকেন। এই অ্যালগরিদমটি ওপেন-সোর্স লেক্সার জেনারেটর আরই2সি-তে প্রয়োগ করা হয়েছিল। ট্রাফিমোভিচ কুক্লেউইজ দ্ব্যর্থতা নিরসন অ্যালগরিদমকে আনুষ্ঠানিক করেছেন। 2018 সালে অ্যাঞ্জেলো বোরসোটি টি. ডি. এফ. এ-র একটি পরীক্ষামূলক জাভা বাস্তবায়নে কাজ করেছিলেন; এটি পরে 2021 সালে প্রকাশিত হয়েছিল। 2019 সালে বোরসোটি এবং ট্রাফিমোভিচ ওকুই এবং সুজুকি দ্বারা পি. ও. এস. আই. এক্স দ্ব্যর্থতা নিরসন অ্যালগরিদমকে টি. ডি. এফ. এ-তে রূপান্তরিত করেন। তারা নতুন অ্যালগরিদমের সঠিকতার একটি আনুষ্ঠানিক প্রমাণ দিয়েছেন এবং দেখিয়েছেন যে এটি অনুশীলনে কুক্লেউইজ অ্যালগরিদমের চেয়ে দ্রুত। 2020 সালে ট্রাফিমোভিচ আরই2সি-তে টিডিএফএ বাস্তবায়ন সম্পর্কে একটি নিবন্ধ প্রকাশ করেন। 2022 সালে বোরসোটি এবং ট্রাফিমোভিচ টি. ডি. এফ. এ নির্মাণের বিস্তারিত বিবরণ সহ একটি গবেষণাপত্র প্রকাশ করেন। গবেষণাপত্রে তাদের অতীতের গবেষণাকে অন্তর্ভুক্ত করা হয়েছে এবং মাল্টি-পাস টি. ডি. এফ. এ উপস্থাপন করা হয়েছে যা সময়মতো নির্ধারণের জন্য আরও উপযুক্ত। তারা অন্যান্য অ্যালগরিদমের সাথে টি. ডি. এফ. এ-কে তুলনা করে এবং মানদণ্ড প্রদান করে। আনুষ্ঠানিক সংজ্ঞা টি. ডি. এফ. এ-র সাধারণ ডি. এফ. এ-র মতো একই মৌলিক কাঠামো রয়েছেঃ রূপান্তর দ্বারা সংযুক্ত অবস্থার একটি সীমাবদ্ধ সেট। এছাড়াও, টি. ডি. এফ. এ-র রেজিস্টারের একটি নির্দিষ্ট সেট রয়েছে যা ট্যাগ মান ধারণ করে এবং রেজিস্টারের মানগুলি সেট বা অনুলিপি করে এমন ট্রানজিশনে অপারেশনগুলি রেজিস্টার করে। মানগুলি স্কেলার অফসেট হতে পারে, অথবা ট্যাগগুলির জন্য অফসেট তালিকা হতে পারে যা বারবার মেলে (পরেরটি একটি ট্রাই কাঠামো ব্যবহার করে দক্ষতার সাথে উপস্থাপন করা যেতে পারে)। নিয়মিত অভিব্যক্তিতে ট্যাগ এবং টি. ডি. এফ. এ-তে রেজিস্টারের মধ্যে কোনও ওয়ান-টু-ওয়ান ম্যাপিং নেইঃ একটি ট্যাগের জন্য অনেক রেজিস্টারের প্রয়োজন হতে পারে এবং একই রেজিস্টারে বিভিন্ন ট্যাগের মান থাকতে পারে। নিম্নলিখিত সংজ্ঞাটি ট্রাফিমোভিচ এবং বোরসোতির মতে। লৌরিকারির মূল সংজ্ঞাটি কিছুটা আলাদা। একটি ট্যাগ করা নির্ধারক সীমাবদ্ধ অটোমেটন হল একটি টুপল, যেখানেঃ প্রতীকগুলির একটি সীমাবদ্ধ সেট (বর্ণমালা) ট্যাগগুলির একটি সীমাবদ্ধ সেট প্রাথমিক অবস্থা সহ অবস্থার একটি সীমাবদ্ধ সেট এবং চূড়ান্ত অবস্থার একটি উপসেট হল চূড়ান্ত রেজিস্টারের একটি উপসেট সহ রেজিস্টারের একটি সীমাবদ্ধ সেট (প্রতি ট্যাগে একটি) একটি ট্রানজিশন ফাংশন একটি চূড়ান্ত ফাংশন, যেখানে নিম্নলিখিত ধরণের রেজিস্টার ক্রিয়াকলাপের একটি সেট রয়েছেঃ রেজিস্টারকে শূন্য বা বর্তমান অবস্থানে সেট করুনঃ, যেখানে নিবন্ধনের জন্য অনুলিপি রেজিস্টারঃ নিবন্ধনের জন্য রেজিস্টার কপি করুন এবং ইতিহাস যুক্ত করুনঃ, যেখানে উদাহরণ চিত্র 0-এর উপর একটি স্ট্রিং বর্ণমালার সাথে নিয়মিত অভিব্যক্তির জন্য একটি উদাহরণ টিডিএফএ দেখায় এবং ট্যাগগুলির একটি সেট যা কমপক্ষে একটি প্রতীকের সাথে ফর্মের স্ট্রিংয়ের সাথে মেলে। টি. ডি. এফ. এ-র চারটি রাজ্য রয়েছে যার মধ্যে তিনটি চূড়ান্ত। রেজিস্টারের সেটটি চূড়ান্ত রেজিস্টারের একটি উপসেট সহ যেখানে রেজিস্টার-তম ট্যাগের সাথে মিলে যায়। রূপান্তরগুলির ক্রিয়াকলাপগুলি ফাংশন দ্বারা সংজ্ঞায়িত করা হয় এবং চূড়ান্ত অবস্থার ক্রিয়াকলাপগুলি ফাংশন দ্বারা সংজ্ঞায়িত করা হয় (প্রশস্ত-টিপযুক্ত তীর দিয়ে চিহ্নিত)। উদাহরণস্বরূপ, স্ট্রিং মিলানোর জন্য, একটি 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-এ পূর্ববর্তী পরিবর্তনের ব্যাকলিংক নির্বাচন করে। ফলস্বরূপ ট্যাগ করা স্ট্রিং হল। প্রতিটি ট্যাগের জন্য শেষ অফসেট বা অফসেট তালিকা পুনর্গঠনের জন্য এতে সমস্ত প্রয়োজনীয় তথ্য রয়েছে। মহম্মদ ইমরান চৌধুরী দ্বারা বর্ণিত সম্পর্কিত স্বয়ংক্রিয় স্ট্যাডাটা টি. ডি. এফ. এ-র সাথে খুব মিল রয়েছে, তবে তাদের রাজ্যে রেজিস্টার অপারেশন রয়েছে, ট্রানজিশনে নয়। গ্র্যাথওল দ্বারা বর্ণিত ডি. এস. এস. টি (ডিটারমিনিস্টিক স্ট্রিমিং স্ট্রিং ট্রান্সডিউসার) টি. ডি. এফ. এ-র বেশি দূরবর্তী আত্মীয়, যা সাবম্যাচ এক্সট্রাকশনের চেয়ে সম্পূর্ণ পার্সিংয়ের জন্য বেশি উপযুক্ত। ডি. এস. এস. টি-তে ε-ক্লোজার দ্বারা নির্মিত পাথ ট্রি থাকে, যেখানে টি. ডি. এফ. এ-তে একটি পচানো আকারে অনুরূপ তথ্য থাকে (রেজিস্টার সংস্করণ এবং লুকহেড ট্যাগ)। তথ্যসূত্র সীমাবদ্ধ স্বয়ংক্রিয়