WikiSysop: Bot: Automatska zamjena teksta (-{{cite book +{{Citiranje knjige)

2021-11-17T05:21:23Z

Bot: Automatska zamjena teksta (-{{cite book +{{Citiranje knjige)

←Starija inačica		Inačica od 17. studeni 2021. u 05:21
Redak 164:		Redak 164:
	{{izvori}}		{{izvori}}

	* {{~~cite book~~		* {{Citiranje knjige
	\|author = [[Michael Sipser]]		\|author = [[Michael Sipser]]
	\| year = 1997		\| year = 1997
Redak 171:		Redak 171:
	\| id = {{ISBN\|0-534-94728-X}}}}		\| id = {{ISBN\|0-534-94728-X}}}}

	*{{~~cite book~~		*{{Citiranje knjige
	\| author = Siniša Srbljić		\| author = Siniša Srbljić
	\| title = Jezični procesori 1		\| title = Jezični procesori 1

WikiSysop: Bot: Automatski unos stranica

2021-08-20T01:30:03Z

Bot: Automatski unos stranica

Nova stranica

U [[lingvistika|lingvistici]] i [[računarstvo|računarstvu]], '''kontekstno neovisna gramatika (KNG)''' (rjeđe još i '''kontekstno slobodna gramatika''' ili '''gramatika neovisna o sadržaju''', te još i '''bezokolinska gramatika'''<ref name="InfoRjecnik">Kiš Miroslav, ''Englesko-hrvatski i hrvatsko-engleski informatički rječnik'', Zagreb, Naklada Ljevak, 2000., str. 234</ref>) je [[formalna gramatika]] u kojoj je svaka produkcija oblika
:V → ''w''
gdje je V [[Završni i nezavršni znakovi|nezavršni znak]] a ''w'' niz znakova (string) koji se sastoji od završnih i/ili nezavršnih znakova. Termin "kontekstno neovisna" izražava činjenicu da će nezavršni znak V uvijek biti zamijenjen nizom znakova ''w'' neovisno o kontekstu u kojem se pojavljuje. [[Formalni jezik]] je [[kontekstno neovisni jezik]] ako postoji kontekstno neovisna gramatika koja ga generira.

Kontekstno neovisne gramatike su dovoljno moćne da opišu [[sintaksa|sintaksu]] većine [[programski jezik|programskih jezika]]; ustvari sintaksa većine programskih jezika i jest specificirana koristeći kontekstno neovisne gramatike. U drugu ruku, kontekstno neovisne gramatike su dovoljno jednostavne da dozvole izgradnju učinkovitih algoritama parsiranja koji, za dani niz znakova, određuju može li se i kako niz generirati iz gramatike. Earleyjev parser je primjer takvog algoritma, dok [[LL pareser|LL]] i [[LR parser]]i barataju tek sa nešto ograničenim podskupovima kontekstno neovisnih gramatika.

BNF ([[Backus-Naurov oblik]]) je najuobičajenija notacija korištena za izražavanje kontekstno neovisnih gramatika.

Nisu svi formalni jezici kontekstno neovisni; dobro poznat protuprimjer je <math> \{ a^n b^n c^n : n \ge 0 \} </math>, skup svih nizova znakova koji sadrže jednak broj znakova a, nakon kojeg slijedi jednak broj znakova b i jednak broj znakova c.

== Formalna definicija ==
Baš kao i svaka [[formalna gramatika]], kontekstno neovisna gramatika G se može definirati kao uređena četvorka:

<math>G = (V_t, V_n, P, S)</math>
gdje je

*<math>V_t</math> konačan skup završnih znakova
*<math>V_n</math> konačan skup nezavršnih znakova
*<math>P</math> konačan skup pravila produkcija
*<math>S</math> je element skupa <math>V_n</math>, istaknuti početni nezavršni znak
*elementi skupa <math>P</math> su oblika
::<math>V_n \longrightarrow (V_t \cup V_n)^*</math>

Za jezik L kažemo da je kontekstno neovisni jezik (KNJ) ako je njegova gramatika kontekstno neovisna. Preciznije, to je jezik čije su riječi, rečenice i fraze načinjene od znakova i riječi iz kontekstno neovisne gramatike. Obično je KNJ oblika L=L(G). Dolje su dani primjeri za KNG ali ne i za KNJ.

== Primjeri ==
=== Primjer 1 ===
Jednostavna kontekstno neovisna gramatika je zadana sa:
:S → aSb | ε
gdje je znak | korišten kao separator višestrukih opcija za isti nezavršni znak, a ε stoji za [[prazni niz]].
Ova gramatika generira jezik
<math> \{ a^n b^n : n \ge 0 \} </math>
koji nije [[regularni jezik|regularan]].

=== Primjer 2 ===
Slijedi kontekstno neovisna gramatika za sintaktički ispravne infiksne algebarske izraze nad varijablama x, y i z:
:S → x | y | z | S + S | S - S | S * S | S/S | (S)

Ova gramatika može, na primjer, generirati niz znakova "( x + y ) * x - z * y / ( x + x )".

Ova gramatika je [[nejednoznačna gramatika|nejednoznačna]], što znači da može generirati isti niz znakova sa više različitih stabala parsiranja.

=== Primjer 3 ===
Kontekstno neovisna gramatika za jezik koji se sastoji od svih nizova znakova nad abecedom {a,b} koji sadrže različit broj znakova a i b jest
:S → U | V
:U → TaU | TaT
:V → TbV | TbT
:T → aTbT | bTaT | ε
Ovdje T može generirati sve nizove znakova sa jednakim brojem znakova a i b, U generira sve nizove znakova koji sadrže više znakova a nego b, dok V generira sve nizove znakova koji sadrže manje znakova a nego b.

=== Primjer 4 ===
Drugi primjer kontekstno neovisnog jezika jest <math> \{ b^n a^m b^{2n} : n \ge 0, m \ge 0 \} </math>. Ovo nije regularan jezik, ali je kontekstno neovisan i može ga generirati sljedeća kontekstno neovisna gramatika:
:S → bSbb | A
:A → aA | ε

=== Drugi primjeri ===
Kontekstno neovisne gramatike nisu ograničene isključivo u primjeni na matematičke ("formalne") jezike.
Na primjer, postoje indicije da je klasa tamilske poezije zvana Venpa upravljana kontekstno neovisnom gramatikom.<ref>
{{citiranje knjige
| first = BalaSundaraRaman
| last = L
| authorlink =
| coauthors = Ishwar.S, Sanjeeth Kumar Ravindranath
| date = 2003-08-22
| title = Context Free Grammar for Natural Language Constructs - An implementation for Venpa Class of Tamil Poetry
| booktitle = Proceedings of Tamil Internet, Chennai, 2003
| editor =
| others =
| edition =
| publisher = International Forum for Information Technology in Internet
| location =
| pages = 128-136
| url = http://citeseer.ist.psu.edu/balasundararaman03context.html
| format =
| accessdate = 2006-08-24
| doi =
| id =
}}</ref>

== Produkcije i sintaksna stabla ==
Postoje dva uobičajena načina za opis načina na koji se dani niz znakova može izvesti iz početnog nezavršnog znaka dane gramatike. Najjednostavniji način jest navesti uzastopne nizove znakova, počinjući sa početnim nezavršnim znakom i završujući sa nizom znakova, te produkcijskim pravilima koja su primijenjena. Ako uvedemo strategiju "uvijek prvo zamijeni krajnji lijevi nezavršni znak", tada za je za kontekstno neovisne gramatike sama lista primijenjenih produkcijskih pravila dovoljna. Ova se tehnika zove ''postupak generiranja niza zamjenom krajnje lijevog nezavršnog znaka'' (engl. ''leftmost derivation''). Na primjer, ako razmatramo sljedeću gramatiku:
: (1) S → S + S
: (2) S → 1
: (3) S → a

i niz znakova "1 + 1 + a", tada tom tehnikom dobijemo listu produkcijskih pravila [ (1), (1), (2), (2), (3) ]. Analogno možemo definirati ''postupak generiranja niza zamjenom krajnje desnog nezavršnog znaka'' (engl. ''rightmost derivation''). U tom slučaju lista glasi [ (1), (3), (1), (2), (2)].

Razlika između postupaka generiranja zamjenom krajnje lijevog i krajnje desnog nezavršnog znaka je važna pošto je za većinu [[parsiranje|parsera]] transformacija ulaznog niza znakova definirana davanjem dijela koda za svaku produkciju gramatike koji se izvršava kadgod je produkcija primijenjena. Stoga je važno znati odlučuje li parser primjenom tehnike zamjene krajnje lijevog ili krajnje desnog nezavršnog znaka, pošto ova odluka određuje redoslijed izvršavanja dijelova koda. Za detalje pogledati na primjer [[LL parser]]e i [[LR parser]]e.

Produkcija također na neki način nameće hijerarhijsku strukturu izvedenog niza znakova. Na primjer, struktura niza znakova "1 + 1 + a" bi, sudeći po postupku generiranja niza zamjenom krajnje lijevog nezavršnog znaka, bila:

:S→S+S (1)
:S→S+S+S (1)
:S→1+S+S (2)
:S→1+1+S (2)
:S→1+1+a (3)

: { { { 1 }S + { 1 }S }S + { a }S }S
gdje { ... }S označava podniz koji je prepoznat da pripada skupu S. Ova se hijerarhija također može shvatiti kao stablo:

S
/|\
/ | \
/ | \
S '+' S
/|\ |
/ | \ |
S '+' S 'a'
| |
'1' '1'

Ovo se stablo zove ''konkretno sintaksno stablo'' (vidi također [[apstraktno sintaksno stablo]]) niza znakova. U ovom slučaju predstavljeni postupci generiranja zamjenom krajnje lijevog i desnog nezavršnog znaka definiraju isto sintaksno stablo, iako se međutim isti niz znakova može generirati još jednim postupkom generiranja zamjenom krajnje lijevog nezavršnog znaka

:S→ S + S (1)
:S→ 1 + S (2)
:S→ 1 + S + S (1)
:S→ 1 + 1 + S (2)
:S→ 1 + 1 + a (3)

koji definira sljedeće sintaksno stablo:

S
/|\
/ | \
/ | \
S '+' S
| /|\
| / | \
'1' S '+' S
| |
'1' 'a'

Ako za neke nizove znakova jezika gramatike postoji više od jednog stabla parsiranja, tada za gramatiku kažemo da je [[nejednoznačna gramatika]]. Takve gramatike je obično teško parsirati jer parser ne može uvijek odlučiti koje pravilo gramatike treba primjeniti.

== Normalne forme ==
Svaka kontekstno neovisna gramatika koja ne generira prazni niz se može preoblikovati u istovjetnu gramatiku u [[Chomskyjev normalni oblik|Chomskyjevom normalnom obliku]] ili [[Greibachov normalni oblik|Greibachovom normalnom obliku]]. Ovdje "istovjetan" označava da gramatike generiraju iste jezike.

Zbog osobito jednostavnog oblika produkcija gramatika u Chomskyjevom normalnom obliku, ovaj normalni oblik ima i teoretske i praktične implikacije. Na primjer, za danu kontekstno neovisnu gramatiku se Chomskyjev normalni oblik može iskoristiti za konstrukciju polinomnog algoritma koji odlučuje pripada li dani niz znakova jeziku kojeg gramatika generira ili ne (CYK algoritam).

== Neodlučivi problemi ==
Iako su neke operacije nad kontekstno neovisnim gramatikama odlučive zbog njihove ograničene moći, KNG imaju nekih zanimljivih neodlučivih problema. Jedan od najjednostavnijih i najpoznatijih jest problem odlučivanja generira li KNG jezik svih nizova znakova. Može se demonstrirati redukcija na ovaj problem iz dobro poznatog neodlučivog problema određivanja prihvaća li [[Turingov stroj]] neki pojedinačni ulaz. Ta redukcija koristi koncept ''povijesti izračuna'', niz znakova koji u cijelosti opisuje tijek izračuna (komputacije) Turingovog stroja. Možemo konstruirati KNG koja generira sve nizove znakova koji nisu prihvatljive povijesti izračuna za neki pojedinačni Turingov stroj za neki pojedinačni ulaz, te će stoga KNG generirati sve nizove znakova samo ako stroj ne prihvaća taj ulaz.

Kao posljedica toga, također je neodlučivo opisuju li dvije KNG isti jezik, pošto ionako ne možemo odlučiti je li KNG istovjetna trivijalnoj KNG koja odlučuje jezik svih nizova znakova.

U drugu ruku, problem određivanja prihvaća li KNG barem jedan niz znakova jest odlučiv.

Također je korisni napomenuti da je problem određivanja opisuje li [[kontekstno ovisna gramatika]] kontekstno neovisan jezik također neodlučiv.

== Svojstva kontekstno neovisnih jezika ==
* Alternativna i istovjetna definicija kontekstno neovisnih jezika koristi nedeterminističke [[potisni automat|potisne automate]]: jezik je kontekstno neovisan ako i samo ako ga takav automat može prihvatiti.
* Jezik se također može modelirati kao skup svih slijedova završnih znakova koje gramatika generira. Ovaj model je koristan u razumijevanju skupovnih operacija nad jezicima.
* Unija i nadovezivanje (konkatenacija) dvaju kontekstno neovisnih jezika je kontekstno neovisan jezik, ali presjek ne mora biti.
* Prevrtanje kontekstno neovisnog jezika je kontekstno neovisan jezik, ali komplement ne mora biti.
* Svaki [[regularni jezik]] je kontekstno neovisan pošto može biti opisan [[regularna gramatika|regularnom gramatikom]].
* Presjek kontekstno neovisnog jezika i regularnog jezika je uvijek kontekstno neovisan.
* Postoje [[kontekstno ovisni jezik|kontekstno ovisni jezici]] koji nisu kontekstno neovisni.
* Da bi se dokazalo da je dani jezik kontekstno ovisan, može se koristiti [[svojstvo napuhavanja]] za kontekstno ovisne jezike.

== Vidi još ==
* [[Formalna gramatika]]

== Izvori ==

{{izvori}}

* {{cite book
|author = [[Michael Sipser]]
| year = 1997
| title = Introduction to the Theory of Computation
| publisher = PWS Publishing
| id = {{ISBN|0-534-94728-X}}}}

*{{cite book
| author = Siniša Srbljić
| title = Jezični procesori 1
| publisher = Element
| year = 2003
| id = {{ISBN|953-197-129-3}}}}

{{Formalni jezici i gramatike}}

[[Kategorija:Formalni jezici]]

Kontekstno neovisna gramatika - Povijest promjena

WikiSysop: Bot: Automatska zamjena teksta (-{{cite book +{{Citiranje knjige)

WikiSysop: Bot: Automatski unos stranica