Sprawl Lemmas untuk Bahasa Biasa dan Bebas Konteks

Dua lemma pertumbuhan adalah pernyataan yang digunakan untuk membuktikan keterbatasan kelas-kelas penting bahasa formal: reguler dan bebas konteks. Pentingnya kelas-kelas ini bagi pemrogram mudah dimengerti: ekspresi reguler (salah satu deskripsi bahasa reguler) sering digunakan dalam pekerjaan, dan bahasa pemrograman yang sintaksnya dijelaskan oleh tata bahasa bebas konteks bahkan lebih dari itu.

Lemma sangat mirip satu sama lain baik dalam formulasi maupun dalam pembuktian. Kedekatan ini tampak begitu indah bagi saya sehingga saya memutuskan untuk mencurahkan seluruh artikel untuk itu.

Rencananya adalah ini: kami memahami apa bahasa reguler dan apa hubungan antara ekspresi reguler dan automata terbatas, kami merumuskan dan membuktikan lemma ekstensi untuk bahasa biasa, menggunakannya untuk membuktikan ketidakteraturan beberapa bahasa. Kemudian kami melakukan trik serupa dengan bahasa bebas konteks, di sepanjang jalan mencari tahu bagaimana mereka berhubungan dengan bahasa biasa dan bagaimana menyiasati pembatasan yang ditemukan menggunakan tata bahasa umum. Pergilah!

KDPV menggambarkan proses pertumbuhan untuk tata bahasa KS

— ( , ) . , , . : $$$\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$pindah ke kanan garis. Pola serupa sering ditemukan dalam algoritma untuk mesin Turing.

Hal ini juga digunakan dalam membuktikan kesetaraan (dalam beberapa bukan arti paling sederhana) dari mesin Turing dan kalkuli asosiatif berdasarkan tata bahasa. Saya akan memberi tahu Anda tentang hal itu lain waktu.