Програмски преводиоци 1/К1 2015 - Историја измена

Pop: /* Rešenje */

2025-08-13T14:05:57Z

Rešenje

← Старија измена		Верзија на датум 13. август 2025. у 16:05
Ред 178:		Ред 178:

	=== Rešenje ===		=== Rešenje ===
	* <S> → a <S> b <A>		* <S> → a <S> <X>
	* <S> → a <A> b <A>		* <S> → a <M> <X>
	* <A> → c <A>		* <M> → c <M>
	* <A> → ε		* <M> → ε
	~~Ovo rešenje nije ispravno, jer ne garantuje da će pri svakom ponavljanju <math~~>b ~~c^k</math~~> ~~biti podjednak broj slova <math~~>c~~</math~~>~~. Ipak, nije poznato da li je uopšte moguće napisati bezkontekstnu gramatiku za jezik iz postavke zadataka, pa je ovo rešenje možda prihvatljivo.~~		* <X> → b <C>
			* <C> → c <C>
			* <C> → ε

	== 4. zadatak ==		== 4. zadatak ==

KockaAdmiralac: Formatiranje regularnih izraza

2022-10-31T15:29:54Z

Formatiranje regularnih izraza

← Старија измена		Верзија на датум 31. октобар 2022. у 17:29
Ред 187:		Ред 187:
	=== Postavka ===		=== Postavka ===
	<div class="abc-list">		<div class="abc-list">
	# Na osnovu regularnog izraza <math>(a* \| b*) c+</math>, konstruisati minimalni deterministički automat metodom pozicija.		# Na osnovu regularnog izraza <math>(a^* \| b^*) c^+</math>, konstruisati minimalni deterministički automat metodom pozicija.
	# Nacrtati graf NKA dobijenog transformacijom regularnog izraza <math>(a* \| b*)+</math> primenom Tompsonovog algoritma. Nije potrebno konstruisati minDKA.		# Nacrtati graf NKA dobijenog transformacijom regularnog izraza <math>(a^* \| b^*)^+</math> primenom Tompsonovog algoritma. Nije potrebno konstruisati minDKA.
	</div>		</div>

KockaAdmiralac: Ispravka da gramatika zapravo bude regularna

2022-10-31T15:26:29Z

Ispravka da gramatika zapravo bude regularna

← Старија измена		Верзија на датум 31. октобар 2022. у 17:26
Ред 165:		Ред 165:

	=== Rešenje ===		=== Rešenje ===
	* <S> → <A>		* <S> → a <A>
	* <S> → <B>		* <S> → b <B>
			* <S> → ε
	* <A> → a <A>		* <A> → a <A>
	* <A> → ε		* <A> → ε

KockaAdmiralac: Greška u prepisivanju

2022-10-31T15:09:41Z

Greška u prepisivanju

← Старија измена		Верзија на датум 31. октобар 2022. у 17:09
Ред 78:		Ред 78:
	\| B		\| B
	\| A		\| A
	\| 0		\| 1
	\|-		\|-
	! B		! B
	\| A		\| A
	\| B		\| B
	\| 1		\| 0
	\|}		\|}
	{\| class="wikitable"		{\| class="wikitable"

KockaAdmiralac: I malo veće slike

2022-10-31T14:07:03Z

I malo veće slike

← Старија измена		Верзија на датум 31. октобар 2022. у 16:07
Ред 191:		Ред 191:

	=== Rešenje ===		=== Rešenje ===
	<gallery class="transparent-svg">		<gallery class="transparent-svg" widths="500" heights="500">
	PPR K1 2015 zadatak 4 a.svg \| Sintaksno stablo u stavci pod a.		PPR K1 2015 zadatak 4 a.svg \| Sintaksno stablo u stavci pod a.
	PPR K1 2015 zadatak 4 b.svg \| Graf nedeterminističkog konačnog automata u stavci pod b.		PPR K1 2015 zadatak 4 b.svg \| Graf nedeterminističkog konačnog automata u stavci pod b.

KockaAdmiralac: Bela pozadina na

2022-10-31T14:06:28Z

Bela pozadina na <gallery>

← Старија измена		Верзија на датум 31. октобар 2022. у 16:06
Ред 191:		Ред 191:

	=== Rešenje ===		=== Rešenje ===
	<gallery>		<gallery class="transparent-svg">
	PPR K1 2015 zadatak 4 a.svg \| Sintaksno stablo u stavci pod a.		PPR K1 2015 zadatak 4 a.svg \| Sintaksno stablo u stavci pod a.
	PPR K1 2015 zadatak 4 b.svg \| Graf nedeterminističkog konačnog automata u stavci pod b.		PPR K1 2015 zadatak 4 b.svg \| Graf nedeterminističkog konačnog automata u stavci pod b.

KockaAdmiralac: Bez znaka za kraj sekvence u ulaznoj azbuci

2022-10-31T13:55:18Z

Bez znaka za kraj sekvence u ulaznoj azbuci

← Старија измена		Верзија на датум 31. октобар 2022. у 15:55
Ред 218:		Ред 218:
	! b		! b
	! c		! c
	~~! ─┤~~
	! Prihvata		! Prihvata
	\|-		\|-
Ред 225:		Ред 224:
	\| 2, 3		\| 2, 3
	\| 3, 4		\| 3, 4
	\|
	\| 0		\| 0
	\|-		\|-
Ред 232:		Ред 230:
	\|		\|
	\| 3, 4		\| 3, 4
	\|
	\| 0		\| 0
	\|-		\|-
Ред 239:		Ред 236:
	\| 2, 3		\| 2, 3
	\| 3, 4		\| 3, 4
	\|
	\| 0		\| 0
	\|-		\|-
Ред 246:		Ред 242:
	\|		\|
	\| 3, 4		\| 3, 4
	~~\| 4~~
	~~\| 0~~
	\|-
	~~! 4~~
	\|
	\|
	\|
	\|
	\| 1		\| 1
	\|}		\|}

KockaAdmiralac: Moja rešenja K1 2015

2022-10-31T13:15:08Z

Moja rešenja K1 2015

Нова страница

{{tocright}}
'''Prvi kolokvijum 2015. godine''' održan je 25. oktobra i trajao je 90 minuta. Postavka je dostupna [http://ir4pp1.etf.rs/Rokovi/2015-2016/si4pp1-1516-k1k2.zip sa stranice predmeta] (arhiva).

== 1. zadatak ==
=== Postavka ===
<div class="abc-list">
# Opisati korake generalnog postupka kojim se za dva proizvoljna deterministička automata sa istim ulaznim azbukama konstruiše automat koji prihvata sve sekvence koje prihvata i prvi automat i dodatno sve sekvence koje NE prihvata drugi automat (i nijednu više).
# Konstruisati minimalni deterministički konačni automat prema postupku opisanom pod a) za sledeća dva automata. Prikazati svaki korak postupka.
</div>
{| class="wikitable"
|+ Prvi automat
!
! x
! y
! Prihvata
|-
! → 0
| 1
| 0
| 1
|-
! 1
| 2
| 1
| 0
|-
! 2
| 2
| 0
| 0
|}
{| class="wikitable"
|+ Drugi automat
!
! x
! y
! Prihvata
|-
! → A
| B
| A
| 0
|-
! B
| A
| B
| 1
|}

=== Rešenje ===
Generalni postupak konstruisanja takvog automata jeste da se dva deterministička automata samo spoje, nova početna stanja postaju početna stanja oba automata a na drugom automatu se obrne šta su stanja prihvatanja a šta neprihvatanja kako bi se prihvatale sekvence koje drugi automat ne prihvata. Kako se ovim postupkom dobija nedeterministički konačni automat, potrebno je pretvoriti nedeterministički u deterministički konačni automat. Početno stanje se sastoji od početnih stanja oba automata, a stanja prihvatanja su sva stanja koje sadrže neko od stanja prihvatanja prethodnih automata.

Ispod je prikazan postupak konverzije gorenavedenih automata.

{| class="wikitable"
|+ Spojeni automati u jedan nedeterministički konačni automat
!
! x
! y
! Prihvata
|-
! → 0
| 1
| 0
| 1
|-
! 1
| 2
| 1
| 0
|-
! 2
| 2
| 0
| 0
|-
! → A
| B
| A
| 0
|-
! B
| A
| B
| 1
|}
{| class="wikitable"
|+ Konverzija nedeterminističkog u deterministički konačni automat
!
! x
! y
! Prihvata
|-
! 0, A
| 1, B
| 0, A
| 1
|-
! 1, B
| 2, A
| 1, B
| 0
|-
! 2, A
| 2, B
| 0, A
| 1
|-
! 2, B
| 2, A
| 0, B
| 0
|-
! 0, B
| 1, A
| 0, B
| 1
|-
! 1, A
| 2, B
| 1, A
| 1
|}
{| class="wikitable"
|+ Konačni deterministički automat
!
! x
! y
! Prihvata
|-
! A
| B
| A
| 1
|-
! B
| C
| B
| 0
|-
! C
| D
| A
| 1
|-
! D
| C
| E
| 0
|-
! E
| F
| E
| 1
|-
! F
| D
| F
| 1
|}

== 2. zadatak ==
=== Postavka ===
Konstruisati regularnu gramatiku koja generiše tačno iste sekvence kao regularni izraz a* | b*.

=== Rešenje ===
* <S> → <A>
* <S> → <B>
* <A> → a <A>
* <A> → ε
* <B> → b <B>
* <B> → ε

== 3. zadatak ==
=== Postavka ===
Napisati beskontekstnu gramatiku koja opisuje sve sekvence koje pripadaju sledećem jeziku: <math>L(G) = \left\{ a^n c^m \left(b c^k\right)^n | m, k \geq 0, n > 0 \right\}</math>, gde <math>\Sigma = \{a, b, c\}</math> predstavlja skup simbola alfabeta.

=== Rešenje ===
* <S> → a <S> b <A>
* <S> → a <A> b <A>
* <A> → c <A>
* <A> → ε
Ovo rešenje nije ispravno, jer ne garantuje da će pri svakom ponavljanju <math>b c^k</math> biti podjednak broj slova <math>c</math>. Ipak, nije poznato da li je uopšte moguće napisati bezkontekstnu gramatiku za jezik iz postavke zadataka, pa je ovo rešenje možda prihvatljivo.

== 4. zadatak ==
=== Postavka ===
<div class="abc-list">
# Na osnovu regularnog izraza <math>(a* | b*) c+</math>, konstruisati minimalni deterministički automat metodom pozicija.
# Nacrtati graf NKA dobijenog transformacijom regularnog izraza <math>(a* | b*)+</math> primenom Tompsonovog algoritma. Nije potrebno konstruisati minDKA.
</div>

=== Rešenje ===
<gallery>
PPR K1 2015 zadatak 4 a.svg | Sintaksno stablo u stavci pod a.
PPR K1 2015 zadatak 4 b.svg | Graf nedeterminističkog konačnog automata u stavci pod b.
</gallery>
{| class="wikitable"
|+ Tabela sledećih pozicija u stavci pod a
! Pozicija
! Sledeća pozicija
|-
! 1
| 1, 3
|-
! 2
| 2, 3
|-
! 3
| 3, 4
|-
! 4
| -
|}
{| class="wikitable"
|+ Konverzija nedeterminističkog konačnog automata u deterministički u stavci pod a
!
! a
! b
! c
! ─┤
! Prihvata
|-
! 1, 2, 3
| 1, 3
| 2, 3
| 3, 4
|
| 0
|-
! 1, 3
| 1, 3
|
| 3, 4
|
| 0
|-
! 2, 3
|
| 2, 3
| 3, 4
|
| 0
|-
! 3, 4
|
|
| 3, 4
| 4
| 0
|-
! 4
|
|
|
|
| 1
|}

[[Категорија:Рокови]]
[[Категорија:Програмски преводиоци 1]]