Tagged Deterministic Finite Automaton
தானியங்கி கோட்பாட்டில், குறிக்கப்பட்ட வரையறுக்கப்பட்ட வரையறுக்கப்பட்ட தானியங்கி இயந்திரம் (டி. டி. எஃப். ஏ) என்பது வரையறுக்கப்பட்ட வரையறுக்கப்பட்ட தானியங்கி இயந்திரத்தின் (டி. எஃப். ஏ) நீட்டிப்பாகும். வழக்கமான மொழிகளுக்கான அங்கீகாரப் பிரச்சினையைத் தீர்ப்பதோடு மட்டுமல்லாமல், டி. டி. எஃப். ஏ துணைப் பொருத்தம் பிரித்தெடுத்தல் மற்றும் பகுப்பாய்வு செய்யும் திறனையும் கொண்டுள்ளது. ஒரு சரம் வழக்கமான வெளிப்பாட்டால் வரையறுக்கப்பட்ட மொழியைச் சேர்ந்ததா என்பதை நியதி டி. எஃப். ஏ கண்டுபிடிக்க முடியும், டி. டி. எஃப். ஏ குறிப்பிட்ட துணை வெளிப்பாடுகளுடன் பொருந்தக்கூடிய அடி மூலக்கூறுகளையும் பிரித்தெடுக்க முடியும். மேலும் பொதுவாக, டி. டி. எஃப். ஏ ஒரு வழக்கமான வெளிப்பாட்டில் குறிக்கப்பட்ட நிலைகளுடன் பொருந்தக்கூடிய உள்ளீட்டு சரத்தில் உள்ள நிலைகளை அடையாளம் காண முடியும் (குறிச்சொற்கள் அடைப்புக்குறிகளைப் பிடிப்பது போன்ற மெட்டா-சின்னங்கள், ஆனால் இணைத்தல் தேவை இல்லாமல்). டி. டி. எஃப். ஏ முதன்முதலில் 2000 ஆம் ஆண்டில் வில்லே லாரிக்காரியால் விவரிக்கப்பட்டது. அதற்கு முன்பு ஒரு வரையறுக்கப்பட்ட வரையறுக்கப்பட்ட-நிலை தானியங்கி இயந்திரத்தில் ஒரு பாஸில் சப்மேட்ச் பிரித்தெடுத்தல் செய்ய முடியுமா என்பது தெரியவில்லை, எனவே இந்த காகிதம் ஒரு முக்கியமான முன்னேற்றமாக இருந்தது. லாரிக்காரி டிடிஎஃப்ஏ கட்டுமானத்தை விவரித்தார் மற்றும் தீர்மானிக்கும் செயல்முறை முடிவடைகிறது என்பதற்கான ஆதாரத்தை வழங்கினார், இருப்பினும் வழிமுறை தெளிவற்ற தன்மையை சரியாக கையாளவில்லை. 2007 ஆம் ஆண்டில் கிறிஸ் குக்லெவிக்ஸ் டிடிஎஃப்ஏவை ஹாஸ்கெல் நூலகத்தில் ரெஜெக்ஸ்-டிடிஎஃப்ஏவை போஸிக்ஸ் மிக நீண்ட போட்டி சொற்பொருள்களுடன் செயல்படுத்தினார். குக்லெவிக்ஸ் இந்த வழிமுறையைப் பற்றி முறைசாரா விளக்கத்தைக் கொடுத்தார், மேலும் டி. டி. எஃப். ஏ போஸிக்ஸ் மிக நீண்ட-போட்டி விவாதம் திறன் கொண்டதா என்ற முக்கிய கேள்விக்கு பதிலளித்தார், இது மற்ற ஆராய்ச்சியாளர்களால் சந்தேகிக்கப்பட்டது. 2017 ஆம் ஆண்டில் உல்யா டிராஃபிமோவிச் டி. டி. எஃப். ஏவை ஒரு குறியீட்டு தோற்றத்துடன் விவரித்தார். லுக்ஹெட் சின்னத்தைப் பயன்படுத்துவது டிடிஎஃப்ஏவில் பதிவேடுகள் மற்றும் பதிவு செயல்பாடுகளின் எண்ணிக்கையைக் குறைக்கிறது, இது லாரிகாரி டிடிஎஃப்ஏவை விட வேகமாகவும் பெரும்பாலும் சிறியதாகவும் இருக்கும். டிராபிமோவிச் டிடிஎஃப்ஏ வகைகளை டிடிஎஃப்ஏ (1) மற்றும் டிடிஎஃப்ஏ (0) உடன் மற்றும் இல்லாமல் எல்ஆர் பாகங்கள் எல்ஆர் (1) மற்றும் எல்ஆர் (0) உடன் ஒப்புமை மூலம் அழைத்தார். இந்த வழிமுறை திறந்த மூல லெக்சர் ஜெனரேட்டர் RE2C இல் செயல்படுத்தப்பட்டது. டிராஃபிமோவிச் குக்லெவிக்ஸ் விவாதம் பகுப்பாய்வு வழிமுறையை முறைப்படுத்தினார். 2018 ஆம் ஆண்டில் ஏஞ்சலோ போர்சோட்டி டி. டி. எஃப். ஏ இன் சோதனை ஜாவா செயல்படுத்தலில் பணியாற்றினார்; இது பின்னர் 2021 இல் வெளியிடப்பட்டது. 2019 ஆம் ஆண்டில் போர்சோட்டி மற்றும் டிராஃபிமோவிச் ஆகியோர் ஒகுய் மற்றும் சுசுகி ஆகியோரால் டிடிஎஃப்ஏ-க்கு போஸிக்ஸ் விவாதம் வழிமுறையைத் தழுவினர். அவர்கள் புதிய வழிமுறையின் சரியான தன்மைக்கான முறையான ஆதாரத்தை வழங்கினர், மேலும் இது நடைமுறையில் குக்லெவிக்ஸ் வழிமுறையை விட வேகமானது என்பதைக் காட்டினர். 2020 ஆம் ஆண்டில் டிராஃபிமோவிச் RE2C இல் TDFA செயல்படுத்தல் பற்றி ஒரு கட்டுரையை வெளியிட்டார். 2022 ஆம் ஆண்டில் போர்சோட்டி மற்றும் டிராஃபிமோவிச் ஆகியோர் டி. டி. எஃப். ஏ கட்டுமானத்தைப் பற்றிய விரிவான விளக்கத்துடன் ஒரு கட்டுரையை வெளியிட்டனர். இந்த ஆய்வுக் கட்டுரை அவர்களின் கடந்த கால ஆராய்ச்சியை இணைத்து, சரியான நேரத்தில் தீர்மானிப்பதற்கு மிகவும் பொருத்தமான மல்டி-பாஸ் டிடிஎஃப்ஏவை வழங்கியது. அவர்கள் டிடிஎஃப்ஏவை மற்ற வழிமுறைகளுடன் ஒப்பிட்டுப் பார்த்தனர் மற்றும் அளவுகோல்களை வழங்கினர். முறையான வரையறை டிடிஎஃப்ஏ சாதாரண டிஎஃப்ஏவின் அதே அடிப்படை கட்டமைப்பைக் கொண்டுள்ளதுஃ மாற்றங்களால் இணைக்கப்பட்ட நிலைகளின் வரையறுக்கப்பட்ட தொகுப்பு. இது தவிர, டி. டி. எஃப். ஏ ஒரு நிலையான பதிவேடுகளைக் கொண்டுள்ளது, அவை குறிச்சொல் மதிப்புகளைக் கொண்டுள்ளன, மேலும் பதிவு மதிப்புகளை அமைக்கும் அல்லது நகலெடுக்கும் மாற்றங்களில் செயல்பாடுகளைப் பதிவு செய்கின்றன. மதிப்புகள் அளவிடக்கூடிய ஆஃப்செட்டுகளாக இருக்கலாம் அல்லது மீண்டும் மீண்டும் பொருந்தக்கூடிய குறிச்சொற்களுக்கான ஆஃப்செட் பட்டியல்களாக இருக்கலாம் (பிந்தையது ஒரு ட்ரை கட்டமைப்பைப் பயன்படுத்தி திறம்பட குறிப்பிடப்படலாம்). ஒரு வழக்கமான வெளிப்பாட்டில் உள்ள குறிச்சொற்கள் மற்றும் டி. டி. எஃப். ஏ-வில் உள்ள பதிவேடுகளுக்கு இடையில் ஒருவருக்கொருவர் வரைபடம் இல்லைஃ ஒரு குறிச்சொல்லுக்கு பல பதிவேடுகள் தேவைப்படலாம், அதே பதிவேட்டில் வெவ்வேறு குறிச்சொற்களின் மதிப்புகள் இருக்கலாம். பின்வரும் வரையறை டிராஃபிமோவிச் மற்றும் போர்சொட்டியின் கூற்றுப்படி உள்ளது. லாரிக்காரியின் அசல் வரையறை சற்று வித்தியாசமானது. குறிக்கப்பட்ட வரையறுக்கப்பட்ட வரையறுக்கப்பட்ட தானியங்கி இயந்திரம் என்பது ஒரு டப்பிள் ஆகும், இதில்ஃ குறியீடுகளின் ஒரு வரையறுக்கப்பட்ட தொகுப்பு (எழுத்துக்கள்) என்பது குறிச்சொற்களின் ஒரு வரையறுக்கப்பட்ட தொகுப்பாகும், இது ஆரம்ப நிலை கொண்ட நிலைகளின் ஒரு வரையறுக்கப்பட்ட தொகுப்பாகும், மேலும் இறுதி நிலைகளின் துணைக்குழு என்பது இறுதி பதிவேடுகளின் துணைக்குழுவுடன் (குறிச்சொல்லுக்கு ஒன்று) ஒரு வரையறுக்கப்பட்ட பதிவேடுகளின் தொகுப்பாகும், இது ஒரு இறுதி செயல்பாடாகும், அங்கு பின்வரும் வகைகளின் பதிவு செயல்பாடுகளின் தொகுப்பாகும்ஃ பதிவேட்டை பூஜ்யமாக அல்லது தற்போதைய நிலைக்கு அமைக்கவும்ஃ, பதிவு செய்ய நகல் பதிவேடு இருக்கும் இடத்தில்ஃ பதிவு செய்ய பதிவேட்டை நகலெடுத்து வரலாற்றைச் சேர்க்கவும்ஃ, எடுத்துக்காட்டுக்கு மேல் ஒரு சரம் எங்கே படம் 0 என்பது எழுத்துக்களுடன் வழக்கமான வெளிப்பாட்டிற்கான எடுத்துக்காட்டு டி. டி. எஃப். ஏ மற்றும் குறைந்தபட்சம் ஒரு சின்னத்துடன் படிவத்தின் சரங்களுடன் பொருந்தக்கூடிய குறிச்சொற்களின் தொகுப்பைக் காட்டுகிறது. டிடிஎஃப்ஏ நான்கு மாநிலங்களைக் கொண்டுள்ளது, அவற்றில் மூன்று இறுதிப் போட்டிகளாகும். பதிவேடுகளின் தொகுப்பு இறுதி பதிவேடுகளின் துணைக்குழுவுடன் உள்ளது, அங்கு பதிவு-th குறிச்சொல்லுடன் ஒத்திருக்கிறது. மாற்றங்கள் செயல்பாட்டால் வரையறுக்கப்பட்ட செயல்பாடுகளைக் கொண்டுள்ளன, மேலும் இறுதி நிலைகள் செயல்பாட்டால் வரையறுக்கப்பட்ட செயல்பாடுகளைக் கொண்டுள்ளன (பரந்த முனை அம்புடன் குறிக்கப்படுகின்றன). எடுத்துக்காட்டாக, சரத்துடன் பொருந்த, ஒன்று நிலை 0 இல் தொடங்கி, முதல் நிலைக்கு பொருந்துகிறது மற்றும் நிலை 1 க்கு நகர்கிறது (பதிவேடுகளை வரையறுக்கப்படாத மற்றும் தற்போதைய நிலை 0 க்கு அமைத்தல்), இரண்டாவது மற்றும் சுழல்களை நிலை 1 உடன் பொருந்துகிறது (பதிவு மதிப்புகள் இப்போது உள்ளன), பொருத்தங்கள் மற்றும் நிலை 2 க்கு நகர்கிறது (பதிவு மதிப்புகள் இப்போது உள்ளன), நிலை 2 இல் இறுதி செயல்பாடுகளை செயல்படுத்துகிறது (பதிவு மதிப்புகள் இப்போது உள்ளன) இறுதியாக TDFA இலிருந்து வெளியேறுகிறது. சிக்கலானது கனோனிக்கல் டி. எஃப். ஏ அங்கீகார சிக்கலை நேரியல் நேரத்தில் தீர்க்கிறது. டிடிஎஃப்ஏ-க்கும் இது பொருந்தும், ஏனெனில் பதிவேடுகள் மற்றும் பதிவு செயல்பாடுகளின் எண்ணிக்கை நிலையானது மற்றும் வழக்கமான வெளிப்பாட்டை மட்டுமே சார்ந்துள்ளது, ஆனால் உள்ளீட்டின் நீளத்தைப் பொறுத்தது அல்ல. சப்மேட்ச் பிரித்தெடுப்பின் மேல்நிலை ஒரு வழக்கமான வெளிப்பாட்டில் குறிச்சொல் அடர்த்தி மற்றும் ஒவ்வொரு குறிச்சொல்லின் உறுதியற்ற அளவு (ஒரு டிடிஎஃப்ஏ மாநிலத்தில் குறிச்சொல்லின் அனைத்து சாத்தியமான மதிப்புகளையும் கண்காணிக்க தேவையான அதிகபட்ச பதிவேடுகளின் எண்ணிக்கை) ஆகியவற்றைப் பொறுத்தது. ஒரு தீவிரத்தில், குறிச்சொற்கள் இல்லையென்றால், ஒரு டிடிஎஃப்ஏ ஒரு நியமன டிஎஃப்ஏவைப் போன்றது. மறுபுறம், ஒவ்வொரு துணை வெளிப்பாடும் குறிக்கப்பட்டால், ஒரு டி. டி. எஃப். ஏ திறம்பட முழு பகுப்பாய்வு செய்கிறது மற்றும் ஒவ்வொரு மாற்றத்திலும் பல செயல்பாடுகளைக் கொண்டுள்ளது. நடைமுறையில் ஒரு சில சப்மேட்ச் குழுக்களுடன் நிஜ உலக வழக்கமான வெளிப்பாடுகளுக்கு மேல்நிலை டி. எஃப். ஏ உடன் பொருந்துவதை ஒப்பிடும்போது மிகக் குறைவு. டிடிஎஃப்ஏ கட்டுமானம் ஒரு சில படிகளில் செய்யப்படுகிறது. முதலாவதாக, ஒரு வழக்கமான வெளிப்பாடு குறிக்கப்பட்ட வரையறுக்கப்படாத வரையறுக்கப்பட்ட தானியங்கியாக (டிஎன்எஃப்ஏ) மாற்றப்படுகிறது. இரண்டாவதாக, ஒரு டிஎன்எஃப்ஏ ஒரு தீர்மானிக்கும் நடைமுறையைப் பயன்படுத்தி டிடிஎஃப்ஏவாக மாற்றப்படுகிறது; இந்த படிநிலையில் தெளிவற்ற டிஎன்எஃப்ஏ பாதைகளுக்கு இடையிலான மோதல்களைத் தீர்க்கும் தெளிவற்ற தன்மையும் அடங்கும். அதன்பிறகு, ஒரு டி. டி. எஃப். ஏ விருப்பப்படி பதிவேடுகள் மற்றும் செயல்பாடுகளின் எண்ணிக்கையைக் குறைக்கும் பல தேர்வுகளைச் செய்யலாம், இதில் மாநிலங்களின் எண்ணிக்கையைக் குறைக்கும் மினிமைசேஷன் அடங்கும். போலி குறியீட்டைக் கொண்டு டி. டி. எஃப். ஏ கட்டுமானத்தின் அனைத்து படிகளுக்கும் வழிமுறைகள் போர்ஸோட்டி மற்றும் டிராஃபிமோவிச் ஆகியோரால் காகிதத்தில் கொடுக்கப்பட்டுள்ளன. இந்த பிரிவு வழக்கமான வெளிப்பாட்டின் எடுத்துக்காட்டில் டி. டி. எஃப். ஏ கட்டுமானத்தை விளக்குகிறது, அங்கு ஒரு குறிச்சொல் மற்றும் எழுத்துக்கள் சின்னங்கள். குறிக்கப்பட்ட என்எப்ஏ டிஎன்எஃப்ஏ என்பது குறிக்கப்பட்ட ε-மாற்றங்களுடன் ஒரு வரையறுக்கப்படாத வரையறுக்கப்பட்ட தானியங்கி இயந்திரமாகும். இது முதன்முதலில் லாரிக்காரியால் விவரிக்கப்பட்டது, இருப்பினும் இதேபோன்ற கட்டுமானங்கள் மிக முன்னதாகவே உணவு இயந்திரங்கள் மற்றும் வரையறுக்கப்படாத வரையறுக்கப்பட்ட-நிலை கடத்திகள் என்று அறியப்பட்டன. டிஎன்எஃப்ஏ கட்டுமானம் தாம்சனின் கட்டுமானத்துடன் மிகவும் ஒத்திருக்கிறதுஃ இது ஒரு வழக்கமான வெளிப்பாட்டின் கட்டமைப்பை பிரதிபலிக்கிறது. முக்கியமாக, டிஎன்எஃப்ஏ ஒரு வழக்கமான வெளிப்பாட்டில் தெளிவின்மையைப் பாதுகாக்கிறதுஃ ஒரு சரத்தை இரண்டு வெவ்வேறு வழிகளில் பொருத்த முடிந்தால், இந்த வழக்கமான வெளிப்பாட்டிற்கான டிஎன்எஃப்ஏ இந்த சரத்திற்கு இரண்டு வெவ்வேறு ஏற்றுக்கொள்ளும் பாதைகளைக் கொண்டுள்ளது. போர்சோட்டி மற்றும் டிராஃபிமோவிச்சின் டிஎன்எஃப்ஏ வரையறை லாரிகாரியின் அசல் வரையறையிலிருந்து வேறுபடுகிறது, இதில் டிஎன்எஃப்ஏ மாற்றங்கள் மீது எதிர்மறை குறிச்சொற்களைக் கொண்டிருக்கலாம்ஃ குறிச்சொல் மாற்றத்திற்கு ஒரு புறவழி இருக்கும்போது அவை போட்டி இல்லாததை வெளிப்படையாக செய்ய வேண்டும். படம் 1 வழக்கமான வெளிப்பாட்டிற்கு டிஎன்எஃப்ஏவைக் காட்டுகிறது. இது மூன்று வகையான மாற்றங்களைக் கொண்டுள்ளதுஃ எழுத்துக்கள் குறியீடுகளில் மாற்றங்கள் (அடர் நீலம்), குறிக்கப்பட்ட ε-மாற்றங்கள் (நிலை 4 இலிருந்து நிலை 12 க்கு குறிச்சொல்லுடன் மற்றும் நிலை 10 இலிருந்து நிலை 11 க்கு எதிர்மறை குறிச்சொல்லுடன், பிரகாசமான பச்சை), மற்றும் குறிக்கப்படாத ε-மாற்றங்கள் (வெளிர் நீலம்). டிஎன்எஃப்ஏ ஒரு தொடக்க நிலை 0 மற்றும் ஒரு இறுதி நிலை 11 ஐக் கொண்டுள்ளது. டிஎன்எஃப்ஏ தீர்மானிப்பைப் புரிந்துகொள்வதற்காக, முதலில் டிஎன்எஃப்ஏ உருவகப்படுத்துதலைப் புரிந்துகொள்ள இது உதவுகிறது. நியமன ε-NFA உருவகப்படுத்துதலை நினைவுகூருங்கள்ஃ இது தொடக்க நிலையின் ε-மூடுதலாக செயலில் உள்ள நிலைகளின் துணைக்குழுவை உருவாக்குகிறது, பின்னர் ஒரு வளையத்தில் அடுத்த உள்ளீட்டு சின்னத்தில் மீண்டும் மீண்டும் படிகள் எடுத்து செயலில் உள்ள நிலை தொகுப்பின் ε-மூடுதலை உருவாக்குகிறது. இறுதியில் வளையம் முடிவடைகிறதுஃ ஒன்று செயலில் உள்ள தொகுப்பு காலியாகிறது (அதாவது ஒரு தோல்வி), அல்லது அனைத்து உள்ளீட்டு சின்னங்களும் நுகரப்படுகின்றன (அதாவது செயலில் உள்ள தொகுப்பில் ஒரு இறுதி நிலை இருந்தால் வெற்றி, இல்லையெனில் ஒரு தோல்வி). டிஎன்எஃப்ஏ உருவகப்படுத்துதல் ஒத்திருக்கிறது, ஆனால் இது கூடுதலாக குறிச்சொல் மதிப்புகளை கண்காணிக்கிறது. ஒவ்வொரு முறையும் உருவகப்படுத்துதல் ஒரு குறிக்கப்பட்ட மாற்றத்தை எதிர்கொள்ளும்போது, அது குறிச்சொல் மதிப்பை தற்போதைய ஆஃப்செட்டுக்கு புதுப்பிக்கிறது. உருவகப்படுத்துதல் ஒரே நேரத்தில் பல நிர்ணயிக்கப்படாத பாதைகளைக் கண்காணிப்பதால், இந்த பாதைகளில் குறிச்சொல் மதிப்புகள் வேறுபடலாம் மற்றும் தனித்தனியாக கண்காணிக்கப்பட வேண்டும். மற்றொரு சிரமம் விவாதம் தேவைப்படுகிறதுஃ நியதி NFA உருவகப்படுத்துதல் போலல்லாமல், டிஎன்எஃப்ஏ உருவகப்படுத்துதல் தெளிவற்ற பாதைகளை வேறுபடுத்திக் காட்ட வேண்டும், ஏனெனில் அவை வெவ்வேறு குறிச்சொல் மதிப்புகளைக் கொண்டிருக்கலாம். படம் 2 ஒரு சரத்தில் டிஎன்எஃப்ஏ உருவகப்படுத்துதலின் ஒரு உதாரணத்தைக் காட்டுகிறதுஃ தெளிவின்மை என்பது ஒரே உள்ளீட்டிற்கு பல வேறுபட்ட பார்ஸ் மரங்கள் இருப்பதைக் குறிக்கிறது. இது ஒரு வழக்கமான வெளிப்பாட்டின் பண்பு; டிஎன்எஃப்ஏ கட்டுமானத்தால் தெளிவின்மை பாதுகாக்கப்படுகிறது மற்றும் டிஎன்எஃப்ஏ உருவகப்படுத்துதல் அல்லது தீர்மானிப்பின் போது தீர்க்கப்படுகிறது. தெளிவின்மையைத் தீர்ப்பதற்கான ஒரு வழி ஒரு தெளிவின்மைக் கொள்கையைப் பயன்படுத்துவதாகும், இதற்கு மிகவும் குறிப்பிடத்தக்க எடுத்துக்காட்டுகள் இடது-பேராசை மற்றும் மிக நீண்ட-போட்டி (போஸிக்ஸ்) கொள்கைகள் ஆகும். இடதுசாரி-பேராசைக் கொள்கை வழக்கமான வெளிப்பாட்டு கட்டமைப்பின் அடிப்படையில் வரையறுக்கப்படுகிறது; இது ஒரு எளிய மற்றும் திறமையான செயல்பாட்டை ஒப்புக்கொள்கிறது. மறுபுறம், போஸிக்ஸ் கொள்கை, பகுப்பாய்வு முடிவுகளின் கட்டமைப்பின் அடிப்படையில் வரையறுக்கப்படுகிறது; அதை செயல்படுத்துவது மிகவும் கடினம் மற்றும் கணக்கீட்டு ரீதியாக இடது-பேராசை கொள்கையை விட மிகவும் சிக்கலானது. டி. டி. எஃப். ஏ இரண்டு கொள்கைகளுடனும் வேலை செய்ய முடியும், மேலும் இது தீர்மானிக்கும் போது நிகழ்கிறது மற்றும் டி. டி. எஃப். ஏ கட்டமைப்பில் கட்டமைக்கப்படுவதால், குழப்பத்தில் இயக்க நேர மேல்நிலை இல்லை. டிஎன்எஃப்ஏ உருவகப்படுத்துதலைப் பொறுத்தவரை, மறுபுறம், தெளிவற்ற தன்மைக்கு செலவழித்த நேரம் இயக்க நேரத்தில் சேர்க்கப்பட்டுள்ளது. வழக்கமான வெளிப்பாட்டின் எடுத்துக்காட்டு வேண்டுமென்றே தெளிவற்றது, ஏனெனில் இது ஒருவரை இரண்டு வெவ்வேறு வழிகளில் பகுப்பாய்வு செய்ய அனுமதிக்கிறதுஃ இடது மாற்று அல்லது வலது வழி. எந்த மாற்றீடு விரும்பப்படுகிறது என்பதைப் பொறுத்து, குறிச்சொல்லின் மதிப்பு (குறியீடுகள் மற்றும் குறியீடுகளுக்கு இடையிலான நிலையில் ஆஃப்செட்) அல்லது (வரையறுக்கப்படாதது) இருக்க வேண்டும். போஸிக்ஸ் மற்றும் இடதுசாரி பேராசை குறைதீர்க்கும் கொள்கைகள் இரண்டும் இந்த விஷயத்தில் முதல் மாற்று விரும்பத்தக்கது என்பதை ஒப்புக்கொள்கின்றன. டி. என். எஃப். ஏ நிர்ணயம் என்பது ஒரு என். எஃப். ஏ-வை டி. எஃப். ஏ-வாக மாற்றும் நியதி அதிகார தொகுப்பு கட்டுமான வழிமுறையை அடிப்படையாகக் கொண்டது. இந்த வழிமுறை சாத்தியமான அனைத்து சரங்களிலும் NFA ஐ உருவகப்படுத்துகிறது. உருவகப்படுத்துதலின் ஒவ்வொரு கட்டத்திலும், என். எஃப். ஏ நிலைகளின் செயலில் உள்ள தொகுப்பு ஒரு புதிய டி. எஃப். ஏ நிலையை உருவாக்குகிறது. புதிய நிலை தற்போதுள்ள டி. எஃப். ஏ நிலைக்கு ஒத்ததாக இருந்தால், அது நிராகரிக்கப்பட்டு தற்போதுள்ள நிலைக்கு மாற்றப்படும், மேலும் உருவகப்படுத்துதலின் தற்போதைய கிளை முடிவடைகிறது. இல்லையெனில் புதிய மாநிலம் வளர்ந்து வரும் டி. எஃப். ஏ நிலைகளின் தொகுப்பில் சேர்க்கப்படுகிறது, மேலும் இந்த மாநிலத்திலிருந்து உருவகப்படுத்துதல் தொடர்கிறது. இறுதியில் நிர்ணயம் முடிவடைகிறதுஃ சாத்தியமான அனைத்து சரங்களின் தொகுப்பும் எல்லையற்றதாக இருந்தாலும், வெவ்வேறு டி. எஃப். ஏ நிலைகளின் தொகுப்பு வரையறுக்கப்பட்டுள்ளது, மேலும் ஒரு கட்டத்தில் அனைத்து புதிய நிலைகளும் ஏற்கனவே உள்ளவற்றுடன் ஒத்ததாக மாறும். டிடிஎஃப்ஏ விஷயத்தில் அப்பாவித்தனமான பவர்செட் கட்டுமானம் ஒரு சிக்கலை எதிர்கொள்கிறதுஃ டிடிஎஃப்ஏ மாநிலங்களில் குறிச்சொல் தகவல் உள்ளது, இது உருவகப்படுத்துதலின் ஒவ்வொரு கட்டத்திலும் மாறுகிறது (ஆஃப்செட்டுகள் அதிகரிக்கும் போது). இது டி. டி. எஃப். ஏ நிலைகளை வரைபடமாக்குவதைத் தடுக்கிறதுஃ ஒரே மாதிரியான டி. என். எஃப். ஏ நிலைகளைக் கொண்ட ஒரு ஜோடி நிலைகள், ஆனால் வெவ்வேறு டேக் ஆஃப்செட்டுகள் ஒரே மாதிரியானவை அல்ல, அவற்றை வரைபடமாக்க முடியாது. இதன் விளைவாக, உருவகப்படுத்துதல் காலவரையின்றி தொடர்கிறது, டி. டி. எஃப். ஏ நிலைகளின் தொகுப்பு வளர்கிறது, மேலும் நிர்ணயம் முடிவடையாது. இந்த சிக்கலைத் தீர்க்க, லாரிக்காரி திசைதிருப்பல் யோசனையைப் பயன்படுத்தினார்ஃ டி. டி. எஃப். ஏ மாநிலங்களில் உடனடி குறிச்சொல் மதிப்புகளைச் சேமிப்பதற்குப் பதிலாக, அவற்றை மறைமுகமாக பதிவேடுகளில் சேமிக்க அவர் பரிந்துரைத்தார். பதிவேடுகளில் உள்ள குறிச்சொல் மதிப்புகள் வேறுபட்டிருக்கலாம், ஆனால் பதிவேடுகள் ஒரே மாதிரியாக இருக்கும் வரை அது ஒரு பொருட்டல்ல. இது முடித்தல் சிக்கலைத் தீர்க்கிறதுஃ டி. டி. எஃப். ஏ மாநிலங்களில் வெவ்வேறு பதிவேடுகள் இருந்தாலும், தொடர்புடைய பதிவு மதிப்புகளை நகலெடுக்கும் செயல்பாடுகளைச் சேர்ப்பதன் மூலம் அவற்றை ஒரே மாதிரியாக (ஒருவருக்கொருவர் வரைபடமாக்கலாம்) செய்யலாம். திசைதிருப்பல் இலவசம் அல்லஃ பதிவு மதிப்புகளைப் புதுப்பிக்கும் மாற்றங்களில் இயக்க நேரப் பதிவு செயல்பாடுகளைச் சேர்க்க வேண்டும். ரன்டைம் ஓவர்ஹெட்டைக் குறைக்க, டிராஃபிமோவிச் லுக்ஹெட் ஆப்டிமைசேஷனைப் பயன்படுத்தினார். பதிவு நடவடிக்கைகளை உள்வரும் மாற்றத்திலிருந்து டி. டி. எஃப். ஏ மாநிலத்திற்கு இந்த மாநிலத்திலிருந்து வெளிச்செல்லும் மாற்றங்களுக்கு நகர்த்துவதே யோசனை. இந்த வழியில் செயல்பாடுகள் லுக்ஹெட் சின்னத்தில் பிரிக்கப்படுகின்றன, இது பதிவு ஆயுட்காலங்களுக்கு இடையிலான ஒன்றுடன் ஒன்று குறைகிறது மற்றும் விரைவான டி. டி. எஃப். ஏ விளைவை ஏற்படுத்துகிறது. இந்த உகப்பாக்கத்தைப் பயன்படுத்த, கட்டுமானத்தில் உள்ள ஒவ்வொரு டிடிஎஃப்ஏ மாநிலத்திலும் லுக்ஹெட் குறிச்சொற்களைக் கண்காணிப்பது அவசியம் மற்றும் டிடிஎஃப்ஏ நிலைகளை வரைபடமாக்கும்போது அவற்றை கணக்கில் எடுத்துக்கொள்வது அவசியம். படம் 3 இயங்கும் உதாரணத்திற்கான தீர்மானிக்கும் செயல்முறையைக் காட்டுகிறது. இதன் விளைவாக வரும் டிடிஎஃப்ஏவை படம் 4 காட்டுகிறது. உகப்பாக்கங்கள் உகப்பாக்கங்களின் குறிக்கோள் டிடிஎஃப்ஏ அளவு மற்றும் பதிவேடுகள் மற்றும் செயல்பாடுகளின் எண்ணிக்கையை மாற்றங்களில் குறைப்பதாகும். இந்த பிரிவு ஒரு நடைமுறை டிடிஎஃப்ஏ செயல்படுத்தலில் பயன்படுத்தப்படும் சில தேர்வுகளை விவரிக்கிறது. இந்த உகப்பாக்கங்கள் எதுவும் டிடிஎஃப்ஏ செயல்பாட்டிற்கு குறிப்பாக சிக்கலானவை அல்லது இன்றியமையாதவை அல்ல, ஆனால் ஒன்றாக மற்றும் சரியான வரிசையில் பயன்படுத்தப்படும்போது அவை டிடிஎஃப்ஏவை கணிசமாக வேகமாகவும் சிறியதாகவும் மாற்றும். நிலையான-குறிச்சொற்கள் உகப்பாக்கம் வழக்கமான வெளிப்பாடு மட்டத்தில் (டிஎன்எஃப்ஏ கட்டுமானத்திற்கு முன்பு) பயன்படுத்தப்படுகிறது. யோசனை என்னவென்றால், ஒரு ஜோடி குறிச்சொற்கள் ஒருவருக்கொருவர் நிலையான தூரத்திற்குள் இருந்தால், அவை இரண்டையும் கண்காணிக்க வேண்டிய அவசியமில்லைஃ ஒரு குறிச்சொல்லின் மதிப்பை மற்ற குறிச்சொல்லின் மதிப்பிலிருந்து ஒரு நிலையான ஆஃப்செட்டைச் சேர்ப்பதன் மூலம் கணக்கிட முடியும். எடுத்துக்காட்டாக, வழக்கமான வெளிப்பாடு குறிச்சொற்களில் மற்றும் ஒருவருக்கொருவர் ஒரு சின்ன தூரத்திற்குள் உள்ளன, எனவே கணக்கிடப்படலாம். இந்த உகப்பாக்கம் டிடிஎஃப்ஏ கட்டுமான நேரம் (நிலையான குறிச்சொற்கள் டிஎன்எஃப்ஏ கட்டுமானம் மற்றும் தீர்மானிப்பதில் இருந்து விலக்கப்பட்டுள்ளதால்) மற்றும் பொருந்தும் நேரம் (குறைவான பதிவு செயல்பாடுகள் இருப்பதால்) ஆகிய இரண்டையும் குறைக்கும். டிடிஎஃப்ஏ கட்டுமானத்திற்குப் பிறகு பதிவு உகப்பாக்கங்கள் பயன்படுத்தப்படுகின்றன. ஒரு டிடிஎஃப்ஏ பதிவேடுகளில் ஒரு கட்டுப்பாட்டு ஓட்ட வரைபடத்தைத் (சிஎஃப்ஜி) தூண்டுகிறதுஃ மாற்றங்களின் செயல்பாடுகள் அடிப்படை தொகுதிகளை உருவாக்குகின்றன, மேலும் இரண்டு தொகுதிகளுக்கு இடையில் ஒரு வளைவு உள்ளது, அவற்றில் ஒன்று மற்றொன்றிலிருந்து டிடிஎஃப்ஏ மாற்றங்களால் அடையக்கூடியதாக இருந்தால், மற்ற பதிவு செயல்பாடுகளைக் கடந்து செல்லாமல். சிஎஃப்ஜி என்பது பதிவேடுகளில் உள்ள ஒரு நிரலை மாறிகளாகக் குறிக்கிறது, எனவே வழக்கமான தொகுப்பு உகப்பாக்கம் அதற்கு பயன்படுத்தப்படலாம் (லைவன்ஸ் பகுப்பாய்வு, டெட் கோட் நீக்குதல் மற்றும் பதிவு ஒதுக்கீடு போன்றவை). டி. டி. எஃப். ஏ மினிமைசேஷன் டி. எஃப். ஏ மினிமைசேஷனுடன் மிகவும் ஒத்திருக்கிறது, ஒரு கூடுதல் கட்டுப்பாட்டைத் தவிரஃ டி. டி. எஃப். ஏ மாற்றங்களில் பதிவு நடவடிக்கைகள் கணக்கில் எடுத்துக்கொள்ளப்பட வேண்டும். எனவே, டி. டி. எஃப். ஏ ஒரே மாதிரியானவை, ஆனால் ஒரே சின்னத்தில் உள்வரும் மாற்றங்களில் வெவ்வேறு பதிவு செயல்களைக் கொண்டுள்ளன, அவற்றை இணைக்க முடியாது. டிஎஃப்ஏ மினிமைசேஷனுக்கான அனைத்து வழக்கமான வழிமுறைகளும் டிடிஎஃப்ஏ மினிமைசேஷனுக்கு ஏற்ப மாற்றியமைக்கப்படலாம், எடுத்துக்காட்டாக மூரின் வழிமுறை ஆர்இ2சி லெக்சர் ஜெனரேட்டரில் பயன்படுத்தப்படுகிறது. படம் 5 வழக்கமான வெளிப்பாட்டிற்கான உகந்த டிடிஎஃப்ஏவைக் காட்டுகிறது. இது உண்மையில் ஒரு சொற்பொருள் சமமான வழக்கமான வெளிப்பாட்டிற்கான டி. டி. எஃப். ஏ போன்றது என்பதை நினைவில் கொள்க, அங்கு தெளிவின்மை அகற்றப்பட்டுள்ளது. தீர்மானிக்கும் போது தெளிவற்ற தன்மை தீர்க்கப்படுகிறது, மேலும் படம் 4 இல் உள்ள உகந்ததாக இல்லாத டி. டி. எஃப். ஏ சந்தேகத்திற்கு இடமின்றி உள்ளது, ஆனால் இது சில உள்ளமைக்கப்பட்ட பணிநீக்கத்தைக் கொண்டுள்ளது, அவை உகந்ததாக்குவதன் மூலம் அகற்றப்படலாம். டிடிஎஃப்ஏ கட்டுமானத்திற்காக செலவிடப்பட்ட நேரம் இயக்க நேரத்தில் சேர்க்கப்படாதபோது, பதிவேடுகளுடன் கூடிய மல்டி-பாஸ் டிடிஎஃப்ஏ டிடிஎஃப்ஏ முன்கூட்டியே தீர்மானிக்க மிகவும் பொருத்தமானது (எ. கா. லெக்ஸர் ஜெனரேட்டர்களில்). ஆனால் சரியான நேரத்தில் தீர்மானிப்பதற்காக (எ. கா. வழக்கமான வெளிப்பாடு நூலகங்களில்) டி. டி. எஃப். ஏ கட்டுமான நேரத்தைக் குறைப்பது விரும்பத்தக்கது. மற்றொரு கவலை ஒரு வழக்கமான வெளிப்பாட்டில் குறிச்சொல் அடர்த்திஃ குறிச்சொற்களின் எண்ணிக்கை ஒப்பீட்டளவில் சிறியதாக இருந்தால் பதிவேடுகளுடன் கூடிய டி. டி. எஃப். ஏ திறமையானது. ஆனால் பெரிதும் குறிக்கப்பட்ட வழக்கமான வெளிப்பாடுகளுக்கு பதிவேடுகளுடன் டி. டி. எஃப். ஏ துணை உகந்ததுஃ மாற்றங்கள் செயல்பாடுகளுடன் குழப்பமடைகின்றன, இதனால் டி. டி. எஃப். ஏ செயல்படுத்தல் மெதுவாகிறது. உயிர் மற்றும் குறுக்கீடு தகவல்களின் அளவு காரணமாக பதிவு உகப்பாக்கங்களும் சிக்கலானவையாக மாறுகின்றன. மல்டி-பாஸ் டிடிஎஃப்ஏ இரண்டு சிக்கல்களையும் நிவர்த்தி செய்கிறதுஃ அவை டிடிஎஃப்ஏ கட்டுமான நேரத்தைக் குறைக்கின்றன, மேலும் அவை அடர்த்தியான சப்மேட்ச் பிரித்தெடுத்தலுக்கு மிகவும் பொருத்தமானவை. கனோனிக்கல் டி. டி. எஃப். ஏ உடன் முக்கிய வேறுபாடு என்னவென்றால், மல்டி-பாஸ் டி. டி. எஃப். ஏ பதிவு செயல்பாடுகளைக் கொண்டிருக்கவில்லை. அதற்கு பதிலாக அவை பல பாஸ்களைக் கொண்டுள்ளனஃ உள்ளீட்டு சரத்துடன் பொருந்தக்கூடிய ஒரு முன்னோக்கி பாஸ் மற்றும் டி. டி. எஃப். ஏ நிலைகளின் வரிசையை பதிவு செய்கிறது, மேலும் ஒன்று அல்லது அதற்கு மேற்பட்ட பின்தங்கிய பாஸ்கள் பதிவு செய்யப்பட்ட நிலைகள் வழியாக மீண்டும் நிகழ்கின்றன மற்றும் சப்மேட்ச் தகவல்களை சேகரிக்கின்றன. ஒரு பின்தங்கிய பாஸ் போதுமானது, ஆனால் ஒரு கூடுதல் பாஸ் பயன்படுத்தப்படலாம் எ. கா. சப்மேட்ச் முடிவுகளுக்கு தேவையான அளவு நினைவகத்தை மதிப்பிடுவதற்கு. டிடிஎஃப்ஏ நிலைகளின் வரிசையிலிருந்து பொருந்தக்கூடிய டிஎன்எஃப்ஏ பாதையை மீண்டும் கண்டுபிடிப்பதற்காக, மல்டி-பாஸ் டிடிஎஃப்ஏ மாற்றங்கள் மற்றும் இறுதி நிலைகளில் பின்னிணைப்புகளைப் பயன்படுத்துகிறது. ஒரு பின்னிணைப்பு என்பது ஒரு ஜோடி, இதில் முதல் கூறு முந்தைய மாற்றங்களில் பின்னிணைப்பு வரிசைகளில் ஒரு குறியீடாகும், இரண்டாவது கூறு டிடிஎஃப்ஏ நிலைகளுக்கு இடையிலான டிஎன்எஃப்ஏ பாதையின் ஒரு துண்டுக்கான குறிச்சொற்களின் வரிசையாகும். படம் 6 ஒரு சரத்தில் வழக்கமான வெளிப்பாடு பொருத்தத்திற்கான மல்டி-பாஸ் டிடிஎஃப்ஏவின் உதாரணத்தைக் காட்டுகிறது (அதே வழக்கமான வெளிப்பாட்டிற்கான பதிவேடுகளுடன் டிடிஎஃப்ஏவைக் காட்டும் படம் 0 உடன் ஒப்பிடுக): முன்னோக்கி பாஸ் 0,1,1,2 நிலைகளின் வரிசையை சேகரிக்கிறது. பின்தங்கிய பாஸ் நிலை 2 இலிருந்து நிலை 0 க்கு பின்னிணைப்புகளைக் கண்டறிந்து குறிச்சொல் வரிசைகள் மற்றும் உள்ளீட்டு சின்னங்களை ஒருங்கிணைக்கிறது. இது பின்னிணைப்புடன் தொடங்குகிறது. குறிக்கப்பட்ட சரம் உள்ளது. குறியீடு 0 நிலை 1 இலிருந்து நிலை 2 க்கு முந்தைய மாற்றத்தின் பின்னிணைப்பைத் தேர்ந்தெடுக்கிறது (இந்த மாற்றத்தில் உள்ள ஒரே ஒன்று). குறிக்கப்பட்ட சரம் ஆகிறது. குறியீடு 0 நிலை 1 இலிருந்து நிலை 1 க்கு முந்தைய சுழல் மாற்றத்தின் பின்னிணைப்பைத் தேர்ந்தெடுக்கிறது. குறிக்கப்பட்ட சரம் ஆகிறது. குறியீடு 0 நிலை 0 இலிருந்து நிலை 1 க்கு முந்தைய மாற்றத்தின் பின்னிணைப்பைத் தேர்ந்தெடுக்கிறது. இதன் விளைவாக குறிக்கப்பட்ட சரம். ஒவ்வொரு குறிச்சொல்லுக்கும் கடைசி ஆஃப்செட்டுகள் அல்லது ஆஃப்செட் பட்டியல்களை மறுகட்டமைக்க தேவையான அனைத்து தகவல்களும் இதில் உள்ளன. முகமது இம்ரான் சவுத்ரியால் விவரிக்கப்பட்ட தொடர்புடைய தானியங்கி ஸ்டாட்ஃபா டிடிஎஃப்ஏவுடன் மிகவும் ஒத்திருக்கிறது, தவிர அவை மாநிலங்களில் பதிவு நடவடிக்கைகளைக் கொண்டுள்ளன, மாற்றங்களில் அல்ல. கிராத்வோலால் விவரிக்கப்பட்ட டி. எஸ். எஸ். டி. க்கள் (டிட்டர்மினிஸ்டிக் ஸ்ட்ரீமிங் ஸ்ட்ரிங் டிரான்ஸ்யூசர்கள்) டி. டி. எஃப். ஏ-வுக்கு மிகவும் தொலைதூர உறவினர், இது சப்மேட்ச் பிரித்தெடுத்தலை விட முழு பாகுபடுத்தலுக்கு மிகவும் பொருத்தமானது. டிஎஸ்டிஎஸ்டி நிலைகள் ε-மூடுதலால் கட்டப்பட்ட பாதை மரங்களைக் கொண்டுள்ளன, அதே நேரத்தில் டிடிஎஃப்ஏ நிலைகள் இதே போன்ற தகவல்களை சிதைந்த வடிவத்தில் (பதிவு பதிப்புகள் மற்றும் லுக்ஹெட் குறிச்சொற்கள்) கொண்டுள்ளன. குறிப்புகள் ஃபைனைட் ஆட்டோமேட்டா