تمدد Lemmas للغات العادية وخالية من السياق

هناك نوعان من قشور النمو عبارة عن بيانات تُستخدم لإثبات حدود فئات مهمة من اللغات الرسمية: العادية وخالية من السياق. من السهل فهم أهمية هذه الفئات للمبرمجين : يتم استخدام التعبيرات العادية (أحد أوصاف اللغات العادية) في كثير من الأحيان في العمل ، ولغات البرمجة التي يتم وصف تركيبها من خلال القواعد النحوية الخالية من السياق أكثر من ذلك.

تتشابه الليمونات إلى حد كبير مع بعضها البعض سواء في التركيبات أو في البراهين. بدا لي هذا القرب رائعًا جدًا لدرجة أنني قررت تكريس مقال كامل له.

الخطة هي: نحن نفهم ما هي اللغات العادية وما هي العلاقة بين التعبيرات العادية والأتمتة المحدودة ، نقوم بصياغة وإثبات lemma امتداد للغات العادية ، نستخدمها لإثبات عدم انتظام عدة لغات. ثم نقوم بخدعة مماثلة مع اللغات الخالية من السياق ، على طول الطريقة التي نكتشف بها كيفية ارتباطها باللغات العادية وكيفية التحايل على القيود المكتشفة باستخدام القواعد النحوية العامة. اذهب!

يوضح KDPV عملية النمو لقواعد اللغة 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$. .

( ) , . - .