4. gyakorlat
\(L(A) = \{uvu^{-1} : u \in \{a, b\}^*,\; v \in \{c, d\}^+,\; |v|_c = |v|_d \}\)
Feladat / 1
Mitől lesz egy grammatika Chomsky-normálformájú?
- Új start szimbólum bevezetése (start szimbólum ne szerepeljen szabály jobb oldalán) (KES szabály)
- Áldeterminálisok bevezetése
- Hossz redukció (ne legyen kettőnél több nem terminális a szabályok jobb oldalán)
- \(\varepsilon\)-mentesítés
- Láncmentesítés
Az eredetivel ekvivalens grammatikát kapunk.
\(G_1 = (\{S, A, B, C\}, \; \{x, y, z\}, \; S, \; *)\)
*
\(S \to AxBy\)
\(A \to BC \mid z\)
\(B \to CC \mid xy\)
\(C \to S \mid \varepsilon\)
Új start szimbólum
\(G_1 = (\{S', A, B, C\}, \; \{x, y, z\}, \; S', \; *)\)
*
\(S' \to S\) (ez új)
\(S \to AxBy\)
\(A \to BC \mid z\)
\(B \to CC \mid xy\)
\(C \to S \mid \varepsilon\) (emiatt kellett)
Ki lehet hagyni, ha nyílvánvaló, hogy a grammatika nem tudja generálni az üres szót. (itt nem)
Áldeterminálisok bevezetése
(Itt nem vezettünk be új start szimbólumot)
\(G_1' = (\{S, A, B, C\}, \; \{x, y, z\}, \; S, \; *)\)
*
\(S \to AXBY\)
\(A \to BC \mid z\)
\(B \to CC \mid XY\)
\(C \to S \mid \varepsilon\)
\(X \to x\)
\(Y \to y\)
Hossz redukció
(Itt nem vezettünk be új start szimbólumot)
\(G_1' = (\{S, A, B, C, D, E, X, Y\}, \; \{x, y, z\}, \; S, \; *)\)
*
\(S \to AD\) (ezt rövidítettük le)
\(A \to BC \mid z\)
\(B \to CC \mid XY\)
\(C \to S \mid \varepsilon\)
\(D \to XE\)
\(E \to BY\)
\(X \to x\)
\(Y \to y\)
\(\varepsilon\)-mentesítés
(Itt nem vezettünk be új start szimbólumot)
\(G_1' = (\{S, A, B, C, D, E, X, Y\}, \; \{x, y, z\}, \; S, \; *)\)
*
\(S \to AD \mid D\)
\(A \to BC \mid B \mid C \mid z\)
\(B \to CC \mid C \mid XY\)
\(C \to S\)
\(D \to XE\)
\(E \to BY \mid Y\)
\(X \to x\)
\(Y \to y\)
Láncmentesítés
(Itt nem vezettünk be új start szimbólumot)
\(G_1' = (\{S, A, B, C, D, E, X, Y\}, \; \{x, y, z\}, \; S, \; \text{szabályok *})\)
* Szabályok:
\(S \to AD \mid XE\)
\(A \to BC \mid CC \mid XY \mid AD \mid XE \mid z\)
\(B \to CC \mid AD \mid XE \mid XY\)
\(C \to AD \mid XE\)
\(D \to XE\)
\(E \to BY \mid y\)
\(X \to x\)
\(Y \to y\)
ZH
- min. 20 pont kell
- 5 feladat (10 pont / feladat)
- Témák:
- Chomsky normál formára hozás egyes lépései
- CYK algoritmus
- Veremautomaták