Környezetfüggetlen grammatikák, Chomsky normálforma, CYK algoritmus

• Környezetfüggetlen grammatikák, Chomsky normálforma, CYK algoritmus
  • Redukált grammatika
  • Chomsky normálforma
  • Környezetfüggetlen
  • Források

Egy $G=⟨N,\Sigma ,P,S⟩$ környezetfüggetlen grammatika szabályai $A\to u$ alakúak, ahol $A\in N,i\in (\Sigma \cup N{)}^{\ast }$

Egy $G=⟨N,\Sigma ,P,S⟩$ környezetfüggetlen grammatika egy $X\in N$ nemterminálisát aktívnak mondjuk, ha van olyan $w\in {\Sigma }^{\ast }$ terminális szó, amire $X⟹w$ teljesül. Egyébként $X$-et inaktív nevezzük.

Egy $G=⟨N,\Sigma ,P,S⟩$ környezetfüggetlen grammatika egy $Y\in N$ nemterminálisát elérhetőnek nevezzük, ha léteznek olyan $v_1,v_2\in (N\cup \Sigma {)}^{\ast }$ szavak, amelyekre $S⟹v_{1}Y{v}_2$ teljesül. Egyébként $Y$-t elérhetetlennek (nem elérhetőnek) mondjuk.

Egy $G$ környezetfüggetlen grammatika egy nemterminálisát hasznosnak nevezzük, ha aktív és elérhető. $G$ redukált, ha minden nemterminálisa hasznos.

Redukált grammatika

Minden környezetfüggetlen $G$ grammatikához létezik vele ekvivalens redukált $G^{\prime }$ környezetfüggetlen grammatika.

Lépések:

1. inaktívak elhagyása
2. elérhetetlenek elhagyása

Chomsky normálforma

Egy $G=⟨N,\Sigma ,P,S⟩$ grammatika Chomsky normálformájú, ha minden $P$-beli szabály alakja a következők valamelyike:

• $S\to ϵ$
• $A\to BC,A,B,C\in N$ továbbá $B,C\ne S$, ha $S\to ϵ\in P$
• $A\to a,A\in N,a\in \Sigma$

Minden $G$ környezetfüggetlen grammatikához létezik vele ekvivalens Chomsky normálformájú grammatika

Lépések:

1. álterminálisok bevezetése
2. hosszredukció
3. $ϵ$-mentesítés
4. láncmentesítés

Környezetfüggetlen grammatikák szóproblémája

Legyen $G$ egy környezetfüggetlen grammatika és egy $u\in {\Sigma }^{\ast }$ egy szó. Eldönthető, hogy $u\in L(G)$

A naiv algoritmzs csak exponenciális felső becslést adhatunk a szóprobléma eldöntésének hatékonységéra.

Dinamikus programozás segítségével megalkotott algoritmus már polinomiális lesz.

A CYK algoritmus Chomsky normálformában adott grammatika esetében $|G|\cdot n^3$ nagyságrendűű lépésben eldönti a szóproblémát.

Tetszőleges környezetfüggetlen grammatika esetén tehát a Chomsky normálformára hozással kombinálva a CYK algoritmus hatékonysága $|G{|}^2\cdot n^3$

Források

• Diasor
• Felvétel