Equivalence (formal languages)
ಔಪಚಾರಿಕ ಭಾಷಾ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಎರಡು ವ್ಯಾಕರಣಗಳ ದುರ್ಬಲ ಸಮಾನತೆ ಎಂದರೆ ಅವು ಒಂದೇ ರೀತಿಯ ತಂತಿಗಳನ್ನು ಉತ್ಪಾದಿಸುತ್ತವೆ, ಅಂದರೆ. ಅವರು ಸೃಷ್ಟಿಸುವ ಔಪಚಾರಿಕ ಭಾಷೆಯು ಒಂದೇ ಆಗಿರುತ್ತದೆ. ಕಂಪೈಲರ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಈ ಕಲ್ಪನೆಯನ್ನು ಬಲವಾದ (ಅಥವಾ ರಚನಾತ್ಮಕ) ಸಮಾನತೆಯಿಂದ ಪ್ರತ್ಯೇಕಿಸಲಾಗಿದೆ, ಇದರರ್ಥ ಹೆಚ್ಚುವರಿಯಾಗಿ ಎರಡು ಪಾರ್ಸ್ ಮರಗಳು ಸಮಂಜಸವಾಗಿ ಹೋಲುತ್ತವೆ, ಏಕೆಂದರೆ ಒಂದೇ ಶಬ್ದಾರ್ಥದ ವ್ಯಾಖ್ಯಾನವನ್ನು ಎರಡಕ್ಕೂ ನಿಯೋಜಿಸಬಹುದು. ವಿಜಯ್-ಶಂಕರ್ ಮತ್ತು ವೀರ್ (1994) ಅವರು ರೇಖೀಯ ಸೂಚ್ಯಂಕದ ವ್ಯಾಕರಣಗಳು, ಸಂಯೋಜಿತ ವರ್ಗದ ವ್ಯಾಕರಣಗಳು, ಮರಕ್ಕೆ ಹೊಂದಿಕೊಂಡಿರುವ ವ್ಯಾಕರಣಗಳು ಮತ್ತು ಮುಖ್ಯ ವ್ಯಾಕರಣಗಳು ದುರ್ಬಲವಾಗಿ ಸಮಾನವಾದ ಔಪಚಾರಿಕತೆಗಳಾಗಿವೆ ಎಂದು ತೋರಿಸುತ್ತವೆ, ಏಕೆಂದರೆ ಅವೆಲ್ಲವೂ ಒಂದೇ ಸ್ಟ್ರಿಂಗ್ ಭಾಷೆಗಳನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುತ್ತವೆ. ಮತ್ತೊಂದೆಡೆ, ಎರಡು ವ್ಯಾಕರಣಗಳು ಒಂದೇ ರೀತಿಯ ವ್ಯುತ್ಪತ್ತಿ ಮರಗಳನ್ನು ಉತ್ಪಾದಿಸಿದರೆ (ಅಥವಾ ಹೆಚ್ಚು ಸಾಮಾನ್ಯವಾಗಿ, ಒಂದೇ ರೀತಿಯ ಅಮೂರ್ತ ವಾಕ್ಯರಚನೆಯ ವಸ್ತುಗಳು), ಆಗ ಎರಡು ವ್ಯಾಕರಣಗಳು ಬಲವಾಗಿ ಸಮಾನವಾಗಿರುತ್ತವೆ. ಚೋಮ್ಸ್ಕಿ (1963) ಬಲವಾದ ಸಮಾನತೆಯ ಕಲ್ಪನೆಯನ್ನು ಪರಿಚಯಿಸುತ್ತಾರೆ ಮತ್ತು ವ್ಯಾಕರಣದ ಔಪಚಾರಿಕತೆಗಳನ್ನು ಹೋಲಿಸುವಾಗ ಬಲವಾದ ಸಮಾನತೆಯು ಮಾತ್ರ ಪ್ರಸ್ತುತವಾಗಿದೆ ಎಂದು ವಾದಿಸುತ್ತಾರೆ. ಕೊರ್ನೈ ಮತ್ತು ಪುಲ್ಲಮ್ (1990) ಮತ್ತು ಮಿಲ್ಲರ್ (1994) ಬಲವಾದ ಸಮಾನತೆಯ ಪರಿಷ್ಕೃತ ಕಲ್ಪನೆಯನ್ನು ನೀಡುತ್ತವೆ, ಇದು ವಿಭಿನ್ನ ಔಪಚಾರಿಕತೆಗಳಿಂದ ನೀಡಲಾದ ವಾಕ್ಯರಚನೆಯ ವಿಶ್ಲೇಷಣೆಗಳ ನಡುವಿನ ಐಸೊಮಾರ್ಫಿಕ್ ಸಂಬಂಧಗಳನ್ನು ಅನುಮತಿಸುತ್ತದೆ. ಯೋಶಿನಾಗಾ, ಮಿಯಾವೊ, ಮತ್ತು ತ್ಸುಜಿ (2002) ಯಾವುದೇ ಎಲ್. ಟಿ. ಎ. ಜಿ ಔಪಚಾರಿಕತೆಗೆ ಬಲವಾಗಿ ಸಮಾನವಾದ ಎಚ್. ಪಿ. ಎಸ್. ಜಿ ಇದೆ ಎಂಬುದಕ್ಕೆ ಪುರಾವೆಯನ್ನು ನೀಡುತ್ತದೆ. ಸಂದರ್ಭ-ಮುಕ್ತ ವ್ಯಾಕರಣದ ಉದಾಹರಣೆ ಒಂದು ಉದಾಹರಣೆಯಾಗಿ, ಬ್ಯಾಕಸ್-ನೌರ್ ರೂಪದಲ್ಲಿ ನೀಡಲಾದ ಈ ಕೆಳಗಿನ ಎರಡು ಸಂದರ್ಭ-ಮುಕ್ತ ವ್ಯಾಕರಣಗಳನ್ನು ಪರಿಗಣಿಸಿಃ <ಅಭಿವ್ಯಕ್ತಿ>:: = <ಅಭಿವ್ಯಕ್ತಿ> + "<ಅಭಿವ್ಯಕ್ತಿ> | <ಅಭಿವ್ಯಕ್ತಿ>-" <ಅಭಿವ್ಯಕ್ತಿ> | <ಅಭಿವ್ಯಕ್ತಿ> "*" <ಅಭಿವ್ಯಕ್ತಿ> | <ಅಭಿವ್ಯಕ್ತಿ> | "x" | "y" | "z" | "1" | "2" | "3" | "(" <ಅಭಿವ್ಯಕ್ತಿ> ")" <ಅಭಿವ್ಯಕ್ತಿ>:: = <ಪದ> | <ಅಭಿವ್ಯಕ್ತಿ> "+" <ಪದ> | <ಅಭಿವ್ಯಕ್ತಿ>-"<ಪದ> <ಪದ>:: = <ಪದ> <ಪದ> "x", "y", "z", ಸ್ಥಿರಾಂಕಗಳು "1", "2", "3", ಆಪರೇಟರ್ಗಳು "+", "-", "*", "/", ಮತ್ತು ಆವರಣಗಳು "(" ಮತ್ತು ")" ಎಂಬ ಅಸ್ಥಿರಗಳಿಂದ ನಿರ್ಮಿಸಬಹುದಾದ ಎಲ್ಲಾ ಅಂಕಗಣಿತದ ಅಭಿವ್ಯಕ್ತಿಗಳ ಗುಂಪಾಗಿದೆ. ಆದಾಗ್ಯೂ, ಎರಡನೇ ವ್ಯಾಕರಣದ ಕಾಂಕ್ರೀಟ್ ವಾಕ್ಯರಚನೆಯು ಯಾವಾಗಲೂ ಕಾರ್ಯಾಚರಣೆಗಳ ಸಾಮಾನ್ಯ ಕ್ರಮವನ್ನು ಪ್ರತಿಬಿಂಬಿಸುತ್ತದೆ, ಆದರೆ ಮೊದಲ ವ್ಯಾಕರಣದ ಮರವು ಅಗತ್ಯವಿಲ್ಲ. ಉದಾಹರಣೆಗಾಗಿ ಸ್ಟ್ರಿಂಗ್ "1 + 2 * 3", ಚಿತ್ರದ ಬಲ ಭಾಗವು ಅದರ ವಿಶಿಷ್ಟ ಪಾರ್ಸ್ ಟ್ರೀ ಅನ್ನು ಎರಡನೇ ವ್ಯಾಕರಣದೊಂದಿಗೆ ತೋರಿಸುತ್ತದೆ; ಈ ಟ್ರೀ ಅನ್ನು ಪೋಸ್ಟ್ಫಿಕ್ಸ್ ಕ್ರಮದಲ್ಲಿ ಮೌಲ್ಯಮಾಪನ ಮಾಡುವುದರಿಂದ ಸರಿಯಾದ ಮೌಲ್ಯವನ್ನು ನೀಡುತ್ತದೆ, 7. ಇದಕ್ಕೆ ವ್ಯತಿರಿಕ್ತವಾಗಿ, ಎಡ ಚಿತ್ರದ ಭಾಗವು ಮೊದಲ ವ್ಯಾಕರಣದೊಂದಿಗೆ ಆ ಸ್ಟ್ರಿಂಗ್ಗಾಗಿ ಪಾರ್ಸ್ ಮರಗಳಲ್ಲಿ ಒಂದನ್ನು ತೋರಿಸುತ್ತದೆ; ಅದನ್ನು ಪೋಸ್ಟ್ಫಿಕ್ಸ್ ಕ್ರಮದಲ್ಲಿ ಮೌಲ್ಯಮಾಪನ ಮಾಡುವುದರಿಂದ 9 ದೊರೆಯುತ್ತದೆ. ಎರಡನೇ ವ್ಯಾಕರಣವು ಎಡ ಚಿತ್ರದ ಭಾಗಕ್ಕೆ ಅನುಗುಣವಾದ ಮರವನ್ನು ಉತ್ಪಾದಿಸಲು ಸಾಧ್ಯವಿಲ್ಲವಾದ್ದರಿಂದ, ಮೊದಲ ವ್ಯಾಕರಣವು ಮಾಡಬಹುದು, ಎರಡೂ ವ್ಯಾಕರಣಗಳು ಬಲವಾಗಿ ಸಮಾನವಾಗಿಲ್ಲ. ಭಾಷಾಶಾಸ್ತ್ರದಲ್ಲಿ, ವ್ಯಾಕರಣದ ದುರ್ಬಲ ಉತ್ಪಾದಕ ಸಾಮರ್ಥ್ಯವನ್ನು ಅದರಿಂದ ಉತ್ಪತ್ತಿಯಾಗುವ ಎಲ್ಲಾ ತಂತಿಗಳ ಸೆಟ್ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ, ಆದರೆ ವ್ಯಾಕರಣದ ಬಲವಾದ ಉತ್ಪಾದಕ ಸಾಮರ್ಥ್ಯವು ಅದರಿಂದ ಉತ್ಪತ್ತಿಯಾಗುವ "ರಚನಾತ್ಮಕ ವಿವರಣೆಗಳ" ಸೆಟ್ ಅನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಇದರ ಪರಿಣಾಮವಾಗಿ, ಎರಡು ವ್ಯಾಕರಣಗಳನ್ನು ಅವುಗಳ ದುರ್ಬಲ ಉತ್ಪಾದಕ ಸಾಮರ್ಥ್ಯಗಳು ಹೊಂದಿಕೆಯಾದರೆ ದುರ್ಬಲವಾಗಿ ಸಮಾನವೆಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ; ಬಲವಾದ ಸಮಾನತೆಗೆ ಹೋಲುತ್ತದೆ. ಉತ್ಪಾದಕ ಸಾಮರ್ಥ್ಯದ ಕಲ್ಪನೆಯನ್ನು 1963ರಲ್ಲಿ ನೋಮ್ ಚೋಮ್ಸ್ಕಿ ಪರಿಚಯಿಸಿದರು. ಟಿಪ್ಪಣಿಗಳ ಉಲ್ಲೇಖಗಳು ಔಪಚಾರಿಕ ಭಾಷೆಗಳು