1. gyakorlat

Gyakvez: Kolonits Gábor

Témák: ismétlés és Chomsky normálformára hozás

Ismétlés

Ábécé

Ábécé: Ábécének nevezzük a jelek egy nem üres véges halmazát.

Jele: $V$

Példa: $V = \{a, b, c\}$

Szó

Szó: A V ábécé elemeinek egy tetszőleges véges sorozatát a V ábécé feletti szónak nevezzük.

$\varepsilon$: üres szó
$V^*$: összes lehetséges szó halmaza
$V^+$: nem üres szavak halmaza

Példa: $a, bb, cac, \varepsilon$

Konkatenált

Két szó konkatenációja: Legyenek $u = t_1 \dots t_k$ és $v = q_1 \dots q_m$ szavak egy adott L nyelvből. Ekkor a két szó konkatenációja $uv := t_1 \dots t_kq_1 \dots q_m$ (A két szó egymás utáni leírásával kapott szó.)

Nem kommutatív

$uv \neq vu$

Asszociatív

$u(vw) = (uv)w \forall u, v, w \in V^*$

Példa: $u = ab, \; v = bc \; uv = abbc \; vu = bcab$

Nyelv

Nyelv: $V^*$ valamely részhalmazát a $V$ ábécé feletti nyelvnek nevezzük.

Jele: L

Két speciális nyelv:

Üres nyelv: 0 db szót tartalmaz (jele: $\empty$)
Egyelemű nyelv: csak az üres szót tartalmazza (jele: $\{\varepsilon\}$)

Példa: $L = \{ab, bc, aac, b\} \subseteq V^*$

Nyelvek konkatenáltja

Két nyelv konkatenációja: Legyenek $L_1 $ és $ L_2$ nyelvek. Ekkor az $L_1$ és $L_2$ nyelvek konkatenációján az $L_1 L_2 := \{uv \mid u \in L_1 és v \in L_2 \}$ nyelvet értjük.

$L_1 L_2 \subseteq V^*$

$L_1 L_2 = \{uv \; u \in L_1, v \in L_2\}$

$\empty L = L \empty = \empty$

$\{\varepsilon\} L = L \{\varepsilon\} = L$

Iterált

Nyelv lezártja (iteráltja): Legyen L egy nyelv.

$L^0 := \{\varepsilon\}$

$L^{i + 1} := L^i \, L \quad i \geq 0$

$L^* := \bigcup \limits_{i \geq 0} \, L^i$

$L^+ := \bigcup \limits_{i \geq 1} \, L^i$

Nyelvcsalád

Nyelvek egy véges vagy végtelen halmaza.

Grammatika

Nyíl szintax

Levezetésnél ez használatos: $\Rightarrow$

Több lépés egyszerre levezetésnél: $\xRightarrow*$

Szabályoknál pedig ez: $\to$

$G = (N, T, S, R)$

$N$: nem terminális szimbólumok ABC-je

$T$: terminális szimbólumok ABC-je

$S$: kezdő szimbólum

$R$: átírási szabályok véges halmaza

$N \cap T = \empty$

Példa - G1

$G_1 = (\{S\}, \{a, b\}, S, \{S \to ab \mid \varepsilon\})$

$S \Rightarrow \varepsilon$

$S \Rightarrow aSb \Rightarrow ab$

$S \Rightarrow aSb \xRightarrow* a^i S b^i \Rightarrow a^i b^i$

Ez a nyelvet generálja a grammatika:

$L(G_1) = \{a^i b^i, \; i \geq 0\}$

Példa - G2

$G_1 = (\{S, X, Y\},\; \{a, b, c\},\; S,\; R)$

$R = \{$

$S \to abc \mid aXbc$

$Xb \to bX$

$Xc \to Ybcc$

$bY \to Yb$

$aY \to aaX \mid aa$

$\}$

$S \Rightarrow abc$

$S \Rightarrow aXbc \Rightarrow abXc \Rightarrow abYbcc \Rightarrow aYbbcc \Rightarrow aabbcc$

$S \xRightarrow* aYbbcc \Rightarrow aaXbbcc \Rightarrow aabbXcc \Rightarrow aabbYbccc \xRightarrow* aaabbbccc$

$L(G_2) = \{a^n b^n c^n,\; n \geq 1\}$

Chomsky normálforma (CNF)

Egy 2-es típusú (azaz környezet független) grammatika Chomsky normálformájú alakban van, ha minden szabályának alakja

$A \to BC$
$A \to t$
$A \to \varepsilon$

Ahol $A, B, C \in N,\;\; t \in T \quad$ és S nem szerepel szabály jobb oldalán (KES-szabály).

Bármely környzet független grammatikához meg lehet adni egy fele ekvivalens CNF-et.

Mire jó?

A CNF segítségével belátható, hogy tetszőleges környzet független grammatika és tetszőleges szó esetén a grammatika tudja-e generálni a szót.

Chomsky normálformára hozás lépései

1) Új start szimbólum bevezetése

$G = (N, T, S, R) \; \leadsto$

$G' = (N \cup \{\green{S'}\},\; T,\; \green{S'},\; R \cup \{\green{S' \to S}\})$

Mit csinálunk?

A start szimbólumot lecseréljük (S')
Bevezetjük az "új start szimbólum" $\to$ "eredeti start szimbólum"

2) Álterminálisok bevezetése

$G = (N \cup T',\; T,\; S,\; R')$

$T' := \{t': t \in T\}$

$R' := \{A \to \alpha': A \to \alpha \in R\} \cup \{t' \to t,\, t \in T\}$

Mit csinálunk?

A terminálisok maradnak
Vezessünk be a terminálisok mintájára új nem terminálisokat
Írjuk át a terminálisokat az új nem terminálisokra az eddigi szabályokban
Vezessünk be új szabályokat, ahol az új nem terminálisok a terminálisokra mutatnak

Példa - áterminálisok

Eredeti:

$G_1 = (\{S, X, Y\},\; \{a, b\},\; S,\; R)$

$R = \{$

$S \to aXY$

$X \to bb \mid aY$

$Y \to Sa \mid b$

$\}$

Új:

(Zöld: átírt vagy új)

$G_2 = (\{S, X, Y, \green A, \green B\},\; \{a, b\},\; S,\; R)$

$R = \{$

$S \to \green{A}XY$

$X \to \green{BB} \mid \green{A}Y$

$Y \to S\green{A} \mid \green{B}$

$\green{A \to a}$

$\green{B \to b}$

$\}$