Nested stack automaton
ಆಟೋಮ್ಯಾಟಾ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ನೆಸ್ಟೆಡ್ ಸ್ಟ್ಯಾಕ್ ಆಟೋಮ್ಯಾಟನ್ ಒಂದು ಸೀಮಿತ ಆಟೋಮ್ಯಾಟನ್ ಆಗಿದ್ದು ಅದು ಹೆಚ್ಚುವರಿ ಸ್ಟ್ಯಾಕ್ಗಳಾಗಿರಬಹುದಾದ ಡೇಟಾವನ್ನು ಹೊಂದಿರುವ ಸ್ಟ್ಯಾಕ್ ಅನ್ನು ಬಳಸಬಹುದು. ಸ್ಟ್ಯಾಕ್ ಆಟೋಮ್ಯಾಟನ್ನಂತೆ, ನೆಸ್ಟೆಡ್ ಸ್ಟ್ಯಾಕ್ ಆಟೋಮ್ಯಾಟನ್ ಸ್ಟ್ಯಾಕ್ನಲ್ಲಿ ಮೇಲಕ್ಕೆ ಅಥವಾ ಕೆಳಕ್ಕೆ ಹೆಜ್ಜೆ ಹಾಕಬಹುದು ಮತ್ತು ಪ್ರಸ್ತುತ ಚಿಹ್ನೆಯನ್ನು ಓದಬಹುದು; ಜೊತೆಗೆ, ಇದು ಯಾವುದೇ ಸ್ಥಳದಲ್ಲಿ ಹೊಸ ಸ್ಟ್ಯಾಕ್ ಅನ್ನು ರಚಿಸಬಹುದು, ಅದರ ಮೇಲೆ ಕಾರ್ಯನಿರ್ವಹಿಸಬಹುದು, ಅಂತಿಮವಾಗಿ ಅದನ್ನು ನಾಶಪಡಿಸಬಹುದು ಮತ್ತು ಹಳೆಯ ಸ್ಟಾಕ್ನಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುವುದನ್ನು ಮುಂದುವರಿಸಬಹುದು. ಈ ರೀತಿಯಲ್ಲಿ, ಸ್ಟ್ಯಾಕ್ಗಳನ್ನು ಅನಿಯಂತ್ರಿತ ಆಳಕ್ಕೆ ಪುನರಾವರ್ತಿತವಾಗಿ ನೆಸ್ಟ್ ಮಾಡಬಹುದು; ಆದಾಗ್ಯೂ, ಆಟೋಮ್ಯಾಟನ್ ಯಾವಾಗಲೂ ಒಳಗಿನ ಸ್ಟ್ಯಾಕ್ನಲ್ಲಿ ಮಾತ್ರ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ನೆಸ್ಟೆಡ್ ಸ್ಟ್ಯಾಕ್ ಆಟೋಮ್ಯಾಟನ್ ಸೂಚ್ಯಂಕದ ಭಾಷೆಯನ್ನು ಗುರುತಿಸುವ ಸಾಮರ್ಥ್ಯವನ್ನು ಹೊಂದಿದೆ, ಮತ್ತು ವಾಸ್ತವವಾಗಿ ಸೂಚ್ಯಂಕದ ಭಾಷೆಗಳ ವರ್ಗವು ನಿಖರವಾಗಿ ಒನ್-ವೇ ನಾನ್-ಡಿಟೆರ್ಮಿನಿಸ್ಟಿಕ್ ನೆಸ್ಟೆಡ್ ಸ್ಟ್ಯಾಕ್ ಆಟೋಮ್ಯಾಟಾದಿಂದ ಸ್ವೀಕರಿಸಲ್ಪಟ್ಟ ಭಾಷೆಗಳ ವರ್ಗವಾಗಿದೆ. ನೆಸ್ಟೆಡ್ ಸ್ಟ್ಯಾಕ್ ಆಟೋಮ್ಯಾಟಾವನ್ನು ಕಡಿಮೆ ಕಂಪ್ಯೂಟೇಶನಲ್ ಶಕ್ತಿಯನ್ನು ಹೊಂದಿರುವ ಎಂಬೆಡೆಡ್ ಪುಷ್ ಡೌನ್ ಆಟೋಮ್ಯಾಟಾದೊಂದಿಗೆ ಗೊಂದಲಗೊಳಿಸಬಾರದು. ಫಾರ್ಮಲ್ ಡೆಫಿನಿಷನ್ ಆಟೋಮ್ಯಾಟನ್ ಎ (ಅನಿರ್ದಿಷ್ಟ ದ್ವಿಮುಖ) ನೆಸ್ಟೆಡ್ ಸ್ಟ್ಯಾಕ್ ಆಟೋಮ್ಯಾಟನ್ ಒಂದು ಟುಪಲ್ ಆಗಿದ್ದು, ಅಲ್ಲಿ ಕ್ಯೂ, ಎಸ್ಎಸ್, ಮತ್ತು ಜಾತಗಳು ಅನುಕ್ರಮವಾಗಿ ಖಾಲಿ ಇಲ್ಲದ ಸೀಮಿತ ಸ್ಥಿತಿಗಳು, ಇನ್ಪುಟ್ ಚಿಹ್ನೆಗಳು, ಮತ್ತು ಸ್ಟ್ಯಾಕ್ ಚಿಹ್ನೆಗಳಾಗಿವೆ, [,], ಮತ್ತು] ಇವು ವಿಶಿಷ್ಟವಾದ ವಿಶೇಷ ಚಿಹ್ನೆಗಳಾಗಿದ್ದು, ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ ಮತ್ತು (ಉಪ) ಸ್ಟ್ಯಾಕ್ ಸ್ಟ್ರಿಂಗ್ ಎರಡಕ್ಕೂ ಲೆಫ್ಟ್ ಎಂಡ್ಮಾರ್ಕರ್ ಆಗಿ ಬಳಸಲಾಗುತ್ತದೆ,] ಅನ್ನು ಈ ಸ್ಟ್ರಿಂಗ್ಗಳಿಗೆ ರೈಟ್ ಎಂಡ್ಮಾರ್ಕರ್ ಆಗಿ ಬಳಸಲಾಗುತ್ತದೆ,] ಇದನ್ನು ಇಡೀ ಸ್ಟ್ಯಾಕ್ ಅನ್ನು ಸೂಚಿಸುವ ಸ್ಟ್ರಿಂಗ್ನ ಅಂತಿಮ ಎಂಡ್ಮಾರ್ಕರ್ ಆಗಿ ಬಳಸಲಾಗುತ್ತದೆ. ಒಂದು ವಿಸ್ತೃತ ಇನ್ಪುಟ್ ವರ್ಣಮಾಲೆಯನ್ನು '=' [,] 'ನಿಂದ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ, ಒಂದು ವಿಸ್ತೃತ ಸ್ಟ್ಯಾಕ್ ವರ್ಣಮಾಲೆಯನ್ನು' = '[,]' ನಿಂದ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ, ಮತ್ತು ಇನ್ಪುಟ್ ಚಲನೆ ನಿರ್ದೇಶನಗಳ ಗುಂಪನ್ನು ಡಿ = {-1,0, + 1} ನಿಂದ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. δ, ಸೀಮಿತ ನಿಯಂತ್ರಣವು, Q × β '× (β' β [β], []]) ನಿಂದ Q × D × ([β * βD) ನ ಸೀಮಿತ ಉಪಗುಂಪುಗಳಾಗಿ ಮ್ಯಾಪಿಂಗ್ ಆಗಿದೆ, ಅಂದರೆ β ಅನೌಪಚಾರಿಕವಾಗಿ ಮ್ಯಾಪ್ ಮಾಡುತ್ತದೆ, (ಉಪ) ಸ್ಟ್ಯಾಕ್ನ ಮೇಲಿನ ಚಿಹ್ನೆಯನ್ನು ಅದರ ಹಿಂದಿನ ಎಡ ಎಂಡ್ಮಾರ್ಕರ್ನೊಂದಿಗೆ ಒಂದೇ ಚಿಹ್ನೆಯಾಗಿ ನೋಡಲಾಗುತ್ತದೆ; ನಂತರ δ ಪ್ರಸ್ತುತ ಸ್ಥಿತಿ, ಪ್ರಸ್ತುತ ಇನ್ಪುಟ್ ಚಿಹ್ನೆ ಮತ್ತು ಪ್ರಸ್ತುತ ಸ್ಟ್ಯಾಕ್ ಚಿಹ್ನೆಯನ್ನು ಓದುತ್ತದೆ ಮತ್ತು ಮುಂದಿನ ಸ್ಥಿತಿಯನ್ನು, ಇನ್ಪುಟ್ ಮೇಲೆ ಚಲಿಸುವ ದಿಕ್ಕನ್ನು ಮತ್ತು ಸ್ಟ್ಯಾಕ್ ಮೇಲೆ ಚಲಿಸುವ ದಿಕ್ಕನ್ನು ಅಥವಾ ಮೇಲಿನ ಸ್ಟ್ಯಾಕ್ ಚಿಹ್ನೆಯನ್ನು ಬದಲಿಸಲು ಚಿಹ್ನೆಗಳ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಔಟ್ಪುಟ್ ಮಾಡುತ್ತದೆ. q0 ωQ ಆರಂಭಿಕ ಸ್ಥಿತಿಯಾಗಿದೆ, Z0 ω ω ಆರಂಭಿಕ ಸ್ಟ್ಯಾಕ್ ಸಂಕೇತವಾಗಿದೆ, FωQ ಅಂತಿಮ ಸ್ಥಿತಿಗಳ ಗುಂಪಾಗಿದೆ. ಸಂರಚನೆಯು ಒಂದು ಸಂರಚನೆ, ಅಥವಾ ಅಂತಹ ಸ್ವಯಂಚಾಲಿತ ಯಂತ್ರದ ತತ್ಕ್ಷಣದ ವಿವರಣೆಯು ತ್ರಿವಳಿಗಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ, ಅಲ್ಲಿ q ωQ ಪ್ರಸ್ತುತ ಸ್ಥಿತಿಯಾಗಿದೆ, [a1a2.ai.an-1] ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ ಆಗಿದೆ; ಅನುಕೂಲಕ್ಕಾಗಿ, a0 = [ಮತ್ತು an =] ಅನ್ನು ಇನ್ಪುಟ್ನಲ್ಲಿನ ಪ್ರಸ್ತುತ ಸ್ಥಾನವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ, ಅಂದರೆ. 0 ≤ i ≤ n ಹೊಂದಿರುವ i ಅನ್ನು ಆಯಾ ಚಿಹ್ನೆಯನ್ನು ಒತ್ತಿಹೇಳುವ ಮೂಲಕ ಗುರುತಿಸಲಾಗುತ್ತದೆ. [Z1X2.Xj.Xm-1] ಎಂಬುದು ಸಬ್ಸ್ಟ್ಯಾಕ್ಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಸ್ಟ್ಯಾಕ್ ಆಗಿದೆ; ಅನುಕೂಲಕ್ಕಾಗಿ, X1 = [[Z1 ಮತ್ತು Xm =] ಅನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಸ್ಟಾಕ್ನಲ್ಲಿನ ಪ್ರಸ್ತುತ ಸ್ಥಾನ, ಅಂದರೆ. 1 ≤ j ≤ m ನೊಂದಿಗೆ, ಆಯಾ ಚಿಹ್ನೆಯನ್ನು ಒತ್ತಿಹೇಳುವ ಮೂಲಕ ಗುರುತಿಸಲಾಗುತ್ತದೆ. ಉದಾಹರಣೆ ಒಂದು ಉದಾಹರಣೆ ರನ್ (ಇನ್ಪುಟ್ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ತೋರಿಸಲಾಗಿಲ್ಲ): ಗುಣಲಕ್ಷಣಗಳು ಸ್ವಯಂಚಾಲಿತವಾಗಿ ತಮ್ಮ ಇನ್ಪುಟ್ ಅನ್ನು ಮರು-ಓದಲು ಅನುಮತಿಸಿದಾಗ ("ದ್ವಿಮುಖ ಸ್ವಯಂಚಾಲಿತ"), ಸರಳ ಸ್ಟ್ಯಾಕ್ಗಳಿಗೆ ಹೋಲಿಸಿದರೆ ನೆಸ್ಟೆಡ್ ಸ್ಟ್ಯಾಕ್ಗಳು ಹೆಚ್ಚುವರಿ ಭಾಷಾ ಗುರುತಿಸುವಿಕೆ ಸಾಮರ್ಥ್ಯಗಳಿಗೆ ಕಾರಣವಾಗುವುದಿಲ್ಲ. ಗಿಲ್ಮನ್ ಮತ್ತು ಶಪಿರೊ ಕೆಲವು ಗುಂಪುಗಳಲ್ಲಿ ಸಮಸ್ಯೆ ಎಂಬ ಪದವನ್ನು ಪರಿಹರಿಸಲು ನೆಸ್ಟೆಡ್ ಸ್ಟ್ಯಾಕ್ ಆಟೋಮಾಟಾವನ್ನು ಬಳಸಿದರು. ಟಿಪ್ಪಣಿಗಳು ಉಲ್ಲೇಖಗಳು ಗಣನೆಯ ಮಾದರಿಗಳು ಸ್ವಯಂಚಾಲಿತ (ಗಣನೆ)