Kontekstno neovisni jezik - Povijest promjena

WikiSysop: bnz

2022-03-22T12:18:50Z

bnz

←Starija inačica		Inačica od 22. ožujak 2022. u 12:18
Redak 1:		Redak 1:
	~~<!--'''Kontekstno neovisni jezik'''-->'''~~Kontekstno neovisni jezik''' (rjeđe još i '''kontekstno slobodni jezik''' ili '''jezik neovisan o sadržaju''', te još i '''bezokolinski jezik'''<ref name="InfoRjecnik">Kiš Miroslav, ''Englesko-hrvatski i hrvatsko-engleski informatički rječnik'', Zagreb, Naklada Ljevak, 2000., str. 234</ref>) je [[formalni jezik]] koji je element skupa jezika kojeg definiraju [[kontekstno neovisna gramatika\|kontekstno neovisne gramatike]]. Skup kontekstno neovisnih jezika je identičan skupu jezika koje prihvaćaju [[potisni automat]]i.		Kontekstno neovisni jezik''' (rjeđe još i '''kontekstno slobodni jezik''' ili '''jezik neovisan o sadržaju''', te još i '''bezokolinski jezik'''<ref name="InfoRjecnik">Kiš Miroslav, ''Englesko-hrvatski i hrvatsko-engleski informatički rječnik'', Zagreb, Naklada Ljevak, 2000., str. 234</ref>) je [[formalni jezik]] koji je element skupa jezika kojeg definiraju [[kontekstno neovisna gramatika\|kontekstno neovisne gramatike]]. Skup kontekstno neovisnih jezika je identičan skupu jezika koje prihvaćaju [[potisni automat]]i.

	== Primjeri ==		== Primjeri ==

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

2021-11-17T05:22:02Z

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

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

	* {{~~cite book~~		* {{Citiranje knjige
	\|author = [[Michael Sipser]]		\|author = [[Michael Sipser]]
	\| year = 1997		\| year = 1997
Redak 36:		Redak 36:
	\| 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:28:12Z

Bot: Automatski unos stranica

Nova stranica

'''Kontekstno neovisni jezik''' (rjeđe još i '''kontekstno slobodni jezik''' ili '''jezik neovisan o sadržaju''', te još i '''bezokolinski jezik'''<ref name="InfoRjecnik">Kiš Miroslav, ''Englesko-hrvatski i hrvatsko-engleski informatički rječnik'', Zagreb, Naklada Ljevak, 2000., str. 234</ref>) je [[formalni jezik]] koji je element skupa jezika kojeg definiraju [[kontekstno neovisna gramatika|kontekstno neovisne gramatike]]. Skup kontekstno neovisnih jezika je identičan skupu jezika koje prihvaćaju [[potisni automat]]i.

== Primjeri ==
Kanonski primjer kontekstno neovisnog jezika jest <math>L = \{a^nb^n:n\geq1\}</math>, jezik svih nepraznih nizova znakova (simbola) parne duljine, čiju prvu polovicu čine znakovi <math>a</math>, dok drugu polovicu čine znakovi <math>b</math>. <math>L</math> generira gramatika <math>S\to aSb ~|~ ab</math> te prihvaća potisni automat <math>M=(\{q_0,q_1,q_f\}, \{a\}, \{a,b,z\}, \delta, q_0, \{q_f\})</math> gdje je funkcija prijelaza <math>\delta</math> definirana na sljedeći način:

<center>
<math>\delta(q_0, a, z) = (q_0, a)</math><br>
<math>\delta(q_0, b, ax) = (q_1, x)</math><br>
<math>\delta(q_1, b, ax) = (q_1, x)</math><br>
<math>\delta(q_1, b, bz) = (q_f, z)</math><br>
</center>

Kontekstno neovisni jezici imaju mnoge primjene u [[programski jezik|programskim jezicima]]; na primjer - jezik svih pravilno uparenih zagrada generira gramatika <math>S\to SS ~|~ (S) ~|~ \lambda</math>. Također, većinu aritmetičkih izraza mogu generirati kontekstno neovisne gramatike.

== Svojstva zatvorenosti ==

Kontekstno neovisni jezici su zatvoreni nad sljedećim operacijama. To jest, ako su ''L'' i ''P'' kontekstno neovisni jezici i ''D'' je [[regularni jezik]], sljedeći jezici su također kontekstno neovisni:

* [[Kleeneov operator]] <math>L^*</math> nad jezikom ''L''
* homeomorfizam φ(L) jezika ''L''
* nadovezivanje (konkatenacija) <math>L \circ P</math> jezika ''L'' i jezika ''P''
* unija <math>L \cup P</math> jezika ''L'' i jezika ''P''
* presjek (sa regularnim jezikom) <math>L \cap D</math> jezika ''L'' i jezika ''D''

Kontekstno neovisni jezici nisu zatvoreni nad operacijama komplementa, presjeka i razlike.

== 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]]