2. gyakorlat
Chomsky normálformára hozás lépései
3) Hosszredukció
Mit csinálunk?
- Egy szabály akkor számít túl hosszúnak, ha a jobb oldala hosszabb, mint 2
- Ekkor addig bontjuk az adott szabályt új terminálisok behozásával, amíg max. 2 nem lesz a szabály jobb oldal hossza
Példa - hr - 1
\(S \to A \blue{XBY}\)
\(\leadsto\)
\(S \to A\blue{D}\)
\(\blue{D} \to X\green{BY}\)
\(\leadsto\)
\(S \to AD\)
\(D \to X\green{E}\)
\(\green{E} \to BY\)
4) \(\varepsilon\)-mentesítés
Mit csinálunk?
-
Keressük meg az epsilon-t tartalmazó szabályokat
-
Honnan jutunk el oda? A szabály bal oldalát kivesszük az \(U_1\)-be
-
Honnan jutunk el csak olyan karakterekhez, amik az \(U_1\)-ben szerepelnek? Azok bal oldalát is hozzávesszük az \(U_1\)-hez és ez az \(U_2\)
-
Így tovább, amíg \(U_n \neq U_{n-1}\)
-
Utána a szabályok közül kihúzzuk a sima epsilonra vezetőket (a többi szabály közül nem húzunk ki)
-
A többi érintett szabályra (részben az utolsó U-ban szereplő karakterre vezet) a meglévő mellé felveszünk olyan szabályokat, hogy minden lehetséges módon elhagyjuk az U-ban szereplő karaktereket
-
Ha csak U-ban szereplő karakterre vezet, akkor a szabály marad
-
Ha a start szimbólum szerepel az U-ban, akkor egy start szimbólum -> \(\varepsilon\) szabályt vegyünk fel
5) Láncmentesítés
Mit csinálunk?
Első: táblázat készítése
-
Itt most ne vegyük figyelembe azokat a szabályokat, ahol 1-nél hosszabb a jobb oldal
-
Írjuk fel a táblázatba a bal oldalon szereplő karaktereket
-
Megnézzük, hogy melyikből melyikbe lehet eljutni (ha nincs, akkor vége a láncnak)
Második: láncok felírása
-
Csak azok a szabályok kerülnek a láncokba, amik terminálisra vezetnek vagy ha nem, akkor több mint egy karakterből állnak
-
Felírjuk az összes olyan szabályt, ami azokból jön, amiket a táblázatba az adott bal oldalon álló karakterhez felírtunk
-
Azok a szabályok is maradnak, amik terminálisra vezetnek
Feladat 1
\(G = (\{S\}, \{a, b\}, S, \{S \to aSa \mid bSb \mid aa \mid bb\})\)
Milyen nyelvet generál a grammatika?
L(G) = {uu^-1: u \in {a, b}^+}
---
Hosszredukció
\(G = (\{S, A, B, C, D\}, \{x, y, z\}, S, \{S \to ABCD, A \to BCD, B \to ABC \mid x, C \to AB \mid y, D \to CD \mid z\})\)
G' = ({S, A, B, C, D, E, F, G, H}, {x, y, z}, S, {S \to AE, E \to BF, F \to CD, A \to BG, G \to CD, B \to AH | x}) todo
\(G'' = (\{S, A, B, C, D, E, F\}, \{x, y, z\}, S, \{S \to EF, E \to AB, F \to CD, A \to BF, B \to EC \mid x, C \to AB \mid y, D \to CD \mid z\})\)
A szabályok jobb oldalán legfeljebb két nem terminális van
\(\varepsilon\)-mentesítés
\(G = (\{S, A, B, C, D\}, \{x, y, z\}, s, \{S \to AB, A \to CC \mid BD \mid x, B \to CA \mid y, C \to z \mid \varepsilon, D \to x\})\)
\(u_1 = \{C\}\)
\(u_2 = \{C, A\}\)
\(u_3 = \{C, A, B\}\)
\(u_4 = \{C, A, B, S\}\)
\(u_5 = u_4 = \{C, A, B, S\}\)
\(G' = \left(\{S, A, B, C, D\}, \{x, y, z\}, S, \{S \to AB \mid B \mid A \mid \varepsilon, A \to CC \mid C \mid BD \mid D \mid x, B \to CA \mid C \mid A \mid y, C \to z, D \to x\}\right)\)
Láncmentesítés (5)
\(G = (\{S, A, B, C, D\}, \{x, y, z\}, s, \{S \to AB \mid B \mid A \mid \varepsilon, A \to cc \mid C \mid BD \mid D \mid x, B \to CA \mid C \mid A, C \to z, D \to x\})\)
| x | S | A | B | C | D |
|---|---|---|---|---|---|
| L(x) | \(\{S, A, B, C, D\}\) | \(\{A, C, D\}\) | \(\{A, B, C, D\}\) | \(\{C\}\) | \(\{D\}\) |
\(G' = (\{S, A, B, C, D\}, \{x, y, z\}, S, \{S \to AB \mid \varepsilon \mid CC \mid BD \mid x \mid CA \mid y \mid z, A \to CC \mid BD \mid x \mid z, B \to CC \mid BD \mid x \mid CA \mid y \mid z, C \to z, D \to x\})\)
Feladat 2
Hajtsd végre az epszilonmenetsítlést az alábbi grammatikán!
\(G_1 = (\{S, A, B, C, D, E\}, \{x, y, z\}S, \{\)
\(S \to AB \mid CD\)
\(A \to BE \mid CE \mid x\)
\(B \to AD \mid y\)
\(C \to AD \mid EE\)
\(D \to z\)
\(E \to \varepsilon\)
\(\})\)
\(U_1 = \{E\}\)
\(U_2 = \{E, C\}\)
\(U_3 = \{E, C, A\}\)
\(U_4 = \{A, C, E\}\)
\(G_1' = (\{S, A, B, C, D, E\}, \{x, y, z\}S, \{\)
\(S \to AB \mid B \mid CD \mid D\)
\(A \to BE \mid B \mid CE \mid C \mid E \mid x\)
todo
\(B \to AD \mid y\)
\(C \to AD \mid EE\)
\(D \to z\)
\(E \to \varepsilon\)
\(\})\)
CYK algoritmus (Chomsky algoritmus ?)
Hatékony algoritmus annak eldöntésére, hogy egy Chomsky normálformás szó generál-e TODO
\(S \to AB \mid BC\)
\(A \to BB \mid a\)
\(B \to CC \mid b\)
\(C \to SA \mid a \mid b\)
[kép]
\(S \Longrightarrow AB\)
TODO
Feladat (mittoménhány)
CYK algoritmus segítségével határozd meg, hogy az \(aabba\) szót tudja-e generálni az alábbi grammatika, és ha igen, akkor add meg egy lehetséges levezetését:
\(G_2 = (\{S, A, B, C, D\}, \{a, b\}, S, \{\})\)
\(S \to AC \mid BD\)
\(A \to BB \mid CC \mid a\)
\(B \to SA \mid DS \mid b\)
\(C \to AD \mid CA \mid a\)
\(D \to BA \mid CB \mid b\)
[kép]