Tagged Deterministic Finite Automaton
ಸ್ವಯಂಚಾಲಿತ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಟ್ಯಾಗ್ ಮಾಡಲಾದ ನಿರ್ಣಾಯಕ ಸೀಮಿತ ಸ್ವಯಂಚಾಲಿತ ಯಂತ್ರವು (ಟಿಡಿಎಫ್ಎ) ನಿರ್ಣಾಯಕ ಸೀಮಿತ ಸ್ವಯಂಚಾಲಿತ ಯಂತ್ರದ (ಡಿಎಫ್ಎ) ವಿಸ್ತರಣೆಯಾಗಿದೆ. ಸಾಮಾನ್ಯ ಭಾಷೆಗಳ ಗುರುತಿಸುವಿಕೆಯ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುವುದರ ಜೊತೆಗೆ, ಟಿ. ಡಿ. ಎಫ್. ಎ. ಯು ಸಬ್ಮ್ಯಾಚ್ ಎಕ್ಸ್ಟ್ರಾಕ್ಷನ್ ಮತ್ತು ಪಾರ್ಸಿಂಗ್ ಮಾಡುವ ಸಾಮರ್ಥ್ಯವನ್ನು ಹೊಂದಿದೆ. ಕ್ಯಾನೊನಿಕಲ್ ಡಿಎಫ್ಎ ಒಂದು ಸ್ಟ್ರಿಂಗ್ ನಿಯಮಿತ ಅಭಿವ್ಯಕ್ತಿಯಿಂದ ವ್ಯಾಖ್ಯಾನಿಸಲಾದ ಭಾಷೆಗೆ ಸೇರಿದೆಯೇ ಎಂದು ಕಂಡುಹಿಡಿಯಬಹುದಾದರೂ, ಟಿಡಿಎಫ್ಎ ನಿರ್ದಿಷ್ಟ ಉಪ ಅಭಿವ್ಯಕ್ತಿಗಳಿಗೆ ಹೊಂದಿಕೆಯಾಗುವ ಸಬ್ಸ್ಟ್ರಿಂಗ್ಗಳನ್ನು ಸಹ ಹೊರತೆಗೆಯಬಹುದು. ಹೆಚ್ಚು ಸಾಮಾನ್ಯವಾಗಿ, ಟಿಡಿಎಫ್ಎ ನಿಯಮಿತ ಅಭಿವ್ಯಕ್ತಿಯಲ್ಲಿ ಟ್ಯಾಗ್ ಮಾಡಲಾದ ಸ್ಥಾನಗಳಿಗೆ ಹೊಂದಿಕೆಯಾಗುವ ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ನಲ್ಲಿನ ಸ್ಥಾನಗಳನ್ನು ಗುರುತಿಸಬಹುದು (ಟ್ಯಾಗ್ಗಳು ಆವರಣಗಳನ್ನು ಸೆರೆಹಿಡಿಯುವಂತೆಯೇ ಮೆಟಾ-ಚಿಹ್ನೆಗಳಾಗಿವೆ, ಆದರೆ ಜೋಡಣೆಯ ಅಗತ್ಯವಿಲ್ಲದೇ). ಟಿ. ಡಿ. ಎಫ್. ಎ. ಇತಿಹಾಸವನ್ನು ಮೊದಲ ಬಾರಿಗೆ 2000 ರಲ್ಲಿ ವಿಲ್ಲೆ ಲೌರಿಕಾರಿ ಅವರು ವಿವರಿಸಿದ್ದಾರೆ. ಅದಕ್ಕೂ ಮೊದಲು ನಿರ್ಣಾಯಕ ಸೀಮಿತ-ಸ್ಥಿತಿಯ ಸ್ವಯಂಚಾಲಿತ ಯಂತ್ರದಲ್ಲಿ ಒಂದು ಪಾಸ್ನಲ್ಲಿ ಸಬ್ಮ್ಯಾಚ್ ಹೊರತೆಗೆಯುವಿಕೆಯನ್ನು ನಿರ್ವಹಿಸಲು ಸಾಧ್ಯವೇ ಎಂಬುದು ತಿಳಿದಿರಲಿಲ್ಲ, ಆದ್ದರಿಂದ ಈ ಕಾಗದವು ಒಂದು ಪ್ರಮುಖ ಪ್ರಗತಿಯಾಗಿತ್ತು. ಲೌರಿಕಾರಿ ಟಿ. ಡಿ. ಎಫ್. ಎ. ರಚನೆಯನ್ನು ವಿವರಿಸಿದನು ಮತ್ತು ನಿರ್ಣಯ ಪ್ರಕ್ರಿಯೆಯು ಕೊನೆಗೊಳ್ಳುತ್ತದೆ ಎಂಬುದಕ್ಕೆ ಪುರಾವೆಯನ್ನು ನೀಡಿದನು, ಆದಾಗ್ಯೂ ಅಲ್ಗಾರಿದಮ್ ಅಸ್ಪಷ್ಟತೆಯನ್ನು ಸರಿಯಾಗಿ ನಿರ್ವಹಿಸಲಿಲ್ಲ. 2007ರಲ್ಲಿ ಕ್ರಿಸ್ ಕುಕ್ಲೆವಿಕ್ಜ್ ಅವರು ಹಾಸ್ಕೆಲ್ ಗ್ರಂಥಾಲಯದ ರೆಜೆಕ್ಸ್-ಟಿಡಿಎಫ್ಎಯಲ್ಲಿ ಟಿಡಿಎಫ್ಎಯನ್ನು ಪಿಒಎಸ್ಐಎಕ್ಸ್ ದೀರ್ಘಾವಧಿಯ ಹೊಂದಾಣಿಕೆಯ ಶಬ್ದಾರ್ಥಗಳೊಂದಿಗೆ ಜಾರಿಗೆ ತಂದರು. ಕುಕ್ಲೆವಿಕ್ಜ್ ಅಲ್ಗಾರಿದಮ್ನ ಅನೌಪಚಾರಿಕ ವಿವರಣೆಯನ್ನು ನೀಡಿದರು ಮತ್ತು ಟಿಡಿಎಫ್ಎ ಪೊಸಿಕ್ಸ್ ದೀರ್ಘಾವಧಿಯ-ಹೊಂದಾಣಿಕೆಯ ದ್ವಂದ್ವವನ್ನು ಸಮರ್ಥವಾಗಿದೆಯೇ ಎಂಬ ಪ್ರಮುಖ ಪ್ರಶ್ನೆಗೆ ಉತ್ತರಿಸಿದರು, ಇದನ್ನು ಇತರ ಸಂಶೋಧಕರು ಅನುಮಾನಿಸಿದ್ದರು. 2017ರಲ್ಲಿ ಉಲ್ಯಾ ಟ್ರಾಫಿಮೋವಿಚ್ ಅವರು ಟಿ. ಡಿ. ಎಫ್. ಎ. ಯನ್ನು ಒನ್-ಸಿಂಬಲ್ ಲುಕ್ಹೆಡ್ನೊಂದಿಗೆ ವಿವರಿಸಿದ್ದಾರೆ. ಲುಕ್ಹೆಡ್ ಚಿಹ್ನೆಯ ಬಳಕೆಯು ಟಿಡಿಎಫ್ಎಯಲ್ಲಿ ರಿಜಿಸ್ಟರ್ಗಳು ಮತ್ತು ರಿಜಿಸ್ಟರ್ ಕಾರ್ಯಾಚರಣೆಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಡಿಮೆ ಮಾಡುತ್ತದೆ, ಇದು ಲೌರಿಕಾರಿ ಟಿಡಿಎಫ್ಎಗಿಂತ ವೇಗವಾಗಿ ಮತ್ತು ಚಿಕ್ಕದಾಗಿರುತ್ತದೆ. ಟ್ರಾಫಿಮೊವಿಚ್ ಅವರು ಟಿಡಿಎಫ್ಎ ರೂಪಾಂತರಗಳನ್ನು ಟಿಡಿಎಫ್ಎ (1) ಮತ್ತು ಟಿಡಿಎಫ್ಎ (0) ನೊಂದಿಗೆ ಮತ್ತು ಇಲ್ಲದೆ ಎಲ್ಆರ್ ಪಾರ್ಸರ್ಗಳಾದ ಎಲ್ಆರ್ (1) ಮತ್ತು ಎಲ್ಆರ್ (0) ನೊಂದಿಗೆ ಸಾದೃಶ್ಯದಿಂದ ಕರೆದರು. ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಓಪನ್-ಸೋರ್ಸ್ ಲೆಕ್ಸರ್ ಜನರೇಟರ್ ಆರ್ಇ2ಸಿಯಲ್ಲಿ ಅಳವಡಿಸಲಾಗಿದೆ. ಟ್ರಾಫಿಮೋವಿಚ್ ಅವರು ಕುಕ್ಲೆವಿಕ್ಜ್ ದ್ವಂದ್ವ ನಿವಾರಣಾ ಕ್ರಮಾವಳಿಯನ್ನು ಔಪಚಾರಿಕಗೊಳಿಸಿದರು. 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 ಕ್ಕೆ ಹಿಂದಿನ ಪರಿವರ್ತನೆಯ ಮೇಲಿನ ಬ್ಯಾಕ್ಲಿಂಕ್ ಅನ್ನು ಆಯ್ಕೆ ಮಾಡುತ್ತದೆ. ಪರಿಣಾಮವಾಗಿ ಟ್ಯಾಗ್ ಮಾಡಲಾದ ಸ್ಟ್ರಿಂಗ್ ಆಗಿದೆ. ಇದು ಪ್ರತಿ ಟ್ಯಾಗ್ಗೆ ಕೊನೆಯ ಆಫ್ಸೆಟ್ಗಳನ್ನು ಅಥವಾ ಆಫ್ಸೆಟ್ ಪಟ್ಟಿಗಳನ್ನು ಪುನರ್ನಿರ್ಮಿಸಲು ಅಗತ್ಯವಾದ ಎಲ್ಲಾ ಮಾಹಿತಿಯನ್ನು ಒಳಗೊಂಡಿದೆ. ಮೊಹಮ್ಮದ್ ಇಮ್ರಾನ್ ಚೌಧರಿ ವಿವರಿಸಿದ ಸಂಬಂಧಿತ ಸ್ವಯಂಚಾಲಿತ ಸ್ಟ್ಯಾಡ್ಫಾ ಟಿಡಿಎಫ್ಎಗೆ ಹೋಲುತ್ತದೆ, ಹೊರತುಪಡಿಸಿ ಅವರು ರಾಜ್ಯಗಳಲ್ಲಿ ನೋಂದಾಯಿತ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಹೊಂದಿದ್ದಾರೆ, ಪರಿವರ್ತನೆಯ ಮೇಲೆ ಅಲ್ಲ. ಗ್ರಾಥ್ವೋಲ್ ವಿವರಿಸಿದ ಡಿ. ಎಸ್. ಎಸ್. ಟಿಗಳು (ಡಿಟೆರ್ಮಿನಿಸ್ಟಿಕ್ ಸ್ಟ್ರೀಮಿಂಗ್ ಸ್ಟ್ರಿಂಗ್ ಟ್ರಾನ್ಸ್ಡ್ಯೂಸರ್ಗಳು) ಟಿ. ಡಿ. ಎಫ್. ಎ. ಗೆ ಹೆಚ್ಚು ದೂರದ ಸಂಬಂಧಿಯಾಗಿದ್ದು, ಸಬ್ಮ್ಯಾಚ್ ಎಕ್ಸ್ಟ್ರಾಕ್ಷನ್ಗಿಂತ ಪೂರ್ಣ ಪಾರ್ಸಿಂಗ್ಗೆ ಸೂಕ್ತವಾಗಿವೆ. ಡಿ. ಎಸ್. ಎಸ್. ಟಿ. ರಾಜ್ಯಗಳು ε-ಮುಚ್ಚುವಿಕೆಯಿಂದ ನಿರ್ಮಿಸಲಾದ ಪಥ ಮರಗಳನ್ನು ಹೊಂದಿರುತ್ತವೆ, ಆದರೆ ಟಿ. ಡಿ. ಎಫ್. ಎ. ರಾಜ್ಯಗಳು ಇದೇ ರೀತಿಯ ಮಾಹಿತಿಯನ್ನು ಕೊಳೆತ ರೂಪದಲ್ಲಿ ಹೊಂದಿರುತ್ತವೆ (ರಿಜಿಸ್ಟರ್ ಆವೃತ್ತಿಗಳು ಮತ್ತು ಲುಕ್ಹೆಡ್ ಟ್ಯಾಗ್ಗಳು). ಉಲ್ಲೇಖಗಳು ಸೀಮಿತ ಸ್ವಯಂಚಾಲಿತ