Környezetfüggő grammatikák

• Környezetfüggő grammatikák
  • Kuroda normálforma
  • A környezetfüggő nyelvek szóproblémája
  • Egy 0-típusú normálforma
  • Források

Egy $G=⟨N,\Sigma ,P,S⟩$ grammatikát hossz-nemcsökkentőnek mondunk, ha minden szabályának alakjára az alábbiak valamelyike teljesül:

• $S\to ϵ$, de ha van ilyen szabály, $S$ nem lehet szabály jobb oldalán
• $u\to v$, ahol $u,v\in (\Sigma \cup N{)}^{+}$ és $|u|\le |v|$

Minden hossz-nemcsökkentő grammatika környezetfüggő nyelvet generál.

Következmény: ${\mathcal{L}}_2\subset {\mathcal{L}}_1$

Kuroda normálforma

Egy $G$ grammatikát Kuroda normálformájúnak mondunk, ha minden szabályának alakjára az alábbiak valamelyike teljesül:

• $S\to ϵ$, de ha van ilyen szabály, $S$ nem lehet més szabály jobb oldalán.
• $A\to a$
• $A\to BC$
• $AB\to AC$
• $BA\to CA$

Minen környezetfüggő $G$ grammatikához van vele ekvivalens Kuroda normálformájú $G^{\prime }$ grammatika.

A környezetfüggő nyelvek szóproblémája

Eldönthető, egy $G$ hossz-nemcsökkentő grammatika és $u\in {\Sigma }^{\ast }$ szó esetén $u\in L(G)$.

Egy 0-típusú normálforma

Bármely $G$ 0-típusú grammatikához van vele ekvivalens $G^{\prime }$ grammatika, ahol $G^{\prime }$ minden szabályának alakjára az alábbiak valamelyike teljesül:

• $S\to ϵ$, de ha van ilyen szabály, $S$ nem lehet más szabály jobb oldalán.
• $A\to a$
• $A\to B$
• $A\to BC$
• $AB\to B$
• $AB\to AC$
• $BA\to CA$

Források

• Diasor