Omega-regular language
ω-ನಿಯಮಿತ ಭಾಷೆಗಳು ω-ಭಾಷೆಗಳ ಒಂದು ವರ್ಗವಾಗಿದ್ದು, ಸಾಮಾನ್ಯ ಭಾಷೆಗಳ ವ್ಯಾಖ್ಯಾನವನ್ನು ಅನಂತ ಪದಗಳಿಗೆ ಸಾಮಾನ್ಯೀಕರಿಸುತ್ತವೆ. ಔಪಚಾರಿಕ ವ್ಯಾಖ್ಯಾನ ಒಂದು ω-ಭಾಷೆಯ L ಯು Aω ರೂಪವನ್ನು ಹೊಂದಿದ್ದರೆ ಅದು ω-ನಿಯಮಿತವಾಗಿರುತ್ತದೆ, ಅಲ್ಲಿ A ಎಂಬುದು ಖಾಲಿ ಸ್ಟ್ರಿಂಗ್ AB ಅನ್ನು ಹೊಂದಿರದ ಸಾಮಾನ್ಯ ಭಾಷೆಯಾಗಿದೆ, ಸಾಮಾನ್ಯ ಭಾಷೆಯ A ಮತ್ತು ω-ನಿಯಮಿತ ಭಾಷೆಯ B (BA ಅನ್ನು ಚೆನ್ನಾಗಿ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿಲ್ಲ ಎಂಬುದನ್ನು ಗಮನಿಸಿ) A ≤ B ಅಲ್ಲಿ A ಮತ್ತು B ಗಳು ω-ನಿಯಮಿತ ಭಾಷೆಗಳಾಗಿವೆ (ಈ ನಿಯಮವನ್ನು ಸೀಮಿತವಾಗಿ ಅನೇಕ ಬಾರಿ ಮಾತ್ರ ಅನ್ವಯಿಸಬಹುದು) A ನಿಂದ ಪದಗಳನ್ನು ಅನಂತವಾಗಿ ಅನೇಕ ಬಾರಿ ಸಂಯೋಜಿಸುವ ಮೂಲಕ Aω ನ ಅಂಶಗಳನ್ನು ಪಡೆಯಲಾಗುತ್ತದೆ. ಎ ನಿಯಮಿತವಾಗಿದ್ದರೆ, ಎ ω-ನಿಯಮಿತವಾಗಿರಬೇಕಾಗಿಲ್ಲ ಎಂಬುದನ್ನು ಗಮನಿಸಿ, ಏಕೆಂದರೆ ಎ ಉದಾಹರಣೆಗೆ {ε} ಆಗಿರಬಹುದು, ಖಾಲಿ ಸ್ಟ್ರಿಂಗ್ ಅನ್ನು ಮಾತ್ರ ಹೊಂದಿರುವ ಸೆಟ್, ಈ ಸಂದರ್ಭದಲ್ಲಿ ಎ ω = ಎ, ಇದು ω-ಭಾಷೆಯಲ್ಲ ಮತ್ತು ಆದ್ದರಿಂದ ω-ನಿಯಮಿತ ಭಾಷೆಯಲ್ಲ. ಇದು ω-ನಿಯಮಿತ ಭಾಷೆಗಳು ನಿಖರವಾಗಿ A1B1ω ರೂಪದ ω-ಭಾಷೆಗಳಾಗಿವೆ ಎಂಬ ವ್ಯಾಖ್ಯಾನದ ನೇರವಾದ ಪರಿಣಾಮವಾಗಿದೆ. ಬುಚಿ ಸ್ವಯಂಚಾಲಿತ ಪ್ರಮೇಯಕ್ಕೆ ಸಮಾನತೆಃ ಒಂದು ω-ಭಾಷೆಯು ω-ನಿಯಮಿತ ಭಾಷೆಯಾಗಿದ್ದರೆ ಮಾತ್ರ ಅದನ್ನು ಬುಚಿ ಸ್ವಯಂಚಾಲಿತತೆಯಿಂದ ಗುರುತಿಸಲಾಗುತ್ತದೆ. ಪುರಾವೆಃ ಪ್ರತಿ ω-ನಿಯಮಿತ ಭಾಷೆಯನ್ನು ಅನಿರ್ಧಾರಣೀಯ ಬುಚಿ ಸ್ವಯಂಚಾಲಿತತೆಯಿಂದ ಗುರುತಿಸಲಾಗಿದೆ; ಅನುವಾದವು ರಚನಾತ್ಮಕವಾಗಿದೆ. ω-ನಿಯಮಿತ ಭಾಷೆಯ ವ್ಯಾಖ್ಯಾನದ ಮೇಲೆ ಬುಚಿ ಆಟೋಮಾಟಾದ ಮುಚ್ಚುವ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಮತ್ತು ರಚನಾತ್ಮಕ ಪ್ರಚೋದನೆಯನ್ನು ಬಳಸಿಕೊಂಡು, ಯಾವುದೇ ನಿರ್ದಿಷ್ಟ ω-ನಿಯಮಿತ ಭಾಷೆಗೆ ಬುಚಿ ಆಟೋಮೇಟನ್ ಅನ್ನು ನಿರ್ಮಿಸಬಹುದು ಎಂದು ಸುಲಭವಾಗಿ ತೋರಿಸಬಹುದು. ಇದಕ್ಕೆ ವಿರುದ್ಧವಾಗಿ, ಕೊಟ್ಟಿರುವ ಬುಚಿ ಸ್ವಯಂಚಾಲಿತಕ್ಕೆ, ನಾವು ω-ನಿಯಮಿತ ಭಾಷೆಯನ್ನು ನಿರ್ಮಿಸುತ್ತೇವೆ ಮತ್ತು ನಂತರ ಈ ಭಾಷೆಯನ್ನು A ಗುರುತಿಸಿದೆ ಎಂದು ನಾವು ತೋರಿಸುತ್ತೇವೆ. ಒಂದು ω-ಪದಕ್ಕೆ ಡಬ್ಲ್ಯೂ = ಎ1ಎ2. ಡಬ್ಲ್ಯೂ (ಐ, ಜೆ) ಯು ಡಬ್ಲ್ಯೂ ನ ಸೀಮಿತ ವಿಭಾಗವಾದ ಎಐ + 1.aj-1aj ಆಗಿರಲಿ. ಪ್ರತಿಯೊಂದಕ್ಕೂ, ನಾವು ಸೀಮಿತ ಸ್ವಯಂಚಾಲಿತತೆಯಿಂದ ಸ್ವೀಕರಿಸಲ್ಪಟ್ಟ ಸಾಮಾನ್ಯ ಭಾಷೆ ಎಲ್ ಕ್ಯೂ, ಕ್ಯೂ 'ಅನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುತ್ತೇವೆ. ಲೆಮ್ಮಾಃ ಬುಚಿ ಆಟೋಮ್ಯಾಟನ್ ಎ ಭಾಷೆಯ ಪುರಾವೆಯನ್ನು ಗುರುತಿಸುತ್ತದೆ ಎಂದು ನಾವು ಹೇಳಿಕೊಳ್ಳುತ್ತೇವೆಃ ಪದ ಮತ್ತು q0, q1, q2,. ಇದು a ಅನ್ನು w ಮೇಲೆ ಸ್ವೀಕರಿಸುವ ರನ್ ಎಂದು ಭಾವಿಸೋಣ. ಆದ್ದರಿಂದ, q0 ಒಳಗೆ ಇದೆ ಮತ್ತು ಸ್ವೀಕರಿಸುವ ಓಟದಲ್ಲಿ ಅನಂತವಾಗಿ ಆಗಾಗ್ಗೆ ಸಂಭವಿಸುವಂತಹ ಸ್ಥಿತಿಯು F ನಲ್ಲಿ ಇರಬೇಕು. i0, i1, i2 ಸೂಚ್ಯಂಕಗಳ ಕಟ್ಟುನಿಟ್ಟಾಗಿ ಹೆಚ್ಚುತ್ತಿರುವ ಅನಂತ ಅನುಕ್ರಮವನ್ನು ಆರಿಸೋಣ. ಅಂದರೆ, ಎಲ್ಲಾ k ≤0 ಗೆ. ಆದ್ದರಿಂದ, ಮತ್ತು, ಎಲ್ಲರಿಗೂ, ಆದ್ದರಿಂದ, ಇದಕ್ಕೆ ವಿರುದ್ಧವಾಗಿ, ಕೆಲವರಿಗೆ ಭಾವಿಸೋಣ ಮತ್ತು ಆದ್ದರಿಂದ, ಅನಂತ ಮತ್ತು ಕಟ್ಟುನಿಟ್ಟಾಗಿ ಹೆಚ್ಚುತ್ತಿರುವ ಅನುಕ್ರಮ i0, i1, i2 ಇದೆ. ಅಂದರೆ ಮತ್ತು, ಎಲ್ಲರಿಗೂ Lq, q 'ನ ವ್ಯಾಖ್ಯಾನದ ಪ್ರಕಾರ, ಪದದಿಂದ ಪದಕ್ಕೆ ಒಂದು ಸೀಮಿತ ರನ್ ಇದೆ (0, i0). ಎಲ್ಲಾ k ≤ 0 ಗೆ, ಪದದಿಂದ ಪದಕ್ಕೆ ಸೀಮಿತ ರನ್ ಇರುತ್ತದೆ (ik, ik + 1). ಈ ರಚನೆಯಿಂದ, ಎ ನ ಒಂದು ಓಟವಿದೆ, ಇದು ಅನಂತವಾಗಿ ಆಗಾಗ್ಗೆ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ ಮತ್ತು ಸಂಭವಿಸುತ್ತದೆ. ಆದ್ದರಿಂದ,. ಮೊನಾಡಿಕ್ ಎರಡನೇ-ಕ್ರಮಾಂಕದ ತರ್ಕಕ್ಕೆ ಸಮಾನವಾದ ಬುಚಿ 1962 ರಲ್ಲಿ ω-ನಿಯಮಿತ ಭಾಷೆಗಳು ನಿಖರವಾಗಿ S1S ಎಂಬ ನಿರ್ದಿಷ್ಟ ಮೊನಾಡಿಕ್ ಎರಡನೇ-ಕ್ರಮಾಂಕದ ತರ್ಕದಲ್ಲಿ ವ್ಯಾಖ್ಯಾನಿಸಬಹುದಾದವು ಎಂದು ತೋರಿಸಿದೆ. ಗ್ರಂಥಸೂಚಿ ವೋಲ್ಫ್ಗ್ಯಾಂಗ್ ಥಾಮಸ್, "ಅನಂತ ವಸ್ತುಗಳ ಮೇಲೆ ಆಟೋಮ್ಯಾಟಾ". ಹ್ಯಾಂಡ್ಬುಕ್ ಆಫ್ ಥಿಯೊರೆಟಿಕಲ್ ಕಂಪ್ಯೂಟರ್ ಸೈನ್ಸ್ನ ಸಂಪಾದಕ ಜಾನ್ ವ್ಯಾನ್ ಲೀಯುವೆನ್, ಸಂಪುಟ ಬಿಃ ಫಾರ್ಮಲ್ ಮಾಡೆಲ್ಸ್ ಅಂಡ್ ಸೆಮಾಂಟಿಕ್ಸ್, ಪುಟಗಳು 133-192. ಎಲ್ಸೆವಿಯರ್ ಸೈನ್ಸ್ ಪಬ್ಲಿಷರ್ಸ್, ಆಮ್ಸ್ಟರ್ಡ್ಯಾಮ್, 1990. ಔಪಚಾರಿಕ ಭಾಷೆಗಳು