परिमित अवस्था मशीन क्या है?
परिमित अवस्था मशीन (FSM), जिसे परिमित ऑटोमेटन भी कहते हैं, कंप्यूटर का एक सरल मॉडल है जिसकी कोई मेमोरी नहीं — बस यह याद रहता है कि वह किस अवस्था में है। इसमें होते हैं:
- अवस्थाओं का सीमित समूह (गोले)
- इनपुट वर्णमाला Σ: जिन चिह्नों को यह पढ़ सकती है, जैसे {सिक्का, धक्का} या {0, 1}
- एक आरंभ अवस्था (कहीं से न आता तीर)
- संक्रमण फलन δ: हर अवस्था और चिह्न के लिए अगली अवस्था
- स्वीकारक के लिए स्वीकार (अंतिम) अवस्थाएँ (दोहरे गोले)
मशीन इनपुट स्ट्रिंग बाएँ से दाएँ एक-एक चिह्न पढ़ती है। आख़िरी चिह्न के बाद अगर वह स्वीकार अवस्था में है, तो स्ट्रिंग स्वीकार; वरना अस्वीकार। ऐसी FSM हाँ/ना के अलावा कोई आउटपुट नहीं देती।
अगर हर अवस्था से हर चिह्न के लिए ठीक एक तीर हो, तो यह नियतात्मक FSM (DFA) है। अगर एक चिह्न के लिए कई तीर (या कोई नहीं) हो सकें, तो अनियतात्मक (NFA)। हर NFA को बराबर DFA में बदला जा सकता है।
अवस्था संक्रमण आरेख और तालिका
एक ही मशीन को आरेख में बना सकते हैं या तालिका में लिख सकते हैं।
| वर्तमान अवस्था | इनपुट | अगली अवस्था |
|---|---|---|
| बंद | सिक्का | खुला |
| बंद | धक्का | बंद |
| खुला | सिक्का | खुला |
| खुला | धक्का | बंद |
स्वीकारक का उदाहरण: अवस्थाएँ S0 (आरंभ, स्वीकार) और S1। वर्णमाला {0, 1}। 1 पढ़ने पर अवस्था बदलती है; 0 पर वही रहती है। यह मशीन ठीक वही बाइनरी स्ट्रिंग स्वीकार करती है जिनमें 1 की संख्या सम हो: 1001 → S0 (स्वीकार), 111 → S1 (अस्वीकार)।
आउटपुट वाली FSM: मीली मशीन
मीली मशीन हर संक्रमण पर आउटपुट देती है। हर तीर पर इनपुट / आउटपुट लिखा होता है। इसमें स्वीकार अवस्थाएँ नहीं होतीं; इसका काम इनपुट को आउटपुट में बदलना है।
उदाहरण: टर्नस्टाइल "खुलो" या "बीप" दे सकता है: बंद —सिक्का/खुलो→ खुला, बंद —धक्का/बीप→ बंद। एक और जाना-माना उदाहरण: जब इनपुट बिट पिछले बिट से अलग हो तो 1 देने वाली मशीन (एज डिटेक्टर)। मीली मशीनें ट्रैफ़िक लाइट नियंत्रक, वेंडिंग मशीन और सरल सिफ़र में काम आती हैं।
(मूर मशीन में आउटपुट केवल अवस्था पर निर्भर करता है, संक्रमण पर नहीं।)
समुच्चय, वर्णमाला और शब्द
वर्णमाला Σ चिह्नों का सीमित समुच्चय है, जैसे Σ = {a, b}। शब्द (स्ट्रिंग) चिह्नों का सीमित क्रम है; ख़ाली शब्द ε है। भाषा शब्दों का समुच्चय है, जैसे L = {ab, aab, aaab, …}।
समुच्चय संकेतन: A = {1, 2, 3}; समुच्चय-निर्माण {x | x ∈ ℕ ∧ x < 4}; ∅ रिक्त समुच्चय। संक्रियाएँ: सम्मिलन A ∪ B, सर्वनिष्ठ A ∩ B, अंतर A \ B, कार्तीय गुणनफल A × B (सभी क्रमित युग्म)। समुच्चय परिमित, गणनीय अनंत (जैसे ℕ) या अगणनीय (जैसे ℝ) हो सकते हैं।
सिंटैक्स शब्द का रूप है (क्या वह नियमों से बना है?); सीमैंटिक्स उसका अर्थ।
रेगुलर एक्सप्रेशन और रेगुलर भाषाएँ
रेगुलर एक्सप्रेशन एक छोटा पैटर्न है जो स्ट्रिंग्स के समुच्चय को बताता है:
ab: a फिर ba|b: a या ba*: शून्य या अधिक aa+: एक या अधिक aa?: शून्य या एक a- कोष्ठक समूह बनाते हैं:
(ab)*= ε, ab, abab, …
कोई भाषा रेगुलर है अगर उसे रेगुलर एक्सप्रेशन से लिखा जा सके — और ठीक तभी कोई FSM उसे स्वीकार कर सकती है। उदाहरण: (0|1)*1 = 1 पर ख़त्म होने वाली बाइनरी स्ट्रिंग; 1*01* = ठीक एक 0 वाली स्ट्रिंग।
रोज़मर्रा में: KA05MN1234 जैसी भारतीय नंबर प्लेट का सरल पैटर्न [A-Z]{2}[0-9]{2}[A-Z]{1,2}[0-9]{4} है। पिनकोड, फ़ोन नंबर या तारीख़ भी ऐसे ही जाँचे जाते हैं।
सीमा: FSM बिना सीमा के गिन नहीं सकती। भाषा {aⁿbⁿ} (जितने a उतने b) रेगुलर नहीं है, इसलिए कोई FSM उसे स्वीकार नहीं करती।
कॉन्टेक्स्ट-फ़्री भाषाएँ: BNF और सिंटैक्स आरेख
मिलते कोष्ठक या व्यंजक के अंदर व्यंजक जैसी नेस्टेड संरचनाओं के लिए व्याकरण चाहिए। व्याकरण में टर्मिनल (असली चिह्न), नॉन-टर्मिनल (कोण-कोष्ठक में नाम) और उत्पादन नियम होते हैं। बैकस–नौर फ़ॉर्म (BNF) में:
<digit> ::= 0|1|2|3|4|5|6|7|8|9 <integer> ::= <digit> | <digit><integer>
दूसरा नियम पुनरावर्ती (recursive) है, इसलिए किसी भी लंबाई का पूर्णांक बना सकता है। यही पुनरावृत्ति BNF को रेगुलर एक्सप्रेशन से ज़्यादा ताक़तवर बनाती है: जैसे <S> ::= ab | a<S>b से {aⁿbⁿ} बनता है।
EBNF में शॉर्टकट हैं: {x} दोहराव, [x] वैकल्पिक। सिंटैक्स आरेख यही नियम रेल की पटरियों की तरह दिखाता है: बाएँ से दाएँ कोई भी रास्ता चलिए; अंडाकार टर्मिनल हैं, आयत नॉन-टर्मिनल।
व्युत्पत्ति (पार्स) वृक्ष दिखाता है कि आरंभ चिह्न से शब्द कैसे बना: जैसे 42 → <integer> → <digit><integer> → 4 <digit> → 4 2। कंपाइलर प्रोग्राम जाँचने में ऐसे वृक्ष बनाते हैं।
करके देखें: पहले अंदाज़ा, फिर जाँच
3D के खुले खेल में ऐसा छोटा इनपुट खोजिए जिसमें दो सिक्के हों फिर भी मशीन बंद पर रुके। (संकेत: आख़िरी चिह्न क्या होना चाहिए?)
काग़ज़ पर: वर्णमाला {0, 1} वाली ऐसी FSM बनाइए जो 1 पर ख़त्म होने वाली स्ट्रिंग स्वीकार करे। बस दो अवस्थाएँ चाहिए। 1011 (स्वीकार) और 110 (अस्वीकार) पर जाँचिए।
मुख्य सूत्र और परिभाषाएँ
- FSM = (अवस्थाएँ Q, वर्णमाला Σ, संक्रमण δ: Q × Σ → Q, आरंभ q₀, स्वीकार F)
- स्वीकार ⇔ आख़िरी चिह्न के बाद की अवस्था F में हो
- मीली तीर का लेबल: इनपुट / आउटपुट
- Regex: | (या), * (0 या अधिक), + (1 या अधिक), ? (0 या 1), () समूह
- BNF: <नॉन-टर्मिनल> ::= विकल्प | विकल्प
हल किए गए उदाहरण
1. टर्नस्टाइल को "सिक्का, सिक्का, धक्का, सिक्का" पर चलाइए। वह किस अवस्था में रुकेगा?
बंद → सिक्का → खुला → सिक्का → खुला → धक्का → बंद → सिक्का → खुला। खुला पर रुकता है (स्वीकार)।
2. सम-1 वाली मशीन (S0 स्वीकार, 1 पर अवस्था बदले) में क्या 10110 स्वीकार है?
इसमें तीन 1 हैं। S0 →1→ S1 →0→ S1 →1→ S0 →1→ S1 →0→ S1। S1 पर रुकी: अस्वीकार।
3. 1 से शुरू और 0 पर ख़त्म होने वाली बाइनरी स्ट्रिंग का रेगुलर एक्सप्रेशन लिखिए।
1(0|1)*0। बीच में कुछ भी हो सकता है।
4. इनमें कौन a(b|c)*d से मेल खाते हैं: ad, abcd, abd, acbx?
ad (शून्य दोहराव), abcd और abd मेल खाते हैं। acbx d पर ख़त्म नहीं होता।
5. <integer> ::= <digit> | <digit><integer> से दिखाइए कि 305 मान्य है।
<integer> → <digit><integer> → 3<integer> → 3<digit><integer> → 30<integer> → 30<digit> → 305। मान्य।
6. ऐसी मीली मशीन बनाइए जो वर्तमान बिट पिछले से अलग होने पर 1 दे (शुरुआत में पिछला = 0 मानें)।
अवस्थाएँ P0 (पिछला 0, आरंभ) और P1 (पिछला 1)। P0 —0/0→ P0, P0 —1/1→ P1, P1 —1/0→ P1, P1 —0/1→ P0। इनपुट 0110 पर आउटपुट 0101।
आम गलतियाँ
- आरंभ तीर या स्वीकार अवस्था का दोहरा गोला भूल जाना; तब मशीन पूरी परिभाषित नहीं होती।
- DFA में कोई संक्रमण छोड़ देना। हर अवस्था में हर इनपुट के लिए ठीक एक तीर चाहिए (ज़रूरत हो तो "डेड" अवस्था बनाएँ)।
- सोचना कि a* का मतलब "कम से कम एक a" है। * शून्य भी मानता है; + में कम से कम एक चाहिए।
- सोचना कि FSM किसी भी गहराई के संतुलित कोष्ठक जाँच सकती है। इसके लिए कॉन्टेक्स्ट-फ़्री व्याकरण (BNF) चाहिए, रेगुलर एक्सप्रेशन नहीं।