Програмски преводиоци 1/К1 2017

2022-10-29T13:38:46Z

Vasilevska: /* Rešenje */

{{tocright}}
'''Prvi kolokvijum 2017. godine''' održan je 28. oktobra i trajao je dva sata. Radna verzija postavke roka je [http://ir4pp1.etf.rs/Rokovi/2017-2018/si4pp1-1718-k1k2.zip dostupna sa stranice predmeta] (arhiva).

== 1. zadatak ==
=== Postavka ===
Projektovati potisni automat koji prepoznaje sledeći skup sekvenci: <math>\left\{a^k b^m c^{k-1}\right\} k > 0, m \geq 0</math>

Iz zadatog skupa izabrati jednu sekvencu dužine veće od tri i prikazati proces njenog prepoznavanja.

=== Rešenje ===
{| class="wikitable"
|+ Prvo stanje potisne mašine za prepoznavanje sekvence
!
! a
! b
! c
! ─┤
|-
! ∇
|
* PUSH(A)
* ADVANCE
| REJECT
| REJECT
| REJECT
|-
! A
|
* PUSH(B)
* ADVANCE
|
* ADVANCE
* STATE(S2)
|
* RETAIN
* STATE(S3)
| ACCEPT
|-
! B
|
* PUSH(B)
* ADVANCE
|
* ADVANCE
* STATE(S2)
|
* RETAIN
* STATE(S3)
| REJECT
|}
{| class="wikitable"
|+ Drugo stanje potisne mašine za prepoznavanje sekvence
!
! a
! b
! c
! ─┤
|-
! A
| REJECT
| ADVANCE
| REJECT
| ACCEPT
|-
! B
| REJECT
| ADVANCE
|
* RETAIN
* STATE(S3)
| REJECT
|}
{| class="wikitable"
|+ Treće stanje potisne mašine za prepoznavanje sekvence
!
! a
! b
! c
! ─┤
|-
! A
| REJECT
| REJECT
| REJECT
| ACCEPT
|-
! B
| REJECT
| REJECT
|
* POP
* ADVANCE
| REJECT
|}
Rad ovog automata možemo prikazati na sekvenci '''aabbbc'''.
{| class="wikitable"
! Stek
! Sekvenca
! Stanje
! Operacije
|-
| ∇
| aabbbc─┤
| 1
| PUSH(A), ADVANCE
|-
| ∇A
| abbbc─┤
| 1
| PUSH(B), ADVANCE
|-
| ∇AB
| bbbc─┤
| 1
| ADVANCE, STATE(S2)
|-
| ∇AB
| bbc─┤
| 2
| ADVANCE
|-
| ∇AB
| bc─┤
| 2
| ADVANCE
|-
| ∇AB
| c─┤
| 2
| RETAIN, STATE(S3)
|-
| ∇AB
| c─┤
| 3
| POP, ADVANCE
|-
| ∇A
| ─┤
| 3
| ACCEPT
|}

== 2. zadatak ==
=== Postavka ===
[[Datoteka:PPR K1 2017 zadatak 2 postavka.svg|thumb|Stablo iz postavke drugog zadatka.]]
<div class="abc-list">
# Direktno na zadatom sintaksnom stablu jednog regularnog izraza naznačiti poništivost, i funkcije prva i poslednja pozicija.
# Nacrtati tabelu sa vrednostima funkcije sledeća pozicija.
# Na osnovu zadatog stabla i rezultata pod a) odrediti konačni automat. Obavezno navesti postupak. Nije potrebna minimizacija.
</div>

=== Rešenje ===
[[Datoteka:PPR K1 2017 zadatak 2 rešenje.svg|thumb|Stablo iz rešenja drugog zadatka.]]
{| class="wikitable"
|+ Tabela sledećih pozicija
! Pozicija
! Sledeća pozicija
|-
! 1
| 3
|-
! 2
| 3
|-
! 3
| 4, 5, 8
|-
! 4
| 4, 5, 8
|-
! 5
| 6
|-
! 6
| 7, 8
|-
! 7
| 7, 8
|-
! 8
| -
|}
{| class="wikitable"
|+ Postupak pretvaranja sintaksnog stabla u deterministički konačni automat
!
! +
! -
! d
! .
! Prihvata
|-
! 1, 2, 3
| 3
| 3
| 4, 5, 8
|
| 0
|-
! 3
|
|
| 4, 5, 8
|
| 0
|-
! 4, 5, 8
|
|
| 4, 5, 8
| 6
| 1
|-
! 6
|
|
| 7, 8
|
| 0
|-
! 7, 8
|
|
| 7, 8
|
| 1
|}
{| class="wikitable"
|+ Deterministički konačni automat
!
! +
! -
! d
! .
! Prihvata
|-
! A
| B
| B
| C
|
| 0
|-
! B
|
|
| C
|
| 0
|-
! C
|
|
| C
| D
| 1
|-
! D
|
|
| E
|
| 0
|-
! E
|
|
| E
|
| 1
|}

== 3. zadatak ==
=== Postavka ===
[[Datoteka:PPR K1 2017 zadatak 3 postavka.svg|thumb|Nedeterministički konačni automat iz postavke trećeg zadatka pod b.]]
<div class="abc-list">
# Da li su dati automati ekvivalentni? Obavezno prikazati postupak.
# Konvertovati zadati nedeterministički automat u deterministički. Obavezno prikazati postupak. Nije potrebna minimizacija.
</div>
{| class="wikitable"
|+ Prvi automat iz postavke trećeg zadatka pod a
!
! 0
! 1
! 2
! Prihvata
|-
! → Ax
| Ax
| Ax
| Bx
| 0
|-
! Bx
| Bx
| Ax
| Bx
| 1
|}
{| class="wikitable"
|+ Drugi automat iz postavke trećeg zadatka pod a
!
! 0
! 1
! 2
! Prihvata
|-
! → Az
| Cz
| Az
| Bz
| 0
|-
! Bz
| Bz
| Az
| Az
| 1
|-
! Cz
| Cz
| Az
| Bz
| 0
|}

=== Rešenje ===
{| class="wikitable"
|+ Postupak provere ekvivalencije automata iz trećeg zadatka pod a
!
! 0
! 1
! 2
|-
! Ax, Az
| Ax, Cz
| Ax, Az
| Bx, Bz
|-
! Ax, Cz
| Ax, Cz
| Ax, Az
| Bx, Bz
|-
! Bx, Bz
| Bx, Bz
| Ax, Az
| '''Bz, Az'''
|}
Zbog toga što stanja Bz i Az nisu kompatibilna, ova dva automata '''nisu ekvivalentna'''.

{| class="wikitable"
|+ Postupak pretvaranja nedeterminističkog konačnog automata u deterministički
!
! +
! -
! d
! .
! Prihvata
|-
! → 1, 2, 4, 7, 8, 9
| 3, 8, 9
| 5, 8, 9
| 9, 10, 11, 12, 17, 18, 19
|
| 0
|-
! 3, 8, 9
|
|
| 9, 10, 11, 12, 17, 18, 19
|
| 0
|-
! 5, 8, 9
|
|
| 9, 10, 11, 12, 17, 18, 19
|
| 0
|-
! 9, 10, 11, 12, 17, 18, 19
|
|
| 9, 10, 11, 12, 17, 18, 19
| 13, 14
| 1
|-
! 13, 14
|
|
| 14, 15, 16, 19
|
| 0
|-
! 14, 15, 16, 19
|
|
| 14, 15, 16, 19
|
| 1
|}
{| class="wikitable"
|+ Deterministički konačni automat
!
! +
! -
! d
! .
! Prihvata
|-
! → A
| B
| C
| D
|
| 0
|-
! B
|
|
| D
|
| 0
|-
! C
|
|
| D
|
| 0
|-
! D
|
|
| D
| E
| 1
|-
! E
|
|
| F
|
| 0
|-
! F
|
|
| F
|
| 1
|}

== 4. zadatak ==
=== Postavka ===
?????

=== Rešenje ===
?????

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

SI Wiki - Кориснички доприноси [sr]

Програмски преводиоци 1/К1 2017