Tagged Deterministic Finite Automaton
ઓટોમેટા થિયરીમાં, ટેગ કરેલ નિર્ધારક મર્યાદિત ઓટોમેટન (ટી. ડી. એફ. એ.) એ નિર્ધારક મર્યાદિત ઓટોમેટન (ડી. એફ. એ.) નું વિસ્તરણ છે. નિયમિત ભાષાઓ માટે ઓળખની સમસ્યાને ઉકેલવા ઉપરાંત, ટી. ડી. એફ. એ. સબમેચ નિષ્કર્ષણ અને પદચ્છેદન કરવામાં પણ સક્ષમ છે. જ્યારે કેનોનિકલ ડી. એફ. એ. શોધી શકે છે કે સ્ટ્રિંગ નિયમિત અભિવ્યક્તિ દ્વારા વ્યાખ્યાયિત ભાષાની છે કે નહીં, ત્યારે ટી. ડી. એફ. એ. ચોક્કસ પેટા અભિવ્યક્તિઓ સાથે મેળ ખાતી સબસ્ટ્રિંગ્સ પણ કાઢી શકે છે. વધુ સામાન્ય રીતે, ટી. ડી. એફ. એ. ઇનપુટ સ્ટ્રિંગમાં સ્થિતિને ઓળખી શકે છે જે નિયમિત અભિવ્યક્તિમાં ટેગ કરેલી સ્થિતિ સાથે મેળ ખાય છે (ટેગ એ મેટા-પ્રતીકો છે જે કૌંસને કબજે કરવા સમાન છે, પરંતુ જોડીની જરૂરિયાત વિના). ઇતિહાસ ટી. ડી. એફ. એ. નું વર્ણન સૌપ્રથમ 2000 માં વિલે લૌરિકારી દ્વારા કરવામાં આવ્યું હતું. તે પહેલાં તે અજ્ઞાત હતું કે શું નિર્ધારિત મર્યાદિત-સ્થિતિ ઓટોમેટન પર એક પાસમાં સબમેચ નિષ્કર્ષણ કરવું શક્ય છે કે નહીં, તેથી આ પેપર એક મહત્વપૂર્ણ પ્રગતિ હતી. લૌરિકારીએ ટી. ડી. એફ. એ. ની રચનાનું વર્ણન કર્યું અને એ વાતનો પુરાવો આપ્યો કે નિર્ધારણ પ્રક્રિયા સમાપ્ત થાય છે, જો કે અલ્ગોરિધમ અસ્પષ્ટતાને યોગ્ય રીતે સંભાળી શક્યું ન હતું. 2007માં ક્રિસ કુક્લેવિઝે હાસ્કેલ લાઈબ્રેરી રેગેક્સ-ટી. ડી. એફ. એ. માં ટી. ડી. એફ. એ. નો અમલ પોસિક્સની સૌથી લાંબી મેળ ખાતી સિમેન્ટિક્સ સાથે કર્યો હતો. કુક્લેવિઝે અલ્ગોરિધમનું અનૌપચારિક વર્ણન આપ્યું અને મુખ્ય પ્રશ્નનો જવાબ આપ્યો કે શું ટી. ડી. એફ. એ. પોસિક્સની સૌથી લાંબી-મેળ ખાતી અસ્પષ્ટતા માટે સક્ષમ છે કે કેમ, જેના પર અન્ય સંશોધકો દ્વારા શંકા કરવામાં આવી હતી. 2017 માં ઉલ્યા ટ્રાફિમોવિચે ટીડીએફએને એક-પ્રતીક દેખાવ સાથે વર્ણવ્યું હતું. લુકહેડ પ્રતીકનો ઉપયોગ ટી. ડી. એફ. એ. માં રજિસ્ટર અને રજિસ્ટર કામગીરીની સંખ્યાને ઘટાડે છે, જે તેને લૌરીકારી ટી. ડી. એફ. એ. કરતા ઝડપી અને ઘણીવાર નાની બનાવે છે. ટ્રાફિમોવિચે એલઆર પાર્સર્સ એલઆર (1) અને એલઆર (0) સાથે સામ્યતા દ્વારા લુકહેડ ટીડીએફએ (1) અને ટીડીએફએ (0) સાથે અને વગર ટીડીએફએ વેરિઅન્ટ્સ તરીકે ઓળખાવ્યા. આ અલ્ગોરિધમનો ઓપન-સોર્સ લેક્સર જનરેટર RE2Cમાં અમલ કરવામાં આવ્યો હતો. ટ્રાફિમોવિચે કુક્લેવિઝ અસ્પષ્ટતા અલ્ગોરિધમને ઔપચારિક બનાવ્યું. 2018 માં એન્જેલો બોરસોટીએ ટી. ડી. એફ. એ. ના પ્રાયોગિક જાવા અમલીકરણ પર કામ કર્યું હતું; તે 2021 માં પછીથી પ્રકાશિત થયું હતું. 2019 માં બોરસોટ્ટી અને ટ્રાફિમોવિચે ઓકુઇ અને સુઝુકી દ્વારા ટી. ડી. એફ. એ. માં પોસિક્સ અસ્પષ્ટતા અલ્ગોરિધમનો સ્વીકાર કર્યો. તેઓએ નવા અલ્ગોરિધમની ચોકસાઈનો ઔપચારિક પુરાવો આપ્યો અને બતાવ્યું કે તે વ્યવહારમાં કુક્લેવિઝ અલ્ગોરિધમ કરતાં વધુ ઝડપી છે. 2020માં ટ્રાફિમોવિચે આરઈ2સીમાં ટીડીએફએના અમલીકરણ વિશે એક લેખ પ્રકાશિત કર્યો હતો. 2022માં બોરસોટ્ટી અને ટ્રાફિમોવિચે ટી. ડી. એફ. એ. બાંધકામના વિગતવાર વર્ણન સાથે એક પેપર પ્રકાશિત કર્યું. પેપરમાં તેમના ભૂતકાળના સંશોધનનો સમાવેશ કરવામાં આવ્યો હતો અને મલ્ટી-પાસ ટીડીએફએ રજૂ કરવામાં આવ્યા હતા જે સમયસર નિર્ધારણ માટે વધુ યોગ્ય છે. તેઓએ અન્ય અલ્ગોરિધમ્સ સામે ટી. ડી. એફ. એ. ની સરખામણી પણ કરી અને બેન્ચમાર્ક પ્રદાન કર્યા. ઔપચારિક વ્યાખ્યા ટી. ડી. એફ. એ. સામાન્ય ડી. એફ. એ. જેવું જ મૂળભૂત માળખું ધરાવે છેઃ સંક્રમણો દ્વારા જોડાયેલા રાજ્યોનો મર્યાદિત સમૂહ. તે ઉપરાંત, ટી. ડી. એફ. એ. પાસે રજિસ્ટરોનો એક નિશ્ચિત સમૂહ હોય છે જે ટેગ મૂલ્યો ધરાવે છે, અને રજિસ્ટર મૂલ્યોને સુયોજિત અથવા નકલ કરતા સંક્રમણો પર કામગીરીની નોંધણી કરે છે. મૂલ્યો સ્કેલર ઓફસેટ હોઈ શકે છે, અથવા ટેગ માટે ઓફસેટ સૂચિ હોઈ શકે છે જે વારંવાર મેળ ખાય છે (બાદમાં ટ્રાઇ સ્ટ્રક્ચરનો ઉપયોગ કરીને અસરકારક રીતે રજૂ કરી શકાય છે). નિયમિત અભિવ્યક્તિમાં ટૅગ્સ અને ટી. ડી. એફ. એ. માં રજિસ્ટર વચ્ચે કોઈ એક-થી-એક મેપિંગ નથીઃ એક જ ટેગને ઘણા રજિસ્ટરની જરૂર પડી શકે છે, અને તે જ રજિસ્ટરમાં વિવિધ ટેગ્સના મૂલ્યો હોઈ શકે છે. નીચેની વ્યાખ્યા ટ્રાફિમોવિચ અને બોરસોટ્ટી અનુસાર છે. લૌરિકારીની મૂળ વ્યાખ્યા થોડી અલગ છે. ટેગ કરેલ નિર્ધારક મર્યાદિત ઓટોમેટન એ ટુપલ છે, જ્યાંઃ પ્રતીકોનો મર્યાદિત સમૂહ છે (મૂળાક્ષર) એ ટેગનો મર્યાદિત સમૂહ છે જે પ્રારંભિક સ્થિતિ સાથે રાજ્યોનો મર્યાદિત સમૂહ છે અને અંતિમ રાજ્યોનો સબસેટ એ અંતિમ રજિસ્ટરના સબસેટ સાથે રજિસ્ટરનો મર્યાદિત સમૂહ છે (એક ટેગ દીઠ) એક સંક્રમણ કાર્ય એ અંતિમ કાર્ય છે, જ્યાં નીચેના પ્રકારનાં રજિસ્ટર કામગીરીઓનો સમૂહ છેઃ રજિસ્ટરને શૂન્ય અથવા વર્તમાન સ્થિતિ પર સેટ કરો, જ્યાં નોંધણી કરવા માટે કોપી રજિસ્ટરઃ નોંધણી કરવા અને ઇતિહાસને ઉમેરવા માટે કોપી રજિસ્ટરઃ, જ્યાં ઉદાહરણ આકૃતિ 0 પરની સ્ટ્રિંગ છે તે મૂળાક્ષર સાથે નિયમિત અભિવ્યક્તિ માટે ઉદાહરણ TDFA અને ટેગનો સમૂહ દર્શાવે છે જે ઓછામાં ઓછા એક પ્રતીક સાથે ફોર્મના શબ્દમાળાઓ સાથે મેળ ખાય છે. ટી. ડી. એફ. એ. માં ચાર રાજ્યો છે જેમાંથી ત્રણ અંતિમ છે. રજિસ્ટરોનો સમૂહ અંતિમ રજિસ્ટરના સબસેટ સાથે હોય છે જ્યાં રજિસ્ટર-th ટેગને અનુરૂપ હોય છે. સંક્રમણોમાં કાર્ય દ્વારા વ્યાખ્યાયિત કામગીરી હોય છે, અને અંતિમ સ્થિતિઓમાં કાર્ય દ્વારા વ્યાખ્યાયિત કામગીરી હોય છે (વાઈડ-ટિપ્ડ તીર સાથે ચિહ્નિત). ઉદાહરણ તરીકે, સ્ટ્રિંગને મેચ કરવા માટે, એક સ્ટેટ 0 થી શરૂ થાય છે, પ્રથમ સાથે મેળ ખાય છે અને સ્ટેટ 1 પર જાય છે (રજિસ્ટરને અવ્યાખ્યાયિત અને વર્તમાન પોઝિશન 0 પર સુયોજિત કરે છે), બીજા સાથે મેળ ખાય છે અને લૂપને સ્ટેટ 1 સાથે મેળ ખાય છે (રજિસ્ટર મૂલ્યો હવે છે), મેચ કરે છે અને સ્ટેટ 2 પર જાય છે (રજિસ્ટર મૂલ્યો હવે છે), સ્ટેટ 2 માં અંતિમ કામગીરી કરે છે (રજિસ્ટર મૂલ્યો હવે છે) અને અંતે TDFA માંથી બહાર નીકળે છે. કેનોનિકલ ડી. એફ. એ. જટિલતા રેખીય સમયમાં ઓળખની સમસ્યાનું સમાધાન કરે છે. ટી. ડી. એફ. એ. માટે પણ આ જ લાગુ પડે છે, કારણ કે રજિસ્ટર અને રજિસ્ટર કામગીરીની સંખ્યા નિશ્ચિત હોય છે અને તે માત્ર નિયમિત અભિવ્યક્તિ પર આધાર રાખે છે, પરંતુ ઇનપુટની લંબાઈ પર નહીં. સબમેચ નિષ્કર્ષણ પર ઓવરહેડ નિયમિત અભિવ્યક્તિમાં ટેગની ઘનતા અને દરેક ટેગની બિનનિર્ધારણીય ડિગ્રી (એક જ TDFA સ્થિતિમાં ટેગના તમામ સંભવિત મૂલ્યોને ટ્રેક કરવા માટે જરૂરી રજિસ્ટરની મહત્તમ સંખ્યા) પર આધાર રાખે છે. એક ચરમસીમાએ, જો કોઈ ટેગ ન હોય તો, ટી. ડી. એફ. એ. એ કેનોનિકલ ડી. એફ. એ. સમાન છે. બીજી તરફ, જો દરેક સબએક્સપ્રેશનને ટેગ કરવામાં આવે, તો ટી. ડી. એફ. એ. અસરકારક રીતે સંપૂર્ણ પદચ્છેદન કરે છે અને દરેક સંક્રમણ પર ઘણી કામગીરી કરે છે. વ્યવહારમાં કેટલાક સબમેચ જૂથો સાથે વાસ્તવિક દુનિયાના નિયમિત અભિવ્યક્તિઓ માટે કેનોનિકલ ડી. એફ. એ. સાથે મેળ ખાતી સરખામણીમાં ઓવરહેડ નગણ્ય છે. ટી. ડી. એફ. એ. બાંધકામ ટી. ડી. એફ. એ. બાંધકામ થોડા પગલાંઓમાં કરવામાં આવે છે. પ્રથમ, નિયમિત અભિવ્યક્તિને ટેગ કરેલ બિનનિર્ધારણીય મર્યાદિત ઓટોમેટન (ટી. એન. એફ. એ.) માં રૂપાંતરિત કરવામાં આવે છે. બીજું, ટી. એન. એફ. એ. ને નિર્ધારણ પ્રક્રિયાનો ઉપયોગ કરીને ટી. ડી. એફ. એ. માં રૂપાંતરિત કરવામાં આવે છે; આ પગલામાં અસ્પષ્ટતાનો પણ સમાવેશ થાય છે જે અસ્પષ્ટ ટી. એન. એફ. એ. માર્ગો વચ્ચેના સંઘર્ષોને ઉકેલે છે. તે પછી, ટી. ડી. એફ. એ. વૈકલ્પિક રીતે સંખ્યાબંધ ઓપ્ટિમાઇઝેશનમાંથી પસાર થઈ શકે છે જે રજિસ્ટર અને કામગીરીની સંખ્યાને ઘટાડે છે, જેમાં લઘુતમ સમાવેશ થાય છે જે રાજ્યોની સંખ્યાને ઘટાડે છે. સ્યુડોકોડ સાથે ટી. ડી. એફ. એ. ના નિર્માણના તમામ પગલાઓ માટેના અલ્ગોરિધમ્સ બોર્સોટી અને ટ્રાફિમોવિચ દ્વારા પેપરમાં આપવામાં આવ્યા છે. આ વિભાગ નિયમિત અભિવ્યક્તિના ઉદાહરણ પર ટી. ડી. એફ. એ. ની રચનાને સમજાવે છે, જ્યાં ટેગ છે અને મૂળાક્ષર પ્રતીકો છે. ટેગ કરેલ એન. એફ. એ. ટી. એન. એફ. એ. એ ટેગ કરેલ ε-સંક્રમણો સાથેનું બિનનિર્ધારિત મર્યાદિત ઓટોમેટન છે. તેનું વર્ણન સૌપ્રથમ લૌરિકારી દ્વારા કરવામાં આવ્યું હતું, જો કે સમાન રચનાઓ ઘણી અગાઉ મીલી મશીનો અને બિનનિર્ધારિત મર્યાદિત-સ્થિતિ ટ્રાન્સડ્યુસર્સ તરીકે જાણીતી હતી. ટી. એન. એફ. એ. નું બાંધકામ થોમ્પસનના બાંધકામ જેવું જ છેઃ તે નિયમિત અભિવ્યક્તિની રચનાને પ્રતિબિંબિત કરે છે. મહત્ત્વની વાત એ છે કે, ટી. એન. એફ. એ. નિયમિત અભિવ્યક્તિમાં અસ્પષ્ટતા જાળવી રાખે છેઃ જો સ્ટ્રિંગને બે અલગ અલગ રીતે મેચ કરવી શક્ય હોય, તો આ નિયમિત અભિવ્યક્તિ માટે ટી. એન. એફ. એ. પાસે આ સ્ટ્રિંગ માટે બે અલગ અલગ સ્વીકાર માર્ગ છે. બોર્સોટી અને ટ્રાફિમોવિચ દ્વારા ટી. એન. એફ. એ. ની વ્યાખ્યા લૌરિકારી દ્વારા મૂળ વ્યાખ્યાથી અલગ છે જેમાં ટી. એન. એફ. એ. માં સંક્રમણો પર નકારાત્મક ટેગ હોઈ શકે છેઃ જ્યારે ટેગ કરેલ સંક્રમણ માટે બાયપાસ હોય ત્યારે તેઓ મેચની ગેરહાજરીને સ્પષ્ટ કરવા માટે જરૂરી છે. આકૃતિ 1 નિયમિત અભિવ્યક્તિના ઉદાહરણ માટે ટી. એન. એફ. એ. દર્શાવે છે. તેમાં ત્રણ પ્રકારના સંક્રમણો છેઃ મૂળાક્ષર પ્રતીકો પર સંક્રમણો (ઘેરો વાદળી), ટેગ કરેલ ε-સંક્રમણો (સ્થિતિ 4 થી સ્થિતિ 12 સાથે ટેગ અને સ્થિતિ 10 થી સ્થિતિ 11 સાથે નકારાત્મક ટેગ, તેજસ્વી લીલો), અને ટેગ કરેલ ε-સંક્રમણો (આછા વાદળી). ટી. એન. એફ. એ. પાસે સિંગલ સ્ટાર્ટ સ્ટેટ 0 અને સિંગલ ફાઇનલ સ્ટેટ 11 છે. ટી. એન. એફ. એ. નિર્ધારણને સમજવા માટે, તે પહેલા ટી. એન. એફ. એ. સિમ્યુલેશનને સમજવામાં મદદ કરે છે. કેનોનિકલ ε-NFA સિમ્યુલેશનને યાદ કરો તે શરૂઆતની સ્થિતિના ε-બંધ તરીકે સક્રિય સ્થિતિઓનો સબસેટ બનાવે છે, અને પછી લૂપમાં વારંવાર આગામી ઇનપુટ પ્રતીક પર પગલાં લે છે અને સક્રિય સ્થિતિ સમૂહના ε-બંધની રચના કરે છે. આખરે લૂપ સમાપ્ત થાય છેઃ ક્યાં તો સક્રિય સમૂહ ખાલી થઈ જાય છે (જેનો અર્થ થાય છે નિષ્ફળતા), અથવા તમામ ઇનપુટ પ્રતીકોનો વપરાશ થાય છે (જેનો અર્થ થાય છે સફળતા જો સક્રિય સમૂહમાં અંતિમ સ્થિતિ હોય, અન્યથા નિષ્ફળતા). ટી. એન. એફ. એ. સિમ્યુલેશન સમાન છે, પરંતુ તે વધુમાં ટેગ મૂલ્યોને ટ્રેક કરે છે. દર વખતે જ્યારે સિમ્યુલેશન ટેગ કરેલ સંક્રમણનો સામનો કરે છે, ત્યારે તે વર્તમાન ઓફસેટમાં ટેગ મૂલ્યને અપડેટ કરે છે. સિમ્યુલેશન એક સાથે બહુવિધ બિનનિર્ધારણીય માર્ગોને ટ્રેક કરે છે, તેથી આ માર્ગો પરના ટેગ મૂલ્યો અલગ હોઈ શકે છે અને તેને અલગથી ટ્રેક કરવા જોઈએ. બીજી મુશ્કેલી એ છે કે અસ્પષ્ટતાની જરૂર છેઃ કેનોનિકલ એન. એફ. એ. સિમ્યુલેશનથી વિપરીત, ટી. એન. એફ. એ. સિમ્યુલેશનને અસ્પષ્ટ માર્ગોને અલગ પાડવાની જરૂર છે, કારણ કે તેમાં અલગ ટેગ મૂલ્યો હોઈ શકે છે. આકૃતિ 2 સ્ટ્રિંગ પર ટી. એન. એફ. એ. સિમ્યુલેશનનું ઉદાહરણ બતાવે છેઃ અસ્પષ્ટતા એટલે એક જ ઇનપુટ માટે બહુવિધ વિવિધ પાર્સ વૃક્ષોનું અસ્તિત્વ. તે નિયમિત અભિવ્યક્તિનો ગુણધર્મ છે; અસ્પષ્ટતા ટી. એન. એફ. એ. બાંધકામ દ્વારા સાચવવામાં આવે છે અને ટી. એન. એફ. એ. અનુકરણ અથવા નિર્ધારણ દરમિયાન ઉકેલાય છે. અસ્પષ્ટતાને ઉકેલવાની એક રીત એ છે કે અસ્પષ્ટતા નીતિનો ઉપયોગ કરવો, સૌથી નોંધપાત્ર ઉદાહરણો ડાબેરી-લોભી અને સૌથી લાંબી-મેળ ખાતી (પોસિક્સ) નીતિઓ છે. સૌથી ડાબી બાજુની લોભી નીતિને નિયમિત અભિવ્યક્તિ માળખાની દ્રષ્ટિએ વ્યાખ્યાયિત કરવામાં આવે છે; તે એક સરળ અને કાર્યક્ષમ અમલીકરણને સ્વીકારે છે. બીજી બાજુ, પોસિક્સ નીતિને વિશ્લેષણ પરિણામોના માળખાના સંદર્ભમાં વ્યાખ્યાયિત કરવામાં આવે છે; તેનો અમલ કરવો વધુ મુશ્કેલ છે અને ગણતરીત્મક રીતે સૌથી ડાબી બાજુની લોભી નીતિ કરતાં વધુ જટિલ છે. ટીડીએફએ બંને નીતિઓ સાથે કામ કરી શકે છે, અને અસ્પષ્ટતા પર કોઈ રનટાઇમ ઓવરહેડ નથી, કારણ કે તે નિર્ધારણ દરમિયાન થાય છે અને ટીડીએફએ માળખામાં બને છે. ટી. એન. એફ. એ. સિમ્યુલેશન માટે, બીજી બાજુ, અસ્પષ્ટતા પર ખર્ચવામાં આવેલો સમય રનટાઇમમાં શામેલ છે. નિયમિત અભિવ્યક્તિનું ઉદાહરણ ઇરાદાપૂર્વક અસ્પષ્ટ છે, કારણ કે તે વ્યક્તિને બે અલગ અલગ રીતે વિશ્લેષણ કરવાની મંજૂરી આપે છેઃ ક્યાં તો ડાબા વિકલ્પ તરીકે, અથવા જમણા વિકલ્પ તરીકે. કયા વિકલ્પને પસંદ કરવામાં આવે છે તેના આધારે, ટેગનું મૂલ્ય (પ્રતીકો અને વચ્ચેની સ્થિતિ પર ઓફસેટ), અથવા (અવ્યાખ્યાયિત) હોવું જોઈએ. પોઝિક્સ અને ડાબી બાજુની લોભી અસ્પષ્ટતા નીતિઓ બંને સંમત થાય છે કે આ કિસ્સામાં પ્રથમ વિકલ્પ પ્રાધાન્યક્ષમ છે. નિર્ધારણ ટી. એન. એફ. એ. નિર્ધારણ કેનોનિકલ પાવરસેટ કન્સ્ટ્રક્શન અલ્ગોરિધમ પર આધારિત છે જે એન. એફ. એ. ને ડી. એફ. એ. માં રૂપાંતરિત કરે છે. અલ્ગોરિધમ તમામ સંભવિત શબ્દમાળાઓ પર એન. એફ. એ. નું અનુકરણ કરે છે. અનુકરણના દરેક તબક્કે, એન. એફ. એ. રાજ્યોનો સક્રિય સમૂહ નવી ડી. એફ. એ. સ્થિતિ બનાવે છે. જો નવું રાજ્ય હાલની ડી. એફ. એ. સ્થિતિ જેવું જ હોય, તો તેને કાઢી નાખવામાં આવે છે અને હાલની સાથે બદલવામાં આવે છે, અને સિમ્યુલેશનની વર્તમાન શાખા સમાપ્ત થાય છે. અન્યથા નવા રાજ્યને ડી. એફ. એ. રાજ્યોના વધતા સમૂહમાં ઉમેરવામાં આવે છે અને આ રાજ્યમાંથી અનુકરણ ચાલુ રહે છે. આખરે નિર્ધારણ સમાપ્ત થાય છેઃ જો કે તમામ સંભવિત શબ્દમાળાઓનો સમૂહ અનંત છે, વિવિધ ડી. એફ. એ. સ્થિતિઓનો સમૂહ મર્યાદિત છે, અને અમુક સમયે તમામ નવી સ્થિતિઓ હાલની સ્થિતિઓ જેવી જ બની જાય છે. ટી. ડી. એફ. એ. ના કિસ્સામાં નિષ્કપટ પાવરસેટ બાંધકામને સમસ્યાનો સામનો કરવો પડે છેઃ ટી. ડી. એફ. એ. જણાવે છે કે તેમાં ટેગ માહિતી હોય છે, જે સિમ્યુલેશનના દરેક તબક્કે બદલાય છે (જેમ જેમ ઓફસેટ વધે છે). આ ટી. ડી. એફ. એ. રાજ્યોને નકશા બનાવવાથી અટકાવે છેઃ સમાન ટી. એન. એફ. એ. રાજ્યો ધરાવતી રાજ્યોની જોડી પરંતુ વિવિધ ટેગ ઓફસેટ સમાન નથી અને તેને નકશા કરી શકાતા નથી. પરિણામે, અનુકરણ અનિશ્ચિત સમય સુધી ચાલુ રહે છે, ટી. ડી. એફ. એ. સ્થિતિઓનો સમૂહ વધે છે, અને નિર્ધારણ સમાપ્ત થતું નથી. આ સમસ્યાને ઉકેલવા માટે, લૌરિકારીએ દિશાહિનતાના વિચારને લાગુ કર્યોઃ ટી. ડી. એફ. એ. રાજ્યોમાં તાત્કાલિક ટેગ મૂલ્યોને સંગ્રહિત કરવાને બદલે, તેમણે તેમને પરોક્ષ રીતે રજિસ્ટરમાં સંગ્રહિત કરવાનું સૂચન કર્યું. રજિસ્ટરમાં ટેગ મૂલ્યો અલગ હોઈ શકે છે, પરંતુ જ્યાં સુધી રજિસ્ટર સમાન હોય ત્યાં સુધી તેનાથી કોઈ ફરક પડતો નથી. આ સમાપ્તિ સમસ્યાનું સમાધાન કરે છેઃ જો ટી. ડી. એફ. એ. રાજ્યોમાં જુદા જુદા રજિસ્ટર હોય, તો પણ અનુરૂપ રજિસ્ટર મૂલ્યોની નકલ કરતી કામગીરીઓ ઉમેરીને તેમને સમાન (એકબીજા સાથે મેપ કરેલ) બનાવી શકાય છે. ઇન્ડાયરેક્શન મફત નથીઃ તેને સંક્રમણો પર રનટાઇમ રજિસ્ટર ઓપરેશન્સ ઉમેરવાની જરૂર છે જે રજિસ્ટર મૂલ્યોને અપડેટ કરે છે. રનટાઇમ ઓવરહેડ ઘટાડવા માટે, ટ્રાફિમોવિચે લુકહેડ ઓપ્ટિમાઇઝેશનનો ઉપયોગ કર્યો હતો. ટીડીએફએ રાજ્યમાં આવતા સંક્રમણમાંથી આ રાજ્યમાંથી બહાર જતા સંક્રમણમાં નોંધણી કામગીરીને ખસેડવાનો વિચાર છે. આ રીતે કામગીરી લુકહેડ પ્રતીક પર વિભાજિત થાય છે, જે રજિસ્ટર જીવનકાળ વચ્ચેના ઓવરલેપને ઘટાડે છે અને ઝડપી ટીડીએફએમાં પરિણમે છે. આ ઓપ્ટિમાઇઝેશનનો ઉપયોગ કરવા માટે, બાંધકામ હેઠળના દરેક ટી. ડી. એફ. એ. રાજ્યમાં લુકહેડ ટેગને ટ્રેક કરવું અને ટી. ડી. એફ. એ. રાજ્યોનું મેપિંગ કરતી વખતે તેમને ધ્યાનમાં લેવું જરૂરી છે. આકૃતિ 3 ચાલી રહેલા ઉદાહરણ માટે નિર્ધારણ પ્રક્રિયા દર્શાવે છે. આકૃતિ 4 પરિણામી TDFA દર્શાવે છે. ઓપ્ટિમાઇઝેશન ઓપ્ટિમાઇઝેશનનો ધ્યેય ટી. ડી. એફ. એ. નું કદ અને સંક્રમણો પર રજિસ્ટર અને કામગીરીની સંખ્યા ઘટાડવાનો છે. આ વિભાગ કેટલાક ઓપ્ટિમાઇઝેશનનું વર્ણન કરે છે જેનો ઉપયોગ વ્યવહારુ TDFA અમલીકરણમાં થાય છે. આમાંથી કોઈ પણ ઓપ્ટિમાઇઝેશન ટી. ડી. એફ. એ. કામગીરી માટે ખાસ કરીને જટિલ અથવા મહત્વપૂર્ણ નથી, પરંતુ જ્યારે એકસાથે અને યોગ્ય ક્રમમાં લાગુ કરવામાં આવે ત્યારે તેઓ ટી. ડી. એફ. એ. ને નોંધપાત્ર રીતે ઝડપી અને નાનું બનાવી શકે છે. ફિક્સ્ડ-ટેગ્સ ઓપ્ટિમાઇઝેશન નિયમિત અભિવ્યક્તિ સ્તર (ટી. એન. એફ. એ. બાંધકામ પહેલાં) પર લાગુ કરવામાં આવે છે. વિચાર એ છે કે, જો ટેગની જોડી એકબીજાથી નિશ્ચિત અંતરની અંદર હોય, તો તે બંનેને ટ્રેક કરવાની જરૂર નથીઃ એક ટેગનું મૂલ્ય નિશ્ચિત ઓફસેટ ઉમેરીને અન્ય ટેગના મૂલ્યમાંથી ગણતરી કરી શકાય છે. ઉદાહરણ તરીકે, નિયમિત અભિવ્યક્તિ ટૅગ્સમાં અને એકબીજાથી એક પ્રતીક અંતરની અંદર હોય છે, તેથી તેની ગણતરી આ રીતે કરી શકાય છે. આ ઓપ્ટિમાઇઝેશન ટી. ડી. એફ. એ. બાંધકામના સમય (કારણ કે નિશ્ચિત ટૅગ્સને ટી. એન. એફ. એ. બાંધકામ અને નિર્ધારણમાંથી બાકાત રાખવામાં આવ્યા છે) અને મેળ ખાતા સમય (કારણ કે ત્યાં ઓછી નોંધણી કામગીરી છે) બંનેને ઘટાડી શકે છે. ટી. ડી. એફ. એ. બાંધકામ પછી રજિસ્ટર ઓપ્ટિમાઇઝેશન લાગુ કરવામાં આવે છે. ટી. ડી. એફ. એ. રજિસ્ટર પર નિયંત્રણ પ્રવાહ આલેખ (સી. એફ. જી.) ને પ્રેરિત કરે છેઃ સંક્રમણો પરની કામગીરી મૂળભૂત બ્લોક બનાવે છે, અને બે બ્લોક વચ્ચે એક ચાપ હોય છે જો તેમાંથી એક અન્ય રજિસ્ટર કામગીરીઓમાંથી પસાર થયા વિના, ટી. ડી. એફ. એ. સંક્રમણો દ્વારા અન્ય બ્લોકથી પહોંચી શકાય તેવું હોય. સી. એફ. જી. રજિસ્ટર પરના પ્રોગ્રામને ચલ તરીકે રજૂ કરે છે, તેથી સામાન્ય કમ્પાઇલર ઓપ્ટિમાઇઝેશન તેના પર લાગુ કરી શકાય છે (જેમ કે જીવંત વિશ્લેષણ, ડેડ કોડ નાબૂદી અને રજિસ્ટર ફાળવણી). ટી. ડી. એફ. એ. મિનિમાઈઝેશન એ ડી. એફ. એ. મિનિમાઈઝેશન જેવું જ છે, સિવાય કે એક વધારાનું પ્રતિબંધઃ ટી. ડી. એફ. એ. સંક્રમણો પર નોંધણી ક્રિયાઓ ધ્યાનમાં લેવી આવશ્યક છે. તેથી, TDFA જણાવે છે કે જે સમાન છે, પરંતુ સમાન પ્રતીક પર આવતા સંક્રમણો પર અલગ-અલગ રજિસ્ટર ક્રિયાઓ છે, તેને મર્જ કરી શકાતી નથી. ડી. એફ. એ. લઘુતમ કરવા માટેના તમામ સામાન્ય અલ્ગોરિધમ્સને ટી. ડી. એફ. એ. લઘુતમ કરવા માટે અનુકૂળ કરી શકાય છે, ઉદાહરણ તરીકે મૂરેના અલ્ગોરિધમનો ઉપયોગ આરઈ2સી લેક્સર જનરેટરમાં થાય છે. આકૃતિ 5 નિયમિત અભિવ્યક્તિ માટે શ્રેષ્ઠ TDFA દર્શાવે છે. નોંધ લો કે તે હકીકતમાં અર્થપૂર્ણ રીતે સમકક્ષ નિયમિત અભિવ્યક્તિ માટે TDFA જેવું જ છે, જ્યાં અસ્પષ્ટતા દૂર કરવામાં આવી છે. અસ્પષ્ટતા નિર્ધારણ દરમિયાન ઉકેલાય છે, અને આકૃતિ 4 પર બિન-ઑપ્ટિમાઇઝ કરેલ ટી. ડી. એફ. એ. સ્પષ્ટ છે, પરંતુ તેમાં કેટલીક બિલ્ટ-ઇન રીડન્ડન્સી છે જેને ઓપ્ટિમાઇઝેશન દ્વારા દૂર કરી શકાય છે. જ્યારે ટી. ડી. એફ. એ. બાંધકામ પર ખર્ચવામાં આવેલો સમય રનટાઇમમાં સામેલ ન હોય (દા. ત. ટી. એફ. એ.) ત્યારે રજિસ્ટર સાથે મલ્ટી-પાસ ટી. ડી. એફ. એ. ટી. ડી. એફ. એ. સમય પહેલા નક્કી કરવા માટે સારી રીતે અનુકૂળ હોય છે. લેક્સર જનરેટરમાં). પરંતુ સમયસર નિર્ણય લેવા માટે (દા. ત. નિયમિત અભિવ્યક્તિ પુસ્તકાલયોમાં) ટી. ડી. એફ. એ. બાંધકામનો સમય ઘટાડવો ઇચ્છનીય છે. બીજી ચિંતા નિયમિત અભિવ્યક્તિમાં ટેગની ઘનતા છેઃ જો ટેગની સંખ્યા પ્રમાણમાં ઓછી હોય તો રજિસ્ટર સાથે TDFA કાર્યક્ષમ છે. પરંતુ ભારે ટેગ કરેલા નિયમિત સમીકરણો માટે ટી. ડી. એફ. એ. રજિસ્ટર સાથે સબઓપ્ટિમલ છેઃ સંક્રમણો કામગીરી સાથે અવ્યવસ્થિત થઈ જાય છે, જે ટી. ડી. એફ. એ. ના અમલને ધીમું બનાવે છે. જીવંતતા અને હસ્તક્ષેપ માહિતીના કદને કારણે રજિસ્ટર ઓપ્ટિમાઇઝેશન પણ સમસ્યારૂપ બની જાય છે. મલ્ટી-પાસ ટીડીએફએ બંને મુદ્દાઓને સંબોધિત કરે છેઃ તેઓ ટીડીએફએ બાંધકામના સમયને ઘટાડે છે, અને તેઓ ગાઢ સબમેચ નિષ્કર્ષણ માટે વધુ યોગ્ય છે. કેનોનિકલ ટી. ડી. એફ. એ. સાથેનો મુખ્ય તફાવત એ છે કે મલ્ટી-પાસ ટી. ડી. એફ. એ. પાસે કોઈ નોંધણી કામગીરી નથી. તેના બદલે તેમની પાસે બહુવિધ પાસ હોય છેઃ એક ફોરવર્ડ પાસ જે ઇનપુટ સ્ટ્રિંગ સાથે મેળ ખાય છે અને ટી. ડી. એફ. એ. સ્ટેટ્સના ક્રમને રેકોર્ડ કરે છે, અને એક અથવા વધુ બેકવર્ડ પાસ જે રેકોર્ડ કરેલા સ્ટેટ્સમાંથી પુનરાવર્તન કરે છે અને સબમેચની માહિતી એકત્રિત કરે છે. એક બેકવર્ડ પાસ પૂરતો છે, પરંતુ વધારાના પાસનો ઉપયોગ કરી શકાય છે. સબમેચના પરિણામો માટે જરૂરી મેમરીનો અંદાજ કાઢવો. ટી. ડી. એફ. એ. સ્થિતિઓના ક્રમમાંથી મેળ ખાતા ટી. એન. એફ. એ. માર્ગને શોધવા માટે, મલ્ટી-પાસ ટી. ડી. એફ. એ. સંક્રમણો પર અને અંતિમ સ્થિતિઓમાં બેકલિંક્સનો ઉપયોગ કરે છે. બૅકલિંક એ જોડી છે, જ્યાં પ્રથમ ઘટક અગાઉના સંક્રમણો પર બૅકલિંક એરેમાં અનુક્રમણિકા છે, અને બીજો ઘટક ટી. ડી. એફ. એ. રાજ્યો વચ્ચેના ટી. એન. એફ. એ. માર્ગના ટુકડા માટે ટેગનો ક્રમ છે. આકૃતિ 6 સ્ટ્રિંગ પર નિયમિત અભિવ્યક્તિ મેળ માટે મલ્ટી-પાસ TDFA નું ઉદાહરણ દર્શાવે છે (તેની સરખામણી આકૃતિ 0 સાથે કરો જે સમાન નિયમિત અભિવ્યક્તિ માટે રજિસ્ટર સાથે TDFA દર્શાવે છે): ફોરવર્ડ પાસ 0,1,1,2 સ્થિતિઓનો ક્રમ એકત્રિત કરે છે. પછાત પાસ સ્થિતિ 2 થી સ્થિતિ 0 સુધીની બેકલિંક્સને અનુસરે છે અને ટેગ સિક્વન્સ અને ઇનપુટ પ્રતીકોને સાંકળે છે. તે બૅકલિંકથી શરૂ થાય છે. ટેગ કરેલ શબ્દમાળા છે. અનુક્રમણિકા 0 સ્થિતિ 1 થી સ્થિતિ 2 (આ સંક્રમણ પર એકમાત્ર) માં અગાઉના સંક્રમણ પરની બૅકલિંક પસંદ કરે છે. ટેગ કરેલ શબ્દમાળા બને છે. અનુક્રમણિકા 0 સ્થિતિ 1 થી સ્થિતિ 1 માં અગાઉના લૂપિંગ સંક્રમણ પરની બૅકલિંક પસંદ કરે છે. ટેગ કરેલ શબ્દમાળા બને છે. અનુક્રમણિકા 0 સ્થિતિ 0 થી સ્થિતિ 1 માં અગાઉના સંક્રમણ પરની બૅકલિંક પસંદ કરે છે. પરિણામી ટેગ કરેલ શબ્દમાળા છે. તેમાં દરેક ટેગ માટે છેલ્લા ઓફસેટ અથવા ઓફસેટ યાદીઓનું પુનઃનિર્માણ કરવા માટે તમામ જરૂરી માહિતી છે. મોહમ્મદ ઇમરાન ચૌધરી દ્વારા વર્ણવેલ સંબંધિત ઓટોમેટા સ્ટેડાફા ટી. ડી. એફ. એ. સાથે ખૂબ સમાન છે, સિવાય કે તેઓ રાજ્યોમાં નોંધણી કામગીરી ધરાવે છે, સંક્રમણો પર નહીં. ગ્રેથવોલ દ્વારા વર્ણવેલ ડી. એસ. એસ. ટી. (નિર્ધારિત સ્ટ્રીમિંગ સ્ટ્રિંગ ટ્રાન્સડ્યુસર્સ) ટી. ડી. એફ. એ. ના વધુ દૂરના સંબંધીઓ છે, જે સબમેચ નિષ્કર્ષણ કરતાં સંપૂર્ણ પદચ્છેદન માટે વધુ યોગ્ય છે. ડી. એસ. એસ. ટી. રાજ્યોમાં ε-બંધ દ્વારા બાંધવામાં આવેલા પાથ ટ્રીઝ હોય છે, જ્યારે ટી. ડી. એફ. એ. રાજ્યોમાં વિઘટિત સ્વરૂપમાં સમાન માહિતી હોય છે (રજિસ્ટર વર્ઝન અને લુકહેડ ટેગ્સ). સંદર્ભો મર્યાદિત ઓટોમેટા