Grammatikák csoportosítása

2. Előadás

Grammatikák - ismétlés

Egy $G = ⟨ N, Σ, P, S ⟩$ rendezett négyest grammatikának nevezünk, ha

$N$ és $Σ$ diszjunkt véges ábácék. $N$ elemeit nemterminális, $Σ$ elemeit pedig terminális szimbólumnak nevezzük.
$S \in N$ a grammatika kezdőszimbóluma
$P$ rendezett $(x, y)$ párok véges halmaza, ahol $x, y \in (N \cup Σ)^{*}$ és $x$ legalább egy nemterminális szimbólumot tartalmaz

A $P$ halmaz elemeit szabályoknak (vagy átírási szabályoknak vagy produkcióknak) hívjuk.

A gyakorlatban az $(x, y)$ jelölés helyett szinte mindig az $x \to y$ jelölést használjuk.

Legyen $G = ⟨ N, Σ, P, S ⟩$ egy generatív grammatika és legyen $u, v \in (N, Σ)^{*}$ . A $v$ szó közvetlenül vagy egy lépésben levezethető az $u$ szóból $G$ -ben, jelölése: $i ⟹_{G} v$ , ha $u = u_{1} x u_{2}$ és
$v = u_{1} y u_{2}$ , ahol $u_{1}, u_{2} \in (N \cup Σ)^{*}$ és $x \to y \in P$ .

Legyen $G = ⟨ N, Σ, P, S ⟩$ egy generatív grammatika és legyen $u, v \in (N, Σ)^{*}$ . A $v$ szó (több lépésben) levezethető, ha $u = v$ vagy van olyan $n \geq 1$ és $w_{0}, \dots, w_{n} \in (N \cup Σ)^{*}$ , hogy $w_{i - 1} ⟹_{G} w_{i} (1 \leq i \leq n), w_{0} = u$ és $w_{n} = v$
Jelölés: $u ⟹_{G}^{*} v$

Grammatikák Chomsky féle osztályozása

Legyen $G = ⟨ N, Σ, P, S ⟩$ egy grammatika. A $G$ grammatika $i$ -típusú ( $i = 0, 1, 2, 3$ ), ha $P$ szabályhalmazára teljesülnek a következők:

$i = 0$ eset: nincs korlátozás
$i = 1$ eset:
- $P$ minden szabálya $u_{1} A u_{2} \to u_{1} v u_{2}$ alakú, ahol $u_{1}, u_{2}, v \in (N \cup Σ)^{*}, A \in N$ és $v \neq = ϵ$
- Egyetlen kivételt megengedünk: $P$ tartalmazhatja az $S \to ϵ$ szabályt, de csak abban az esetben, ha $S$ nem fordul elő $P$ egyetlen szabályának jobb oldalán sem. Korlátozott $ϵ$ szabály (KES)
$i = 2$ eset: $P$ minden szabálya $A \to v$ alakú, ahol $A \in N$ és $v \in (N \cup Σ)^{*}$
$i = 3$ eset: $P$ minden szabálya vagy $A \to u B$ vagy $A \to u$ alakú, ahol $A, B \in N$ és $u \in Σ^{*}$

Jelölje $G_{i}$ az $i$ -típusú gramatikák osztályát.

Grammatikák osztályba sorolása

Legyen $G$ egy grammatika. A következő esetek lehetségesek:

$G \in G_{3}, G_{2}, G_{1}, G_{0}$
Lokálisan minden szabály $3$ -as és teljesül a KES.

$G \in G_{3}, G_{2}, G_{0}$
Lokálisan minden szabály $3$ -as den nem teljesül a KES.

$G \in G_{2}, G_{1}, G_{0}$
Lokálisan minden szabály $2$ -as, van $3$ -as szabály és teljesül a KES.

$G \in G_{2}, G_{0}$
Lokálisan minden szabály $2$ -es, van nem $3$ -as szabály de nem teljesül a KES.

$G \in G_{1}, G_{0}$
Lokálisan minden szabály $1$ -es, van nem $2$ -es szanály és teljesül a KES.

$G \in G_{0}$
Van nem $1$ -es szabálya vagy minden szabály $1$ -es, van nem $2$ -es szabálya és nem teljesül a KES.

$L_{i} : = {L ∣\exists G \in G_{i} hogy L = L (G)}$ jelöli az $i$ -típusú nyelvek nyelvosztályát, elemeit $i$ -típusú nyelveknek nevezzük.

A 0-típusú grammatikákat mondatszerkezetű (phrase-structure) grammatikáknak is nevezzük, ami nyelvészeti eredetükre utal.
A 1-típusú grammatikák a környezetfüggő (context-sensitive) grammatikák, mert szabályai olyanok, hogy, egy A nemterminális valamely előfordulása egy $v$ szóval csak $u 1$ és $u 2$ kontextus jelenlétében helyettesíthető.
2-típusú grammatikákat környezetfüggetlen (context-free) grammatikáknak mondjuk, mert szabályai olyanok, hogy az $A$ nemterminális $v$ -vel való helyettesítése bármely kontextusban megengedett.
A 3-típusú grammatikákat reguláris (regular) vagy véges állapotú (finite state) grammatikáknak hívjuk, a véges állapotú automatákkal való kapcsolatuk miatt.
0,1,2,3-típusú nyelvek osztályait rendre rekurzíven felsorolható, környezetfüggő, környezetfüggetlen, valamint reguláris nyelvosztálynak is mondjuk.

Grammatikák a gyakorlatban

BNF (Backus-Naur Form).

A BNF egy széles körben használt metanyelv melynek segítségével szabályok alkothatók meg (például egy programozási nyelv szintaktikai szabályai).

Építőkövei:

$⟨ n \overset{e}{ˊ} v ⟩$ , fogalmak (nemdeterminánsok)
$::=$ a szabályok bal- és jobboldalának elválasztása
a sztringek alkotóelemei (terminálisok)

Egy szabály bal- és jobboldalból áll, köztük ::=, baloldalon pontosan 1 fogalom, jobboldalon terminálisok és fogalmak véges sorozata állhat.

A BNF megfelel a környezetfüggetlen grammatikának.

Chomsky-féle hierarchia

A grammatikák alakja alapján $G_{3} \subseteq G_{2} \subseteq G_{0}$ és $G_{1} \subseteq G_{0}$

Később azt is meg fogjuk mutatni, hogy a következö tétel fennáll: $L_{3} \subset L_{2} \subset L_{1} \subset L_{0}$

Ekvivalens grammatikák és nyelvek

Amíg minden grammatika egyetlen nyelvet generál, ez fordítva nem igaz. Ugyanazt a nyelvet több különböz ̋o grammatika is generálhatja.

A $G_{1}$ és $G_{2}$ grammatikák ekvivalensek egymással, ha ugyanazt a nyelvet generálják, azaz $L (G_{1}) = L (G_{2})$ teljesül.

Az $L_{1}$ és $L_{2}$ nyelveket egymással gyengén ekvivalensnek nevezzük, ha legfeljebb az $ϵ$ tartalmazásában térnek el egymástól, azaz ha $(L_{1} - L_{2}) \cup (L_{2} - L_{1}) \subseteq {ϵ}$ .

A $G_{1}$ és $G_{2}$ grammatikákat gyengén ekvivalensnek nevezzük, ha egymással gyengén ekvivalens nyelveket generálnak.

Terminánsok elimminációja a szabályok baloldalán

Minden $G = ⟨ N, Σ, P, S ⟩$ grammatikához van vele ekvivalens és azonos típusú $G^{'} = ⟨ N^{'}, Σ, P^{'}, S ⟩$ grammatika, melyre $x \in (N^{'})^{+}$ minden $x \to y \in P^{'}$ -re

Zártsági tulajdonságok

Az unió, konkatenáció és iteratív lezárás műveleteket reguláris műveleteknek nevezzük.

Egy $L$ nyelvcsalád zárt a $φ : (L_{1}, \dots, L_{n}) \to φ (L_{1}, \dots, L_{n})$ $n$ -változós nyelvműveletekre nézve, ha minden $L_{1}, \dots L_{n} \in L$ esetén $φ (L_{1}, \dots L_{n}) \in L$

$L_{i}$ zárt a reguláris műveletekre nézve ( $i = 0, 1, 2, 3$ )

4. félévi jegyzetek