Kontekstno neodvisna gramatika

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Kontekstno neodvisna gramatika je četverica G = (N,T,P,S), pri čemer je

Običajno pravila p = (n,w) pišemo v obliki n ::= w. Obstaja tudi dogovor, da pravila z enako levo stranjo zružimo v eni vrsti.

Namesto

n ::= w1
n ::= w2
n ::= w3

pišemo krajše

n ::= w1 | w2 | w3

Takemu zapisu pravil pravijo tudi oblika BNF. Pravila gramatike lahko uporabljamo nad besedami, ki vsebujejo tudi kakšen neterminal. Če je beseda oblike unv, jo z uporabo pravila n ::= w lahko prevedemo na besedo uwv. To lahko zapišemo kot unv → uwv. Relaciji, ki jo dobimo s tranzitivno ovojnico relacije → pa rečemo izpeljava in jo označimo z ⇒.

Vsaka gramatika G definira jezik L(G) nad abecedo terminalnih znakov T.

L(G) sestavljajo tiste besede iz T*, ki jih lahko izpeljemo iz aksioma gramatike G.

Drevo izpeljave

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Vsak izpeljavi S ⇒ w lahko priredimo drevo izpeljave. Če za kakšno besedo obstajata dve različni drevesi izpeljave pravimo, da je gramatika dvoumna.

Zgled

Jezik pravilno oblikovanih oklepajnih izrazov:

T = {(,)}
L = { ε,(),(()),()(),()(()),()()(),(())(),((())), ...}

Jezik L lahko generiramo z gramatikio G, ki ima le tri pravila:

S ::= ε|(S)|SS

Žal je ta gramatika dvoumna. Npr. besedo ε lahko izpeljemo vsaj na dva načina:

S → ε
S → SS → Sε → ε
Osebna orodja