Програмски преводиоци 1/К1 2022 — разлика између измена

Извор: SI Wiki
Пређи на навигацију Пређи на претрагу
м (<ne fali slika>)
Ред 4: Ред 4:


== 1. zadatak ==
== 1. zadatak ==
{{delimično rešeno}}
=== Postavka ===
=== Postavka ===
Data su tri deterministička automata, M, N i P.
Data su tri deterministička automata, M, N i P.
Ред 73: Ред 74:


=== Rešenje ===
=== Rešenje ===
{| class="wikitable"
|+ Nedeterminstički automat koji prihvata s2s3
!
! 1
! 2
! 0
! a
! Prihvata
|-
! D
| E
|
|
|
| 0
|-
! E
| D,1
|
|
|
| 0
|-
! F
| F,1
| E
|
|
| 0
|-
! 1
|
|
| 1
| 2
| 1
|-
! 2
|
|
|
| 1
| 0
|}
{| class="wikitable"
|+ Determinstički automat koji prihvata s2s3
!
! 1
! 2
! 0
! a
! Prihvata
|-
! D,1
| E
|
| 1
| 2
| 1
|-
! E
| D,1
| E
|
|
| 0
|-
! 1
|
|
| 1
| 2
| 1
|-
! 2
|
|
|
| 2
| 0
|}
{| class="wikitable"
|+ Nedeterministički automat koji prihvata traženu sekvencu
|-
!
! 0
! 1
! 2
! a
! Prihvata
|-
| A
| A
| B
|
|
| 1
|-
| B
| B
| C
|
|
| 0
|-
| C
| A
| C
|
|
| 0
|-
| D,1
| 1
| E
|
| 2
| 1
|-
| E
|
| D,1
| E
|
| 0
|-
| 1
| 1
|
|
| 2
| 1
|-
| 2
|
|
|
| 1
| 0
|}
{| class="wikitable"
|+ Deterministički automat koji prihvata traženu sekvencu
|-
!
! 0
! 1
! 2
! a
! 1
|-
| {A,D,1}, S0
| A,1
| B,E
|
| 2
| 1
|-
| {A,1}, S1
| A,1
| B
|
| 2
| 1
|-
| {B,E}, S2
| B
| C,D,1
| E
|
| 0
|-
| {2}, S3
|
|
|
| 1
| 0
|-
| {B}, S4
| B
| C
|
|
| 0
|-
| {C,D,1}, S5
| A,1
| C,E
|
| 2
| 1
|-
| {E}, S6
|
| D,1
| E
|
| 0
|-
| {1}, S7
| 1
|
|
| 2
| 1
|-
| {C}, S8
| A
| C
|
|
| 0
|-
| {C,E}, S9
| A
| C,D,1
| E
|
| 0
|-
| {D,1}, S10
| 1
| E
|
| 2
| 1
|-
| {A}, S11
| A
| B
|
|
| 1
|}


== 2. zadatak ==
== 2. zadatak ==

Верзија на датум 22. октобар 2023. у 14:27

Овај рок није решен. Помозите SI Wiki тако што ћете га решити.

Prvi kolokvijum 2022. godine održan je 31. oktobra i trajao je 90 minuta. Postavka roka još uvek nije zvanično dostupna sa stranice predmeta.

1. zadatak

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Postavka

Data su tri deterministička automata, M, N i P.

  1. Napraviti deterministički konačni automat K koji prihvata sekvence tipa , gde su sve sekvence koje automat M odbija, a i sekvence koje automati N i P prihvataju, respektivno.
  2. Od automata iz tačke pod a napraviti desno-linearnu gramatiku, a zatim iz nje izbaciti sve nedostižne ili mrtve neterminale.
Automat M
0 1 Prihvata
A A B 0
B B C 1
C A C 1
Automat N
1 2 Prihvata
D E 1
E D E 0
F F E 1
Automat P
0 a Prihvata
1 1 2 1
2 1 0

Rešenje

Nedeterminstički automat koji prihvata s2s3
1 2 0 a Prihvata
D E 0
E D,1 0
F F,1 E 0
1 1 2 1
2 1 0
Determinstički automat koji prihvata s2s3
1 2 0 a Prihvata
D,1 E 1 2 1
E D,1 E 0
1 1 2 1
2 2 0
Nedeterministički automat koji prihvata traženu sekvencu
0 1 2 a Prihvata
A A B 1
B B C 0
C A C 0
D,1 1 E 2 1
E D,1 E 0
1 1 2 1
2 1 0
Deterministički automat koji prihvata traženu sekvencu
0 1 2 a 1
{A,D,1}, S0 A,1 B,E 2 1
{A,1}, S1 A,1 B 2 1
{B,E}, S2 B C,D,1 E 0
{2}, S3 1 0
{B}, S4 B C 0
{C,D,1}, S5 A,1 C,E 2 1
{E}, S6 D,1 E 0
{1}, S7 1 2 1
{C}, S8 A C 0
{C,E}, S9 A C,D,1 E 0
{D,1}, S10 1 E 2 1
{A}, S11 A B 1

2. zadatak

Postavka

Aritmetički izraz se sastoji iz nula ili više brojeva, gde je broj niz cifara, sa aritmetičkim operacijama sabiranja ili oduzimanja između njih. Ukoliko su terminali u datoj azbuci jedna cifra ("CIFRA"), znak za sabiranje ("+") i znak za oduzimanje ("-") napisati regularni izraz koji opisuje date aritmetičke izraze, a zatim ga pretvoriti u deterministički konačni automat korišćenjem metoda pozicija.

Rešenje

3. zadatak

Postavka

Konačni automat iz postavke zadatka.

Napisati fragment programskog koda koji implementira konačni automat sa slike:

  1. eksplicitnom predstavom funkcije stanja
  2. implicitnom predstavom funkcija stanja

Rešenje

Преузето из „https://siwiki.rs/w/index.php?title=Програмски_преводиоци_1/К1_2022&oldid=6713”