Omega language
ಸೈದ್ಧಾಂತಿಕ ಗಣಕಯಂತ್ರ ವಿಜ್ಞಾನದ ಔಪಚಾರಿಕ ಭಾಷಾ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಅನಂತ ಪದವು ಅನಂತ-ಉದ್ದದ ಚಿಹ್ನೆಗಳ ಅನುಕ್ರಮವಾಗಿದೆ (ನಿರ್ದಿಷ್ಟವಾಗಿ, ω-ಉದ್ದದ ಅನುಕ್ರಮ), ಮತ್ತು ω-ಭಾಷೆಯು ಅನಂತ ಪದಗಳ ಸಮೂಹವಾಗಿದೆ. ಇಲ್ಲಿ, ω ಮೊದಲ ಕ್ರಮಬದ್ಧ ಸಂಖ್ಯೆಯನ್ನು, ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆಗಳ ಗುಂಪನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಔಪಚಾರಿಕ ವ್ಯಾಖ್ಯಾನವು ಸಂಕೇತಗಳ ಒಂದು ಗುಂಪಾಗಿರಲಿ (ಅಗತ್ಯವಾಗಿ ಸೀಮಿತವಾಗಿಲ್ಲ). ಔಪಚಾರಿಕ ಭಾಷಾ ಸಿದ್ಧಾಂತದ ಪ್ರಮಾಣಿತ ವ್ಯಾಖ್ಯಾನವನ್ನು ಅನುಸರಿಸಿ, σ * ಎಂಬುದು σ ಮೇಲಿನ ಎಲ್ಲಾ ಸೀಮಿತ ಪದಗಳ ಗುಂಪಾಗಿದೆ. ಪ್ರತಿ ಸೀಮಿತ ಪದವು ಒಂದು ಉದ್ದವನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಅದು ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆಯಾಗಿದೆ. n ಉದ್ದದ ಪದವನ್ನು ನೀಡಿದರೆ, w ಅನ್ನು {0,1,., n − 1} → ‡ ಗುಂಪಿನಿಂದ ಒಂದು ಕಾರ್ಯವಾಗಿ ನೋಡಬಹುದು, i ನಲ್ಲಿನ ಮೌಲ್ಯವು i ಸ್ಥಾನದಲ್ಲಿ ಚಿಹ್ನೆಯನ್ನು ನೀಡುತ್ತದೆ. ಅಂತ್ಯವಿಲ್ಲದ ಪದಗಳು, ಅಥವಾ ω-ಪದಗಳನ್ನು, ಅದೇ ರೀತಿ ಕಾರ್ಯಗಳಾಗಿ ನೋಡಬಹುದು. ಎಲ್ಲಾ ಅನಂತ ಪದಗಳ ಗುಂಪನ್ನು  ನಿಷ್ಪತ್ತಿಯ ಮೇಲೆ  ನಿಷ್ಪತ್ತಿಯಾಗಿ ಸೂಚಿಸಲಾಗುತ್ತದೆ. ಎಲ್ಲಾ ಸೀಮಿತ ಮತ್ತು ಅನಂತ ಪದಗಳ ಗುಂಪನ್ನು ಕೆಲವೊಮ್ಮೆ  ನಿಷ್ಪತ್ತಿಯಾದ ಮೇಲೆ  ನಿಷ್ಪತ್ತಿಯಾದ ಅಥವಾ  ನಿಷ್ಪತ್ತಿಯಾದ ಎಂದು ಬರೆಯಲಾಗುತ್ತದೆ. ಹೀಗಾಗಿ ω-ಭಾಷೆಯ L ಓವರ್ σ ಎಂಬುದು σωದ ಉಪವಿಭಾಗವಾಗಿದೆ. ಕಾರ್ಯಾಚರಣೆಗಳು ω-ಭಾಷೆಗಳಲ್ಲಿ ವ್ಯಾಖ್ಯಾನಿಸಲಾದ ಕೆಲವು ಸಾಮಾನ್ಯ ಕಾರ್ಯಾಚರಣೆಗಳೆಂದರೆಃ ಇಂಟರ್ಸೆಕ್ಷನ್ ಮತ್ತು ಯೂನಿಯನ್ ನೀಡಲಾಗಿದೆ ω-ಭಾಷೆಗಳು L ಮತ್ತು M, ಎರಡೂ ω-ಭಾಷೆಗಳಾಗಿವೆ. ಎಡ ಸಂಯೋಜನೆ ಎಲ್ ಒಂದು ω-ಭಾಷೆಯಾಗಿರಲಿ, ಮತ್ತು ಕೆ ಸೀಮಿತ ಪದಗಳ ಭಾಷೆಯಾಗಿರಲಿ. ನಂತರ ಹೊಸ ω-ಭಾಷೆಯ KL ಅನ್ನು ನೀಡಲು K ಅನ್ನು ಎಡಭಾಗದಲ್ಲಿ ಮತ್ತು ಎಡಭಾಗದಲ್ಲಿ ಮಾತ್ರ L ಗೆ ಸಂಯೋಜಿಸಬಹುದು. ಒಮೆಗಾ (ಅನಂತ ಪುನರಾವರ್ತನೆ) ಸಂಕೇತವು ಸೂಚಿಸುವಂತೆ, ಕಾರ್ಯಾಚರಣೆಯು ಸೀಮಿತ-ಉದ್ದದ ಭಾಷೆಗಳಲ್ಲಿ ಕ್ಲೈನ್ ಸ್ಟಾರ್ ಆಪರೇಟರ್ನ ಅನಂತ ಆವೃತ್ತಿಯಾಗಿದೆ. ಔಪಚಾರಿಕ ಭಾಷೆಯಾದ ಎಲ್ ಅನ್ನು ನೀಡಿದರೆ, ಎಲ್ ನಿಂದ ಪದಗಳ ಎಲ್ಲಾ ಅನಂತ ಅನುಕ್ರಮಗಳ ω-ಭಾಷೆಯಾಗಿದೆ; ಕ್ರಿಯಾತ್ಮಕ ದೃಷ್ಟಿಕೋನದಲ್ಲಿ, ಎಲ್ಲಾ ಕಾರ್ಯಗಳ. ಪೂರ್ವಪ್ರತ್ಯಯಗಳು w ಒಂದು ω-ಪದವಾಗಿರಲಿ. ನಂತರ ಔಪಚಾರಿಕ ಭಾಷೆಯಾದ ಪ್ರಿಫ್ (ಡಬ್ಲ್ಯೂ) ಯು ಡಬ್ಲ್ಯೂ ನ ಪ್ರತಿ ಸೀಮಿತ ಪೂರ್ವಪ್ರತ್ಯಯವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಮಿತಿಯನ್ನು ಒಂದು ಸೀಮಿತ-ಉದ್ದದ ಭಾಷೆಯಾದ ಎಲ್ ಅನ್ನು ನೀಡಿದರೆ, ಅನಂತ ಗುಂಪಾಗಿದ್ದರೆ ಮಾತ್ರ ω-ಪದ ಡಬ್ಲ್ಯೂ ಎಲ್ ಮಿತಿಯಲ್ಲಿರುತ್ತದೆ. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ಅನಿಯಂತ್ರಿತವಾಗಿ ದೊಡ್ಡ ನೈಸರ್ಗಿಕ ಸಂಖ್ಯೆ n ಗೆ, L ನಲ್ಲಿ ಕೆಲವು ಪದಗಳನ್ನು ಆಯ್ಕೆ ಮಾಡಲು ಯಾವಾಗಲೂ ಸಾಧ್ಯವಿದೆ, ಅದರ ಉದ್ದವು n ಗಿಂತ ಹೆಚ್ಚಾಗಿರುತ್ತದೆ ಮತ್ತು ಇದು w ನ ಪೂರ್ವಪ್ರತ್ಯಯವಾಗಿದೆ. L ನಲ್ಲಿನ ಮಿತಿ ಕಾರ್ಯಾಚರಣೆಯನ್ನು Lδ ಅಥವಾ ಎಂದು ಬರೆಯಬಹುದು. ω-ಪದಗಳ ನಡುವಿನ ಅಂತರ ಗಣವನ್ನು ಮೆಟ್ರಿಕ್ ವ್ಯಾಖ್ಯಾನದ ಮೂಲಕ ಮೆಟ್ರಿಕ್ ಸ್ಪೇಸ್ ಆಗಿ ಮಾಡಬಹುದುಃ ಅಲ್ಲಿ |x | ಅನ್ನು "x ನ ಉದ್ದ" (x ನಲ್ಲಿನ ಚಿಹ್ನೆಗಳ ಸಂಖ್ಯೆ) ಎಂದು ಅರ್ಥೈಸಲಾಗುತ್ತದೆ, ಮತ್ತು inf ಎಂಬುದು ನೈಜ ಸಂಖ್ಯೆಗಳ ಸೆಟ್ಗಳ ಮೇಲೆ ಅನಂತವಾಗಿದೆ. ಹಾಗಿದ್ದಲ್ಲಿ, ಯಾವುದೇ ದೀರ್ಘವಾದ ಪೂರ್ವಪ್ರತ್ಯಯ x ಮತ್ತು ಹೀಗೆ ಇರುವುದಿಲ್ಲ. ಸಮನ್ವಯವು ಸ್ಪಷ್ಟವಾಗಿದೆ. ಡಬ್ಲ್ಯೂ ಮತ್ತು ವಿ ಉದ್ದದ m ಮತ್ತು v ನ ಗರಿಷ್ಠ ಹಂಚಿಕೆಯ ಪೂರ್ವಪ್ರತ್ಯಯವನ್ನು ಹೊಂದಿದ್ದರೆ ಮತ್ತು ಯು ಉದ್ದದ n ನ ಗರಿಷ್ಠ ಹಂಚಿಕೆಯ ಪೂರ್ವಪ್ರತ್ಯಯವನ್ನು ಹೊಂದಿದ್ದರೆ, ಡಬ್ಲ್ಯೂ ಮತ್ತು ಯು ನ ಮೊದಲ ಅಕ್ಷರಗಳು ಒಂದೇ ಆಗಿರಬೇಕು ಎಂಬ ಅಂಶದಿಂದ ಟ್ರಾನ್ಸಿಟಿವಿಟಿ ಅನುಸರಿಸುತ್ತದೆ. ಆದ್ದರಿಂದ ಡಿ ಒಂದು ಮೆಟ್ರಿಕ್ ಆಗಿದೆ. ಪ್ರಮುಖ ಉಪವರ್ಗಗಳು ω-ಭಾಷೆಗಳ ಅತ್ಯಂತ ವ್ಯಾಪಕವಾಗಿ ಬಳಸಲಾಗುವ ಉಪವರ್ಗವು ω-ನಿಯಮಿತ ಭಾಷೆಗಳ ಗುಂಪಾಗಿದೆ, ಇದು ಬುಚಿ ಆಟೋಮಾಟಾದಿಂದ ಗುರುತಿಸಬಹುದಾದ ಉಪಯುಕ್ತ ಗುಣವನ್ನು ಹೊಂದಿದೆ. ಹೀಗಾಗಿ ω-ನಿಯಮಿತ ಭಾಷಾ ಸದಸ್ಯತ್ವದ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯು ಬುಚಿ ಸ್ವಯಂಚಾಲಿತವನ್ನು ಬಳಸಿಕೊಂಡು ನಿರ್ಧರಿಸಬಹುದಾದಂತಹದ್ದಾಗಿದೆ ಮತ್ತು ಗಣನೆಗೆ ತಕ್ಕಮಟ್ಟಿಗೆ ಸರಳವಾಗಿದೆ. ಭಾಷೆಯು ಒಂದು ಗುಂಪಿನ ಶಕ್ತಿಯ ಗುಂಪಾಗಿದ್ದರೆ ("ಪರಮಾಣು ಪ್ರಸ್ತಾಪಗಳು" ಎಂದು ಕರೆಯಲ್ಪಡುತ್ತದೆ) ಆಗ ω-ಭಾಷೆಯು ರೇಖೀಯ ಸಮಯದ ಗುಣಲಕ್ಷಣವಾಗಿದೆ, ಇದನ್ನು ಮಾದರಿ ಪರಿಶೀಲನೆಯಲ್ಲಿ ಅಧ್ಯಯನ ಮಾಡಲಾಗುತ್ತದೆ. ಗ್ರಂಥಸೂಚಿ ಪೆರ್ರಿನ್, ಡಿ. ಮತ್ತು ಪಿನ್, ಜೆ. ಇ. "ಇನ್ಫೈನೈಟ್ ವರ್ಡ್ಸ್ಃ ಆಟೋಮ್ಯಾಟಾ, ಸೆಮಿಗ್ರೂಪ್ಗಳು, ಲಾಜಿಕ್ ಮತ್ತು ಗೇಮ್ಸ್". ಶುದ್ಧ ಮತ್ತು ಅನ್ವಯಿಕ ಗಣಿತ ಸಂಪುಟ 141, ಎಲ್ಸೆವಿಯರ್, 2004. ಸ್ಟೈಗರ್, ಎಲ್. "ω-ಭಾಷೆಗಳು". ಜಿ. ರೋಜೆನ್ಬರ್ಗ್ ಮತ್ತು ಎ. ಸಲೋಮಾ, ಸಂಪಾದಕರು, ಹ್ಯಾಂಡ್ಬುಕ್ ಆಫ್ ಫಾರ್ಮಲ್ ಲಾಂಗ್ವೇಜಸ್, ಸಂಪುಟ 3, ಪುಟಗಳು 339-387. ಸ್ಪ್ರಿಂಗರ್-ವೆರ್ಲಾಗ್, ಬರ್ಲಿನ್, 1997. ಥಾಮಸ್, ಡಬ್ಲ್ಯೂ. "ಆಟೋಮ್ಯಾಟಾ ಆನ್ ಇನ್ಫೈನೈಟ್ ಆಬ್ಜೆಕ್ಟ್ಸ್". ಹ್ಯಾಂಡ್ಬುಕ್ ಆಫ್ ಥಿಯೊರೆಟಿಕಲ್ ಕಂಪ್ಯೂಟರ್ ಸೈನ್ಸ್ನ ಸಂಪಾದಕ ಜಾನ್ ವ್ಯಾನ್ ಲೀಯುವೆನ್, ಸಂಪುಟ ಬಿಃ ಫಾರ್ಮಲ್ ಮಾಡೆಲ್ಸ್ ಅಂಡ್ ಸೆಮಾಂಟಿಕ್ಸ್, ಪುಟಗಳು 133-192. ಎಲ್ಸೆವಿಯರ್ ಸೈನ್ಸ್ ಪಬ್ಲಿಷರ್ಸ್, ಆಮ್ಸ್ಟರ್ಡ್ಯಾಮ್, 1990. ಗಣನೆಯ ಸಿದ್ಧಾಂತ ಔಪಚಾರಿಕ ಭಾಷೆಗಳು