ऑटोमेटा और औपचारिक भाषा सिद्धांत: रेगुलर एक्सप्रेशन के पीछे का विज्ञान और चॉम्स्की पदानुक्रम

कंप्यूटर विज्ञान की नींव का समर्थन करने वाला भव्य सिद्धांत, ऑटोमेटा ( Automata ) और औपचारिक भाषा सिद्धांत ( Formal Language Theory ) है।

रेगुलर एक्सप्रेशन ( Regular Expressions ) जो हम रोज़ लिखते हैं, प्रोग्रामिंग भाषाओं के सोर्स कोड को पार्स करने वाले कंपाइलर से लेकर प्राकृतिक भाषा प्रसंस्करण ( Natural Language Processing ) तक, इन सभी के मूल में यह सिद्धांत मौजूद है। इस लेख में, चॉम्स्की पदानुक्रम ( Chomsky Hierarchy ) के वर्गीकरण को धुरी बनाकर, हम आपको एक गहरे विश्व में ले जाएंगे जो गणितीय और अमूर्त रूप से गणना की अवधारणा को ही परिभाषित करता है।

1. औपचारिक भाषा क्या है?

हिंदी या अंग्रेजी जैसी “प्राकृतिक भाषाओं” के विपरीत, जिन्हें हम आमतौर पर उपयोग करते हैं, गणितीय नियमों द्वारा सख्ती से परिभाषित भाषा को औपचारिक भाषा ( Formal Language ) कहा जाता है। एक औपचारिक भाषा निम्नलिखित बुनियादी घटकों से बनी होती है।

वर्णमाला और स्ट्रिंग्स

औपचारिक भाषा सिद्धांत में वर्णमाला ( Alphabet ) प्रतीकों का एक गैर-रिक्त सीमित सेट (non-empty finite set) है। इसे आमतौर पर $ \Sigma $ (सिग्मा) प्रतीक द्वारा दर्शाया जाता है।

$$ \Sigma = \{ 0, 1 \} $$

ऊपर बाइनरी संख्या की वर्णमाला है। इस वर्णमाला से उत्पन्न सीमित लंबाई वाले प्रतीकों के अनुक्रम को स्ट्रिंग ( String ) या शब्द ( Word ) कहा जाता है।

वर्णमाला $ \Sigma $ से बनी सभी स्ट्रिंग्स के सेट को (जिसमें खाली स्ट्रिंग $ \epsilon $ शामिल है) क्लीनी स्टार ( Kleene Star ) का उपयोग करके $ \Sigma^* $ के रूप में लिखा जाता है।

भाषा की परिभाषा

औपचारिक भाषा $ L $, $ \Sigma^* $ के एक उपसमुच्चय (subset) के रूप में परिभाषित की गई है। यानी, $ L \subseteq \Sigma^* $ है।

उदाहरण के लिए, “0 और 1 से बनी, और हमेशा 1 पर समाप्त होने वाली स्ट्रिंग्स का सेट” एक भाषा है। इस भाषा $ L $ को इस प्रकार लिखा जा सकता है:

$$ L = \{ w1 \mid w \in \{ 0, 1 \}^* \} $$

औपचारिक भाषा सिद्धांत का मुख्य उद्देश्य यह स्पष्ट करना है कि अनंत स्ट्रिंग्स के ऐसे सेट (भाषाओं) को सीमित नियमों (व्याकरण) या सीमित अवस्थाओं (states) वाली मशीनों (ऑटोमेटा) द्वारा कैसे व्यक्त और पहचाना जा सकता है।

2. चॉम्स्की पदानुक्रम ( Chomsky Hierarchy )

भाषाविद् नोम चॉम्स्की ( Noam Chomsky ) ने 1956 में औपचारिक भाषाओं को उनके उत्पादन नियमों के प्रतिबंधों की ताकत के अनुसार चार पदानुक्रमों में वर्गीकृत किया। इसे ही चॉम्स्की पदानुक्रम कहा जाता है।

पदानुक्रम को निम्नानुसार वर्गीकृत किया गया है (प्रकार 0 से प्रकार 3 तक)। संख्या जितनी अधिक होगी, व्यक्त की जा सकने वाली भाषाओं का वर्ग उतना ही संकीर्ण होगा, लेकिन कंप्यूटर के लिए इसका विश्लेषण करना उतना ही आसान होगा।

  flowchart TD
    "Type0"["प्रकार-0: पुनरावर्ती गणना योग्य भाषा\n(ट्यूरिंग मशीन)"]
    "Type1"["प्रकार-1: संदर्भ-संवेदनशील भाषा\n(रैखिक बाध्य ऑटोमेटन)"]
    "Type2"["प्रकार-2: संदर्भ-मुक्त भाषा\n(पुशडाउन ऑटोमेटन)"]
    "Type3"["प्रकार-3: नियमित भाषा\n(परिमित ऑटोमेटन)"]

    "Type0" --- "Type1"
    "Type1" --- "Type2"
    "Type2" --- "Type3"

    style "Type0" fill:#f9f9f9,stroke:#333,stroke-width:2px
    style "Type1" fill:#e9e9e9,stroke:#333,stroke-width:2px
    style "Type2" fill:#d9d9d9,stroke:#333,stroke-width:2px
    style "Type3" fill:#c9c9c9,stroke:#333,stroke-width:2px

प्रकार 3 (नियमित भाषा) : रेगुलर एक्सप्रेशन द्वारा व्यक्त की जा सकती है, और सीमित ऑटोमेटन (Finite Automaton) द्वारा पहचानने योग्य है।
प्रकार 2 (संदर्भ-मुक्त भाषा) : प्रोग्रामिंग भाषाओं के सिंटैक्स आदि में उपयोग की जाती है, और पुशडाउन ऑटोमेटन द्वारा पहचानने योग्य है।
प्रकार 1 (संदर्भ-संवेदनशील भाषा) : रैखिक बाध्य ऑटोमेटन (Linear Bounded Automaton) द्वारा पहचानने योग्य है।
प्रकार 0 (पुनरावर्ती गणना योग्य भाषा) : ट्यूरिंग मशीन द्वारा पहचानने योग्य है। सभी गणना योग्य भाषाएं।

अगले अध्याय से, हम इस पदानुक्रम को नीचे से क्रम में (सबसे सख्त प्रतिबंध Type-3 से) गहराई से देखेंगे।

3. नियमित भाषाएं और सीमित ऑटोमेटा ( Type-3 )

सीमित ऑटोमेटा ( DFA / NFA )

चॉम्स्की पदानुक्रम के सबसे अंदर नियमित भाषाएं ( Regular Languages ) हैं। इस भाषा को पहचानने वाला कम्प्यूटेशनल मॉडल सीमित ऑटोमेटा ( Finite Automata, FA ) है।

सीमित ऑटोमेटा में, एक निर्धारित अवस्था संक्रमण वाला DFA ( Deterministic Finite Automaton ) और एक अनिर्धारित NFA ( Nondeterministic Finite Automaton ) मौजूद हैं। आश्चर्यजनक रूप से, यह सिद्ध हो चुका है कि इन दोनों द्वारा पहचानी जा सकने वाली भाषाओं का वर्ग पूरी तरह से समान है (DFA और NFA समतुल्य हैं)।

गणितीय रूप से, DFA को निम्नलिखित 5-टपल $ M = (Q, \Sigma, \delta, q_0, F) $ के रूप में परिभाषित किया गया है।

$ Q $ : अवस्थाओं का सीमित सेट
$ \Sigma $ : वर्णमाला
$ \delta $ : अवस्था संक्रमण फलन ( $ \delta: Q \times \Sigma \rightarrow Q $ )
$ q_0 $ : प्रारंभिक अवस्था ( $ q_0 \in Q $ )
$ F $ : स्वीकार्य अवस्थाओं (अंतिम अवस्थाओं) का सेट ( $ F \subseteq Q $ )

ठोस उदाहरण: “101” वाली स्ट्रिंग को स्वीकार करने वाला DFA

वर्णमाला $ \Sigma = \{ 0, 1 \} $ के लिए, एक ऐसे DFA पर विचार करें जो उन स्ट्रिंग्स को पहचानता है जिनमें “101” एक सबस्ट्रिंग के रूप में शामिल है।

  stateDiagram-v2
    [*] --> "q0"
    "q0" --> "q1" : "1"
    "q0" --> "q0" : "0"
    "q1" --> "q2" : "0"
    "q1" --> "q1" : "1"
    "q2" --> "q3" : "1"
    "q2" --> "q0" : "0"
    "q3" --> "q3" : "0, 1"
    "q3" --> [*]

इस अवस्था संक्रमण आरेख को पायथन (Python) प्रोग्राम के रूप में लागू करते हैं।

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class DFA:
    def __init__(self):
        self.states = {'q0', 'q1', 'q2', 'q3'}
        self.alphabet = {'0', '1'}
        self.start_state = 'q0'
        self.accept_states = {'q3'}
        
        # अवस्था संक्रमण फलन
        self.transitions = {
            'q0': {'0': 'q0', '1': 'q1'},
            'q1': {'0': 'q2', '1': 'q1'},
            'q2': {'0': 'q0', '1': 'q3'},
            'q3': {'0': 'q3', '1': 'q3'}
        }
        
    def accepts(self, string: str) -> bool:
        current_state = self.start_state
        for char in string:
            if char not in self.alphabet:
                return False
            current_state = self.transitions[current_state][char]
        return current_state in self.accept_states

# परीक्षण
dfa = DFA()
test_strings = ["001010", "11101", "1001", "010", "101"]

for s in test_strings:
    result = dfa.accepts(s)
    print(f"स्ट्रिंग '{s}': {'स्वीकार किया गया' if result else 'अस्वीकार किया गया'}")

रेगुलर एक्सप्रेशन के साथ संबंध (क्लीनी का प्रमेय)

प्रोग्रामिंग में उपयोग किया जाने वाला रेगुलर एक्सप्रेशन ( Regular Expression ) इस नियमित भाषा का वर्णन करने के लिए एक संकेतन (notation) है। स्टीफन क्लीनी ( Stephen Kleene ) ने यह प्रमेय सिद्ध किया कि “किसी भाषा का रेगुलर एक्सप्रेशन द्वारा दर्शाया जाना और सीमित ऑटोमेटन द्वारा स्वीकार किया जाना समतुल्य है।”

वास्तविक प्रोग्रामिंग भाषाओं के रेगुलर एक्सप्रेशन इंजन (जैसे Python का re मॉड्यूल) दिए गए रेगुलर एक्सप्रेशन पैटर्न से आंतरिक रूप से NFA बनाते हैं, और स्ट्रिंग का मूल्यांकन करते हैं।

पम्पिंग लेम्मा ( Pumping Lemma ) की सीमाएँ

नियमित भाषाएं बहुत उपयोगी होती हैं, लेकिन उनकी सीमाएँ हैं। उदाहरण के लिए, " $ n $ $ a $ के बाद $ n $ $ b $ वाली स्ट्रिंग्स का सेट" ( $ L = \{ a^n b^n \mid n \ge 0 \} $ ) एक नियमित भाषा नहीं है। सीमित ऑटोमेटा के पास “गिनने” के लिए मेमोरी (जैसे स्टैक) नहीं होती है, इसलिए यह अनंत तक याद नहीं रख सकता कि कितने $ a $ आए हैं। इसे सिद्ध करने के लिए गणितीय तकनीक नियमित भाषाओं का पम्पिंग लेम्मा है।

4. संदर्भ-मुक्त भाषाएं और पुशडाउन ऑटोमेटा ( Type-2 )

नियमित भाषाओं द्वारा व्यक्त नहीं किए जा सकने वाले ब्रैकेट के मिलान, और प्रोग्रामिंग भाषाओं के सिंटैक्स (जैसे if-else का नेस्टिंग) को व्यक्त करने के लिए संदर्भ-मुक्त भाषाओं ( Context-Free Languages, CFL ) की आवश्यकता होती है।

पुशडाउन ऑटोमेटन ( PDA )

संदर्भ-मुक्त भाषा को पहचानने वाला कम्प्यूटेशनल मॉडल पुशडाउन ऑटोमेटन ( Pushdown Automaton, PDA ) है। PDA एक सीमित ऑटोमेटन है जिसमें स्टैक ( Stack, लास्ट-इन फर्स्ट-आउट मेमोरी) जोड़ा गया है। स्टैक का उपयोग करके, “खुले ब्रैकेट की संख्या को याद रखना, और हर बार बंद ब्रैकेट आने पर उसे खपाना” जैसी चीजें संभव हो जाती हैं।

ठोस उदाहरण: $ a^n b^n $ को स्वीकार करने वाला PDA

वर्णमाला $ \Sigma = \{ a, b \} $ के साथ, एक PDA लागू करते हैं जो समान संख्या में $ a $ और $ b $ वाली स्ट्रिंग्स को स्वीकार करता है।

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class PDA:
    def __init__(self):
        self.stack = []
        self.state = 'q0'
        
    def accepts(self, string: str) -> bool:
        self.stack = []
        self.state = 'q_a' # a को पढ़ने की अवस्था
        
        for char in string:
            if self.state == 'q_a':
                if char == 'a':
                    self.stack.append('A') # स्टैक पर रखें
                elif char == 'b':
                    self.state = 'q_b'
                    if not self.stack:
                        return False
                    self.stack.pop() # स्टैक से निकालें
                else:
                    return False
            elif self.state == 'q_b':
                if char == 'b':
                    if not self.stack:
                        return False
                    self.stack.pop()
                else:
                    return False
                    
        # जब स्ट्रिंग पढ़ना समाप्त हो जाए, यदि स्टैक खाली है तो स्वीकार करें
        return len(self.stack) == 0

# परीक्षण
pda = PDA()
print("aaabbb:", pda.accepts("aaabbb")) # True
print("aabbb:", pda.accepts("aabbb"))   # False
print("ab:", pda.accepts("ab"))         # True
print("a:", pda.accepts("a"))           # False

संदर्भ-मुक्त व्याकरण ( CFG ) और BNF

संदर्भ-मुक्त भाषा उत्पन्न करने वाले नियमों को संदर्भ-मुक्त व्याकरण ( Context-Free Grammar, CFG ) कहा जाता है। CFG को $ (V, \Sigma, R, S) $ द्वारा परिभाषित किया जाता है। यहां $ R $, $ A \rightarrow \gamma $ के रूप में उत्पादन नियमों का सेट है। ( $ A $ एक गैर-टर्मिनल प्रतीक है, $ \gamma $ टर्मिनल और गैर-टर्मिनल प्रतीकों का क्रम है)।

प्रोग्रामिंग भाषा विनिर्देशों में अक्सर देखा जाने वाला BNF ( Backus-Naur Form ) इस संदर्भ-मुक्त व्याकरण का वर्णन करने के लिए एक मेटा-भाषा है। नीचे गणितीय सूत्रों को परिभाषित करने वाले BNF का एक उदाहरण दिया गया है।

1
2
3
4
<expr>   ::= <expr> "+" <term> | <term>
<term>   ::= <term> "*" <factor> | <factor>
<factor> ::= "(" <expr> ")" | <number>
<number> ::= "0" | "1" | "2" | ... | "9"

कंपाइलर के सिंटैक्स विश्लेषण ( Parsing ) चरण में, लेक्सिकल विश्लेषक द्वारा उत्पन्न टोकन अनुक्रम इस संदर्भ-मुक्त व्याकरण का पालन करते हैं या नहीं, इसकी जाँच PDA के सिद्धांत (LL पार्सिंग या LR पार्सिंग) को लागू करने वाले एल्गोरिदम द्वारा की जाती है, और एक एब्स्ट्रैक्ट सिंटैक्स ट्री ( AST ) बनाया जाता है।

5. संदर्भ-संवेदनशील भाषाएं और रैखिक बाध्य ऑटोमेटा ( Type-1 )

संदर्भ-मुक्त भाषाएं प्रोग्रामिंग भाषाओं के अधिकांश सिंटैक्स को व्यक्त कर सकती हैं, लेकिन “केवल घोषित चर (variables) का ही उपयोग किया जा सकता है” जैसे आस-पास के संदर्भ (अर्थ संबंधी बाधाओं) पर निर्भर प्रतिबंधों को व्यक्त नहीं कर सकतीं। इन्हें संदर्भ-संवेदनशील भाषाओं ( Context-Sensitive Languages, CSL ) द्वारा नियंत्रित किया जाता है।

रैखिक बाध्य ऑटोमेटन ( LBA )

संदर्भ-संवेदनशील भाषा को पहचानने वाला मॉडल रैखिक बाध्य ऑटोमेटन ( Linear Bounded Automaton, LBA ) है। LBA ट्यूरिंग मशीन का ही एक प्रकार है, लेकिन इसकी विशेषता यह है कि टेप की लंबाई इनपुट स्ट्रिंग की लंबाई (रैखिक) के अनुपात में सीमित होती है।

संदर्भ-संवेदनशील भाषा का एक विशिष्ट उदाहरण $ L = \{ a^n b^n c^n \mid n \ge 1 \} $ है। क्योंकि PDA के पास केवल एक स्टैक होता है, यह $ a $ और $ b $ की संख्या का मिलान कर सकता है, लेकिन यह बाद में आने वाले $ c $ की संख्या का मिलान नहीं कर सकता (क्योंकि यह $ a $ की गिनती करके स्टैक से सब कुछ पॉप कर चुका होगा)। LBA टेप पर आगे-पीछे जा सकता है, इसलिए यह इस भाषा को पहचान सकता है।

प्राकृतिक भाषाएं (मानव भाषाएं) आमतौर पर संदर्भ-मुक्त भाषाओं की तुलना में अधिक जटिल मानी जाती हैं और संदर्भ-संवेदनशील भाषाओं के करीब के गुण रखती हैं।

6. पुनरावर्ती गणना योग्य भाषाएं और ट्यूरिंग मशीनें ( Type-0 )

अंत में हम पुनरावर्ती गणना योग्य भाषाओं ( Recursively Enumerable Languages ) और ट्यूरिंग मशीन ( Turing Machine ) पर पहुँचते हैं।

ट्यूरिंग मशीन: गणना का अंतिम मॉडल

1936 में एलन ट्यूरिंग ( Alan Turing ) द्वारा खोजी गई ट्यूरिंग मशीन में किसी भी आधुनिक कंप्यूटर (वॉन न्यूमैन आर्किटेक्चर) की सैद्धांतिक सीमाओं के बराबर कंप्यूटिंग शक्ति है।

एक ट्यूरिंग मशीन एक असीम रूप से लंबे “टेप”, एक “हेड” जो टेप पर पढ़ते और लिखते समय बाएँ और दाएँ चलता है, और सीमित संख्या में “अवस्थाओं” से बनी होती है।

  flowchart LR
    subgraph "Tape"
        direction LR
        "T1"["..."] --- "T2"["0"] --- "T3"["1"] --- "T4"["1"] --- "T5"["0"] --- "T6"["..."]
    end
    "Head"(("Head")) --> "T3"
    "State"["अवस्था: q_read\n(परिमित नियंत्रण)"] --- "Head"

हॉल्टिंग समस्या ( Halting Problem )

ट्यूरिंग मशीन के ढांचे में सबसे महत्वपूर्ण खोजों में से एक अनिर्णेयता ( Undecidability ) का अस्तित्व है। “किसी दिए गए मनमाने प्रोग्राम और इनपुट के लिए, ऐसा कोई प्रोग्राम (एल्गोरिदम) मौजूद नहीं है जो यह निर्धारित कर सके कि वह प्रोग्राम कभी रुकेगा (halt) या अनंत लूप में फँस जाएगा।” यह प्रसिद्ध हॉल्टिंग समस्या ( Halting Problem ) है।

यह उस गणितीय सीमा को दर्शाता है कि, चाहे हम कितने भी शक्तिशाली AI या कंप्यूटर बना लें, “एक पूर्ण स्थैतिक विश्लेषण उपकरण (static analysis tool) जो सभी बग और अनंत लूप का स्वचालित रूप से पहले ही पता लगा ले, कभी भी नहीं बनाया जा सकता है।”

7. आधुनिक सॉफ्टवेयर विकास और औपचारिक भाषा सिद्धांत का प्रतिच्छेदन

अब तक हमने जो सिद्धांत देखे हैं, वे केवल अकादमिक आइवरी टावर तक सीमित नहीं हैं। वे आधुनिक सॉफ्टवेयर इंजीनियरिंग में हर जगह सक्रिय हैं।

लेक्सिकल विश्लेषक ( Lexer ) का स्वचालित निर्माण: Lex और Flex जैसे उपकरण डेवलपर्स द्वारा लिखे गए रेगुलर एक्सप्रेशन को DFA में बदलते हैं और तेज़ C भाषा कोड स्वचालित रूप से उत्पन्न करते हैं।
सिंटैक्स विश्लेषक ( Parser ) का स्वचालित निर्माण: Yacc और Bison जैसे उपकरण डेवलपर्स द्वारा लिखे गए BNF (संदर्भ-मुक्त व्याकरण) से LR पार्सर (PDA का एक अनुप्रयोग) स्वचालित रूप से उत्पन्न करते हैं।
JSON और XML की पार्सिंग: इन डेटा स्वरूपों का सत्यापन (validation) और पार्सिंग भी औपचारिक भाषा सिद्धांत के एल्गोरिदम पर आधारित है।
संपादकों का सिंटैक्स हाइलाइटिंग: IDE कोड को तेज़ी से रंग सकता है क्योंकि इसके पीछे सीमित ऑटोमेटा काम कर रहा है।

रेगेक्स इंजन का नुकसान ( Catastrophic Backtracking )

कई प्रोग्रामिंग भाषाओं ( Java, Python, Ruby, JavaScript, आदि ) में अंतर्निहित रेगुलर एक्सप्रेशन इंजन शुद्ध सैद्धांतिक DFA नहीं हैं, बल्कि बैकट्रैकिंग वाले NFA-आधारित (या बैकट्रैकिंग इंजन) के रूप में लागू किए जाते हैं।

इस वजह से, जब कुछ रेगुलर एक्सप्रेशन पैटर्न (जैसे: (a+)+$ आदि) को चतुर स्ट्रिंग्स दी जाती हैं, तो गणना का समय तेजी से (exponentially) बढ़ जाता है और सिस्टम फ्रीज हो सकता है। इसे ReDoS ( Regular Expression Denial of Service ) भेद्यता (vulnerability) कहा जाता है। यदि आप सिद्धांत को जानते हैं, तो आप तार्किक रूप से विचार कर सकते हैं कि बैकट्रैकिंग क्यों होती है, और कैसे पैटर्न को फिर से लिखा जाए ताकि इसे सुरक्षित DFA समतुल्य प्रसंस्करण में बदला जा सके।

निष्कर्ष: अमूर्तता का सौंदर्य

ऑटोमेटा और औपचारिक भाषा सिद्धांत कंप्यूटर की भौतिक संरचना (CPU और मेमोरी) को पूरी तरह से हटाकर, “गणना क्या है” और “भाषा क्या জ্ঞ” को एक शुद्ध गणितीय मॉडल में अमूर्त करने का चरम है।

प्रकार-3 (Type-3) (DFA): बिना मेमोरी वाली मशीन (रेगुलर एक्सप्रेशन)
प्रकार-2 (Type-2) (PDA): स्टैक मेमोरी वाली मशीन (सिंटैक्स विश्लेषण)
प्रकार-1 (Type-1) (LBA): सीमित टेप वाली मशीन
प्रकार-0 (Type-0) (TM): अनंत टेप वाली मशीन (सार्वभौमिक कंप्यूटर)

जिस सोर्स कोड को हम हर दिन लिखते हैं, उसे कंपाइलर नामक विशाल ऑटोमेटा के झुंड द्वारा प्रकार-2 (सिंटैक्स) से प्रकार-3 (लेक्सिकल) में तोड़ दिया जाता है, और अंततः मशीन भाषा में अनुवादित किया जाता है।

भले ही सतही ढांचे और भाषाओं के रुझान बदल जाएं, 1950 के दशक से चली आ रही यह मजबूत गणितीय नींव नहीं बदलेगी। कभी-कभी, जब आपको रेगुलर एक्सप्रेशन की जटिल पहेली का सामना करना पड़े, या एक नया पार्सर लिखने का अवसर मिले, तो ट्यूरिंग और चॉम्स्की के महान सिद्धांतों के बारे में क्यों न सोचें जो इसके पीछे हैं।