Alapfogalmak, nyelvek, grammatikák

Alapfogalmak, nyelvek, grammatikák

Hol használják a formális nyelveket?

A természetes nyelvek gépi feldolgozása, matematikai modellezése.
Programozási nyelvek, fordítóprogramok
Kódelmélet
Mintafelismerés
$\dots$

Alapfogalmak, jelölések

Ábécé:* egy véges, nemürres halmaz.
Betűk: az ábécé elemei.
Szó, (string): Egy $V$ ábécé elemeiből képzett véges sorozat.
Egy $u = t_{1} \dots t_{n}$ szóban lévő betűk számát $(n)$ a szó hosszának nevezzük. ( $∣ u ∣$ = n)
$ϵ$ : üres szó
$V^{*}$ jelöli a $V$ ábécé feletti szavak halmazát, beleértve az üres szót is.
$V^{+} = V^{*}$ \ ${ϵ}$

A $V^{*}$ szavait hosszlexikografikus (shortlex) rendezés szerinti sorrendben soroljuk fel.

Résszó: az $u$ szó a $v$ szó résszava, ha $v = xu y, (u, v, x, y \in V^{*})$
Valódi résszó: ha $u \neq = v$ és $u \neq = ϵ$
Prefix: ha $x = ϵ$
Suffix ha $y = ϵ$

Ezek valódiak, ha $ϵ$ -tól és $u$ -tól küéönböznek.

Nyelv: egy $V^{*}$ egy $L$ részhalmaza.
Üres nyelv: $θ$
Véges nyelv: $L$ véges, ellenkező esetben végtelen nyelv
Prefix nyelv: $Pre (L) = {u ∣ u \in V^{*}, uv \in L valamely v \in V^{*} - ra}$
Suffox nyelv: $Suf (L) = {u ∣ u \in V^{*}, vu \in L valamely v \in V^{*} - ra}$

Példák:

$L_{1} = {a, ba, ababb, ϵ}$ (véges)
$L_{2} = {a^{i} b^{i} ∣ i \geq 0}$ (végtelen)
$L_{3} = {u u^{R} ∣ u \in V^{*}}$ (végtelen)
$\dots$

Legyen V egy ábécé továbbá legyenek $u = s_{1} \dots s_{n}$ és $t_{1} \dots t_{k}$ V feletti szavak. Ekkor az $uv : = s_{1} \dots s_{n} t_{1} \dots t_{k}$ szót az $u$ és a $v$ konkatenáltjának nevezzük.

A konkatenáció mint művelet asszciatív, de általában nem kommutatív.

$V^{*}$ a konkatenáció műveletére zárt.

A konkatenáció egységelemes művelet, at egységelem az $ϵ$ .

$i$ -edik hatvány: egy szó $i$ -szeres konkatanációja saját magával. ( $u^{i}$ )

Formálisan: $u^{0} : = ϵ, u^{i} : = u u^{i - 1} (i \geq 1)$

Ekkor: $u^{n + k} = u^{n} u^{k}, (k, n \in N)$

Tükörkép

Legyen $u$ egy $V$ ábécé feletti szó. Az $u$ szó $u^{R}$ -rel jelölt tükörképe (vagy megfordítottja) az a szó, amelyet úgy kapunk, hogy $u$ betűit az eredetihez képest fordított sorrendben konkatenáljuk. Vagyis $u^{R}$ i-edik betűje éppen $u$ -nak az $∣ u ∣ + 1 - i$ . betűje $(1 \leq i \leq ∣ u ∣)$ .

Ha $u = u^{R}$ , akkor $u$ -t palindrom-nak nevezük.

$(u^{R})^{R} = u$
$ϵ^{R} = ϵ$
$(uv)^{R} = v^{R} u^{R}$
$(u^{i})^{R} = (u^{R})^{i}, (i \in N)$

Műveletek nyelveken

Halmazműveletek ( $\cup, \cap, -, \dots$ )
- Komplementer jelölése: $\overline{L} = V^{*} - L$
Konkatenáció: $L_{1} L_{2} = {u_{1} u_{2} ∣ u_{1} \in L_{1}, u_{2} \in L_{2}}$
- asszociatív
- nem kommutatív
$i$ -edik hatvány
- $L^{0} : = {ϵ}$
- $L^{i} : = L L^{i - 1}, (i \geq 1)$
- $L^{k + n} = L^{k} L^{n}, (k, n \in N)$
Tükörkép: $L^{R} : = {u^{R} ∣ u \in L}$

Egy nyelv iteratív leárt

Az $L$ nyelv iteratív lezártja (kleene-lezártja): $L^{*} = \cup_{i \geq 0} L^{i}$

AZ $L$ pozitív lezártja: $L^{+} = \cup_{i \geq 1} L^{i}$

$L^{+} = L^{*}$ , ha $ϵ \in L$ és $L^{+} = L^{*} - {ϵ}$ , ha $ϵ \neq \in L$ .

Homomorfizmus

Legyen $V_{1}$ és $V_{2}$ két ábécé. A $h : V_{1}^{*} \to V_{2}^{*}$ leképezést homomorfizmusnak nevezzük, ha teljesülnek a következő feltételek:

$h$ egyértelmű, azaz minden $u \in V_{1}^{*}$ szóra pontosan egy $v \in v_{2}^{*}$ szó létezik, amelyre $h (u) = v$ teljesül.
$h (uv) = h (u) h (v)$ , minden $u, v \in V_{1}^{*}$ -ra.

h-homomorf képi

Legyen $h : V_{1}^{*} \to V_{2}^{*}$ homomorfizmus. A $h$ homomorfizmus $ϵ$ -mentes, ha $h (u) \neq = ϵ$ bármely $u \in V_{1}^{+}$ szóra. Legyen $h : V_{1}^{*} \to V_{2}^{*}$ homomorfizmus. Az $L \subseteq V_{1}^{*}$ nyelv h-homomorf képén a $h (L) = {h (u) ∣ u \in L} \subseteq V_{2}^{*}$ nyelvet értjük.

Formális nyelvek megadása

Véges nyelvek esetén felsorolással
Formulával
Reguláris kifelyezéssel
Végtelen nyelvek esetén felsoroló algortimussal
Generatív grammatikákkal
- A grammatikák szintetizáló eszközök, egyetlen szimbólumból egy szabályrendszer segítségével szavakat lehet felépíteni. Azon szavak halmaza, melyeket fel lehet építeni egy nyelvet határoz meg, tehát a grammatika szabályrendszere meghatároz egy nyelvet.
Matematikai gépek, automaták segítségével
- Az automaták elemző, analitikus eszközök. Az automaták bemenete egy szó, kimenete egy bináris érték. Az automata szabályrendszere szerint feldolgozza a szavakat, csak bizonyos szavak esetén ad igen választ, ezen szavak egy nyelvet alkotnak, melyet az automata szabályrendszere határoz meg.

Figyelem! Nem feltétlen lehet minden eszközzel minden nyelvet megadni. Be fogjuk látni például, hogy reguláris kifejezéssel kevesebb nyelvet lehet leírni mint egy általános grammatikával, de az se elég az összes {0, 1} ábécé feletti nyelv leírásához.

Nyelvcsalások

Ha $X$ egy halmaz, jelölje $P (X)$ az $X$ halmaz hatványhalmazát, azaz $P (X) = {A ∣ \subseteq X}$

Nyelvcsalád alatt nyelveknek egy halmazát értjük.

Grammatikák

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.

Egylépéses levezetés

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$ .

Többlépéses levezetés

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$

4. félévi jegyzetek