WikiSysop: bnz

2022-05-08T14:11:56Z

bnz

←Starija inačica		Inačica od 14:11, 8. svibnja 2022.
Redak 1:		Redak 1:
	~~<!--'''Chomskyjev normalni oblik'''-->~~U [[računarstvo\|računarstvu]], [[formalna gramatika]] je u '''Chomskyjevom normalnom obliku''' ako i samo ako ima sve produkcije u obliku:		U [[računarstvo\|računarstvu]], [[formalna gramatika]] je u '''Chomskyjevom normalnom obliku''' ako i samo ako ima sve produkcije u obliku:

	:''A'' → ''BC'' or		:''A'' → ''BC'' or

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

2021-11-16T06:42:21Z

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

←Starija inačica		Inačica od 06:42, 16. studenoga 2021.
Redak 33:		Redak 33:

	== Izvori ==		== Izvori ==
	* {{~~cite book~~		* {{Citiranje knjige
	\| authorlink = Michael Sipser		\| authorlink = Michael Sipser
	\| author = Michael Sipser		\| author = Michael Sipser
Redak 42:		Redak 42:
	}} Pages 98–101 of section 2.1: context-free grammars. Page 156.		}} Pages 98–101 of section 2.1: context-free grammars. Page 156.

	* {{~~cite book~~		* {{Citiranje knjige
	\| authorlink = John Martin		\| authorlink = John Martin
	\| author = John Martin		\| author = John Martin

WikiSysop: Bot: Automatski unos stranica

2021-08-20T01:02:40Z

Bot: Automatski unos stranica

Nova stranica

U [[računarstvo|računarstvu]], [[formalna gramatika]] je u '''Chomskyjevom normalnom obliku''' ako i samo ako ima sve produkcije u obliku:

:''A'' → ''BC'' or
:''A'' → α or
:''S'' → ε

gdje su ''A'', ''B'' i ''C'' [[završni i nezavršni znakovi|nezavršni znakovi]], α je [[završni i nezavršni znakovi|završni znak]] (znak koji predstavlja konstantnu vrijednost), ''S'' je početni znak i ε je [[prazni niz]]. Također, ni ''B'' niti ''C'' ne smiju biti početni znakovi.

Svaka gramatika u Chomskyjevom normalno obliku je [[kontekstno neovisna gramatika|kontekstno neovisna]], te sljedbeno tome, svaka kontekstno neovisna gramatika se može učinkovito svesti na istovjetnu gramatiku u Chomskyjevom normalnom obliku.

Sa iznimkom opcionalnog pravila ''S'' → ε (uključenog kad gramatika može generirati prazni niz), sva pravila gramatika u Chomskyjevom normalnom obliku su strogo ekspanzivna - prilikom prijelaza između međunizova za vrijeme geneiranja niza znakova, svaki međuniz završnih i nezavršnih znakova je uvijek ili iste duljine ili za jedan element veći od prethodnog međuniza. Generiranje niza znakova duljine n se uvijek obavlja u 2n-1 koraka. Štoviše, jer sve produkcije koje stvaraju nezavršne znakova transformiraju jedan nezavršni znak u točno dva nezavršna znaka, stablo parsiranja gramatike u Chomskyjevom normalnom obliku jest binarno stablo, a dubina ovog stabla ima gornju granicu jednaku duljini niza.

Zbog ovih svojstava, mnogi dokazi u području formalnih jezika i izračunljivosti koriste Chomskyjev normalni oblik. Ova svojstva mogu dovesti do raznih učinkovitih algoritama baziranih na gramatikama u Chomskyjevom normalnom obliku; npr. [[CYK algoritam]] koji odlučuje generira li dana gramatika dani niz znakova koristi Chomskyjev normalni oblik.

Chomskyjev normalni oblik je imenovan po [[Noam Chomsky|Noamu Chomskyu]], američkom jezikoslovacu, tvorcu [[Chomskyjeva hijerarhija jezika|Chomskyjeve hijerarhije]].

== Alternativne definicije ==

Neki autori definiraju Chomskyjev normalni oblik na malo drugačiji način:

[[Formalna gramatika]] je u '''Chomskyjevom normalnom obliku''' ako i samo ako ima sve produkcije u obliku:

:''A'' → ''BC'' or
:''A'' → α

gdje su ''A'', ''B'' i ''C'' nezavršni znakovi, a α [[završni i nezavršni znakovi|završni znak]]. Po ovoj definiciji ''B'' ili ''C'' mogu biti početni znakovi.

Ova se definicija razlikuje od prethodne u tom što unaprijed isključuje mogućnost da će gramatika generirati prazni niz, ε. Ostaje vrijedeće svojstvo da bilo koja [[kontekstno neovisna gramatika]] koja generira jezik ''L'' se može učinkovito svesti u gramatiku u Chomskyjevom normalnom obliku koja generira jezik ''L - {ε}''. Principijelna prednost potonje definicije jest što kao posljedica dokazi mogu biti marginalno jednostavniji, jer svaki korak u generiranju međunizova nikad neće smanjiti duljinu rezultirajućeg međuniza. Nedostatak je, dakako, posebna pažnja koju treba posvetiti ukoliko je izvorna gramatika generirala ε

== Vidjeti također ==
* [[Greibachov normalni oblik]]
* [[Kurodin normalni oblik]]

== Izvori ==
* {{cite book
| authorlink = Michael Sipser
| author = Michael Sipser
| year = 1997
| title = Introduction to the Theory of Computation
| publisher = PWS Publishing
| id = {{ISBN|0-534-94728-X}}
}} Pages 98–101 of section 2.1: context-free grammars. Page 156.

* {{cite book
| authorlink = John Martin
| author = John Martin
| year = 2003
| title = Introduction to Languages and the Theory of Computation
| publisher = McGraw Hill
| id = {{ISBN|0-07-232200-4}}
}} Pages 237–240 of section 6.6: simplified forms and normal forms.

[[Kategorija:Formalni jezici]]

Chomskyjev normalni oblik - Povijest promjena

WikiSysop: bnz

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

WikiSysop: Bot: Automatski unos stranica