नियमित और संदर्भ-मुक्त भाषाओं के लिए फैलाव नींबू

दो विकास नींबू ऐसे कथन हैं जिनका उपयोग औपचारिक भाषाओं की महत्वपूर्ण कक्षाओं की सीमा को साबित करने के लिए किया जाता है: नियमित और संदर्भ-मुक्त। प्रोग्रामर के लिए इन कक्षाओं के महत्व को समझना आसान है: नियमित अभिव्यक्ति (नियमित भाषाओं के विवरणों में से एक) का उपयोग काम में अक्सर किया जाता है, और प्रोग्रामिंग भाषाएं जिनका सिंटैक्स संदर्भ-मुक्त व्याकरण द्वारा वर्णित किया जाता है, वे और भी अधिक हैं।

नींबू एक दूसरे के दोनों रूपों और प्रमाणों में समान हैं। यह निकटता मुझे इतनी अद्भुत लगी कि मैंने इसे पूरा लेख समर्पित करने का फैसला किया।

योजना यह है: हम समझते हैं कि नियमित भाषाएं क्या हैं और नियमित अभिव्यक्तियों और परिमित ऑटोमेटा के बीच क्या संबंध है, हम नियमित भाषाओं के लिए एक एक्सटेंशन लेम्मा बनाते हैं और साबित करते हैं, इसका उपयोग कई भाषाओं की अनियमितता साबित करने के लिए करते हैं। फिर हम संदर्भ-मुक्त भाषाओं के साथ एक समान चाल करते हैं, साथ ही यह भी पता लगाते हैं कि कैसे वे नियमित भाषाओं से संबंधित हैं और आम व्याकरणों का उपयोग करके खोज की गई प्रतिबंधों के आसपास कैसे पहुंचें। जाओ!

केडीपीवी केएस व्याकरण के लिए विकास प्रक्रिया को दिखाता है

— ( , ) . , , . : $$$\Sigma$. , .. , : $$$\varepsilon$.

(.. ), : . . , .

1.

: , , .

, :

• $$$\varnothing$ — , ;
• $$$\{\varepsilon\}$ — , , , ;
• $$$\{a\}, a \in \Sigma$ — , .

. $$$A$ $$$B$ — , :

• $$$A \cup B$ — ;
• $$$A \cdot B = \{\alpha \beta | \alpha \in A, \beta \in B \}$ — : , $$$A$, $$$B$;
• $$$A^*= \{\alpha_1 \alpha_2 ... \alpha_k | k \in \mathbb{N}_0, \alpha_i \in A \}$ — : $$$k$ $$$A$, $$$k$ .

: $$$\mathbb{N}_0 = \mathbb{N} \cup \{0\}$, ,

: $$$A \cdot B = AB$.

. , , . , PuTTY, - :

http[s]?://(?:[a-zA-Z]|[0-9]|[$-_@.&+]|[!*\(\),]|(?:%[0-9a-fA-F][0-9a-fA-F]))+

, url' , , , , url'. .

: ([0-9]), ([s]?), (a+ — , aa*, .. ) . , , .

, ( ), | (), * () . , .

, :

$$$abc(de^*f|de)$

, :

abcde
abcdf
abcdef
abcdeef
abcdeeef
abcdeeeef

.

2.

. — , . , (). .

. , , .

, , . , , . , — , .

. , , , , .

, $$$bab|aab^{*}ca$

. $$$a_i$, $$$a_j$, $$$a_k$ — . $$$a_i$ $$$a_k$ , $$$L_{ik}$. , $$$a_i$ $$$a_j$ $$$L_{ij}$, $$$a_j$ $$$a_k$ — $$$L_{jk}$. , $$$a_j$ , $$$L_{jj}$.

$$$a_j$, $$$a_i$ $$$a_k$ ,

$$

$$L^{'}_{ik} = L_{ik} \cup L_{ij} \cdot L^{*}_{jj} \cdot L_{jk}$$

, $$$a_j$. , , , .

, , . , - , $$$\varepsilon$. , . , .

, . : ; , , , , ; , , , , .

, . , , :

, .

3.

$$$L = \{a^nb^n | n \in \mathbb{N}_0 \}$. $$$\varepsilon$, $$$ab$, $$$aabb$, $$$aaabbb$ . ? , .

, , . , , : , $$$a$ — $$$b$. , ? … , , ?

, ! , , .

. $$$L$ $$$n \in \mathbb{N}$ , $$$\forall w \in L, |w| \ge n$ $$$x$, $$$y$, $$$z$, : $$$w = xyz$; $$$y \ne \varepsilon$; $$$|xy| \le n$; $$$\forall k \ge 0: xy^kz \in L$.

: , , ( .. ) , , .

$$$L = \{a^nb^n | n \in \mathbb{N}_0\}$. $$$n$ — . $$$a^nb^n$ $$$a^nb^n = xyz$,
$$$|xy|\le n$, , , $$$xy$ $$$a$. $$$y$ $$$a$, . $$$xy^kz$ $$$k>1$ $$$a$, $$$b$ , , $$$L$. $$$L$. , $$$L$ !

$$$(^n)^n$, . .

4. -

— , .

: () $$$T$ () $$$N$; $$$\Sigma = N \cup T$. $$$S \in N$ — .

$$$P$. $$$\varphi$ $$$\Sigma$: $$$(s_1, s_2) \in \varphi$, $$$s_1$ $$$s_2$. : . , $$$(s_1, s_2) \in \varphi$, $$$s_1 \rightarrow s_2$.

$$$\beta$ $$$\alpha$, $$$\alpha = xs_1z$, $$$\beta = xs_2z$ $$$(s_1, s_2) \in \varphi$. , — . : $$$\alpha \vdash \beta$.

, $$$\beta$ $$$\alpha$ ( ), $$$s_0 = \alpha$, $$$s_1$, $$$s_2$, ..., $$$s_{k+1}=\beta$, : $$$s_i \vdash s_{i+1}$. $$$\alpha \Rightarrow \beta$.

$$$s$ , : $$$s \in T^*$, $$$S \Rightarrow s$. , , .

, - (-), — . , - , - .

, - :

$$$S \rightarrow (S)S$
$$$S \rightarrow \varepsilon$

, , . , - , . ; .

, , «» :

def BuildPath(queue, parents, parent):
    path = []
    while parents[parent] != parent:
        path += [queue[parent]]
        parent = parents[parent]
    return path[::-1]

def Solve(rules, target):
    queue = ['S']
    parents = [0]

    idx = 0
    while idx < len(queue):
        current = queue[idx]

        for rule in rules:
            entryIdx = current.find(rule[0])
            while entryIdx != -1:
                new = current[:entryIdx] + rule[1] + current[entryIdx + len(rule[0]):]

                if new == target:
                    path = [queue[0]] + BuildPath(queue, parents, idx) + [new]
                    return path

                queue.append(new)
                parents.append(idx)

                entryIdx = current.find(rule[0], entryIdx + 1)

        idx += 1

, , , , , ; ! :

rules = [
    ("S", "(S)S"),
    ("S", ""),
]
target = "(()())()"
print('\n'.join(Solve(rules, target)))

S
(S)S
((S)S)S
((S)(S)S)S
((S)(S)S)(S)S
(()(S)S)(S)S
(()()S)(S)S
(()())(S)S
(()())()S
(()())()

- $$$L = \{a^nb^n | n \in \mathbb{N}_0\}$:

rules = [
    ("S", "aSb"),
    ("S", ""),
]
target = "aaabbb"
print('\n'.join(Solve(rules, target)))

S
aSb
aaSbb
aaaSbbb
aaabbb

- , . , -, . , - : , , , .

, - .

5. -

$$$L = \{ a^nb^nc^n | n \in \mathbb{N}_0 \}$. , - $$$a^nb^n$, , , - :

$$$S \rightarrow \varepsilon$
$$$S \rightarrow AB$
$$$A \rightarrow aAb$
$$$B \rightarrow Bc$
$$$A \rightarrow \varepsilon$
$$$B \rightarrow \varepsilon$

$$$a^nb^nc^m$. , $$$m$ $$$n$? « » , , . , , . -,

- . - $$$L$ $$$n \in \mathbb{N}$ , $$$\forall w \in L, |w| \ge n$ $$$u$, $$$v$, $$$x$, $$$y$, $$$z$, : $$$w = uvxyz$; $$$vy \ne \varepsilon$; $$$|vxy| \le n$; $$$\forall k \ge 0: uv^kxy^kz \in L$.

$$$L = \{ a^nb^nc^n | n \in \mathbb{N}_0\}$. , -. , $$$n$ — . $$$a^nb^nc^n$.

, $$$a^nb^nc^n=uvxyz$, $$$|vxy| \le n$ $$$vy \ne \varepsilon$, $$$uv^kxy^kz$ .

$$$vxy$ $$$a$, $$$c$, .. $$$w$ $$$a$ $$$c$ $$$n$ $$$b$, $$$vxy$ $$$n$.

$$$uv^kxy^kz$ $$$k$. , $$$k>1$ $$$m$, $$$uv^kxy^kz = a^mb^mc^m$, $$$L$. , -!

---

6.

, - . , $$$L = \{ a^nb^nc^n | n \in \mathbb{N}_0 \}$, .

:

$$$S \rightarrow \varepsilon$
$$$S \rightarrow aHbCE$

$$$E$ , $$$b$ $$$c$. :

$$$E \rightarrow \varepsilon$

$$$H$ :

$$$H \rightarrow aHbC$
$$$H \rightarrow \varepsilon$

, , $$$C$ $$$c$. - !

$$$Cb \rightarrow bC$
$$$CE \rightarrow Ec$

! 5 , :

rules = [
    ("S", "aHbCE"),
    ("H", ""),
    ("H", "aHbC"),
    ("Cb", "bC"),
    ("CE", "Ec"),
    ("E", ""),
]
target = "aaabbbccc"
print('\n'.join(Solve(rules, target)))

S
aHbCE
aaHbCbCE
aaaHbCbCbCE
aaaHbbCCbCE
aaaHbbCbCCE
aaaHbbbCCCE
aaaHbbbCCEc
aaaHbbbCEcc
aaaHbbbEccc
aaaHbbbccc
aaabbbccc

: «» ; $$$C$ . .

( ) , . - .