Arsitektur dan Organisasi Komputer - Operating System

Software:
-> System: utk membantu, cth OS
-> Application: program yg dibuat utk menyelesaikan masalah

OS: kumpulan program utk membantu pemakai utk menggunakan komputer dengan lbh mudah.

Fungsi OS:
- Convenience -> membantu
  cth: kalo mau bikin chart tinggal ambil

- Security (keamanan)
   -> Aman thd ancaman (thread), cth: org yg ga punya hak gabisa buka
        -> Data Availability, data integrity, lost data
   -> Aman thd serangan

- Efficiency: utk mengatur sumber daya (CPU, Memory, I/O) di komputer utk dipakai se efisien mungkin.

Tipe" OS (Sesuai Algo):
1. Interactive
2. Batch
3. Single Program (uni-programming)
4. Multi Programming (multi-tasking)

Early systems -> No OS, program interact directly with hardware

Simple Batch Systems -> resident monitor program

Multi-programming Systems -> I/O Devices are very slow, so when one program is waiting for I/O, another can use the CPU
-> Time sharing systems: Allow users to interact directly with the computer. Multiprogramming allows a number oof users to interact with the computer
-> Scheduling: key of multiprogramming
     -> Long Term: Determines which programs are submitted for processing. E.g. Program masih di hard disk tapi udah diatur nanti program dari HD mau diambil dan ditaro dimana
     -> Medium Term: Part of the swapping function, usually based on the need to manage multiprogramming. Trjd di memori utama
     -> Short Term: Dispatcher. Fine grained decisions of which job to execute next. Trjd di CPU

Process Control Block
- Identifier
- State
- Priority
- Program Counter
- Memory pointers
- Context data
- I/O Status
- Accounting Information

Diagram:

Key Element of OS:

Memory Management
- Uni Program: memori terbagi menjadi 2, satu utk OS (monitor), 1 utk program yg sdg berjalan
- Multi program: "user" part is sub-divided and shared among active processes

(Sisanya baca sendiri ya, ada juga di materi OS :))

Read More

Sistem Operasi - Latihan Soal dan Kunci Jawaban

1. Diketahui 32 bit virtual address dibagi menjadi 4 segmen sbb:

Berapa memori yang dibutuhkan untuk page table jika ada 1 proses dengan ukuran 256 KB yang mulai dari alamat 0, dengan PTE (Page Table Entry) = 2 byte.

2. Diketahui 61 bit virtual address, page size 1 KB, RAM 64 KB, PTE 2 byte. Berapa memori yang diperlukan untuk page table jika digunakan:
a. Standard Page Table
b. Inverted page table

3. Diketahui:

Tentukan nomor segment dari alamat-alamat sbb:
a) 649
b) 2310
c) 1727

4. (Soal sama dengan no. 1), diketahui:

5. Apa dampaknya jika ukuran page besar?

KUNCI JAWABAN
1. (1024 + 256 + (64*16)) *2 = ... byte

2. a. ( 2^61/ 2^10 ) * 2^1 = 2^51 * 2^1 = 2^52
    b. 64K/1K = 64 PTE = 128 byte

3. a) 0
    b) 1
    c) 3

5. - Jika dibuat bsr, jml pagenya berkurang, akan memperkecil jumlah page table, sehingga memori yg dipakai berkurang.
    - Akan terjd fragmentasi internal
    - Jika trjd pg fault maka proses utk swap out dan swap in mjd lebih lambat krn ukurannya bsr.

(Mau tau cara pengerjaannya? GO PREMIUM ! (?))
**LOL JK kerjain sendiri yaa. tanya" aja kalo gatau

JAWABAN DISK ARM SCHEDULING ALGORITHM

Read More

Sistem Operasi - Hard Disk

Teori yang lain coba pelajari sendiri ya, disini cuma bkl dibahas mengenai perhitungan:
DISK ARM SCHEDULING ALGORITHM

3 Faktor yang mendorong kecepatan:
- Seek Time: waktu yang dibutuhkan oleh head untuk berpindah dari satu track ke track lain
- Rotation Delay: semakin cepat rotation per meter (Rpm) semakin cepat transfer
- Actual transfer time

Algoritma dlm disk arm scheduling:
1. FCFS -> First Come First Served
2. SSF/SSTF -> Shortest Seek First / Shortest Seek Time First
3. Elevator (Scan)

Contoh soal:
Diketahui disk dengan 40 silinder (0-39). Pada saat sedang membaca silinder 11, ada permintaan untuk membaca silinder: 1, 36, 16, 34, 9, 12.
Hitung total silinder yang dilalui oleh head menggunakan algoritma:
a. FCFS
b. SSF
c. Elevator

Hint:
FCFS = sesuai urutan
SSF = mencari permintaan terdekat dgn posisi skrg
Elevator = meniru algoritma LIFT

Butuh dishare jawabannya? hehe

Read More

Sistem Operasi - Modelling Page Replacement Algo.

Belady's Anomaly -> suatu gejala dimana dgn menambah memori (page frame), ada kemungkinan jumlah page faultnya bertambah.
Ditemukan di Algo. FIFO

Stack Algorithm

-> Memori dari M(m, r) akan menjadi subset dari M(m+1, r)
-> Suatu algoritma yang memiliki stack algorithm tidak akan mengalami Belady's Anomaly

Memprediksi Page Fault Rates

yah intinya gini aja sih. biasa di soal dikasih reference string dan ditanya page faultnya bakal ada berapa kalo page frame nya sekiansekian
nah dari contoh diatas page frame nya ada 4 (0-3)
awalnya kerjain aja kyk biasa, kl diatas sih pake cara FIFO
nah disini ada yg beda yaitu distance string.
Distance string adalah jarak dr angka yg ditemukan dari tempat awalnya (?)
contoh misalkan kolom 9, dia cari 3 dan 3 ada di page frame. nah si 3 ini naik berapa kotak keatas supaya bs jd plg atas (tapi kotak awal posisi dia diitung jg) jd hasilnya 4.
Setelah dapet distance string, kita bisa tau C vector nya. C vector adalah jumlah distance string nya.
C vector utk cth diatas:
C1 = 0
C2 = 1
C3 = 1
C4 = 2
C5 = 0
C6 = 0
C7 = 0
C8 = 0
C~ = 8

Dari C vector yg sudah diketahui kita bisa tau F vector. F vector adalah jumlah page fault yang akan terjadi bila memiliki page frame sebesar F.
F vector utk cth diatas adalah:
F1 = C2 + C3 + C4 + C5 + C6 + C7 + C8 + C~ = 12
F2 = C3 + C4 + C5 + C6 + C7 + C8 + C~ = 11
F3 = C4 + C5 + C6 + C7 + C8 + C~ = 10
F4 = C5 + C6 + C7 + C8 + C~ = 8
F5 = C6 + C7 + C8 + C~ = 8
F6 = C7 + C8 + C~ = 8
F7 = C8 + C~ = 8

Maksudnya adalah kalo misalkan jumlah page frame nya ada 1 (F1), maka akan terjadi 12 page fault. Dan seterusnya :)

Memory Management
-> Sistem Paging, tujuan: agar bs menjalankan program yang besar pada physical memory yg kecil
-> Segmentasi: pengalamatan 2 dimensi
     Tujuan: untuk memudahkan pembuat program. Kenapa? karena biaya membuat software lebih besar dari biaya membuat hardware

Struktur file:
- Byte Sequence: file disimpan dan ditulis per byte
- Record sequence: isinya structure (1 record)
- Tree

Tipe file:
- Executable File: file yg berisi instruksi" yang dimengerti CPU
- Archive File: file yg digunakan utk menyimpan informasi (teks, gambar, video)

Pengaksesan File (pernah keluar di ujian!)
- Sequential Access: pengaksesan selalu dimulai dari awal dan pengakses berikutnya dilakukan secara berurutan. cth: linked list
- Random access: pengaksesan dilakukan secara acak. cth: array
- Direct Access, cth: hash table (array of linked list)

Read More

Sistem Operasi - Page Replacement Algorithm

Ada bbrp algo:
*) Optimal
*) FIFO
*) LRU
*) Second Chance
*) Clock
dll

Reference string: urutan sequence dr virtual page number pada saat program dieksekusi (biasa diket di soal)

cth soal:
diket ref. string: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
dijalankan pada komputer dgn 3 page frame
berapa kali terjadi page fault jika digunakan algoritma:
a) Optimal
b) FIFO
c) LRU
d) clock

Kelemahan FIFO: kemungkinan program yang masin digunakan sdh dibuang karena pertama kali dikeluarkan
Diperbaiki menjadi second chance -> setiap page diberi R-bit, menggunakan linked list
Algoritma:
If R = 0 then Replace
If R = 1 then R = 0, cari page berikutnya sampe ketemu yg R = 0
Perbaikan FIFO dpt jg berupa clock.

Perbedaan clock dan second chance ?
(Comment dibawah kalo ada yg tau yaa wkwkwk)

Read More

Sistem Operasi - Memory Management (Lanjutan)

Swapping (Harddisk -> Backing Store)

Program terdiri dari 3 bagian:
- Code -> tdk prnh berubah
- Data -> bs bertambah/kurang
- Stack -> bs bertambah/kurang

Pemantauan Memori -> agar dpt dgn cepat tau dimana memori dapat digunakan
Menggunakan bitmap dan linked list
Bitmap -> 1 blok memori dipantau dgn 1 bit. 0 = kosong, 1 = berisi
-> ukuran tetap
-> lambat
Linked List -> simpul" yang terkait
Dalam sebuah LL min. ada 2 field: data dan next.

Dari cth diatas, Linked List nya:

P 0 3 -> program dari 0 - 3 (offset 3)
H 3 2 -> Hole dari 3 offset 2
dst.

Contoh Soal!
Diket memori 1 GB
1 blok memori = 1KB
Besar memori yang dihabiskan utk pemantauan dgn bitmap?

Virtual Memory dan Physical Memory
Bila program memerlukan memori yang lebih besar dari besar physical memory yang tersedia, maka digunakan VIRTUAL MEMORY.
Virtual Memory -> menentukan seberapa bsr program yang dapat dieksekusi oleh CPU.

cth: program counter
bila PC hanya ada 2 bit maka hanya dapat mengeksekusi 2^2 program, yaitu dari 00 - 11.

Contoh soal:

Berdasarkan tabel diatas, Hitung physical address bila virtual address nya:
a) 2000
b) 5000
c) 10000
d) 35000


JAWABAN LATIHAN
a) First fit
    90        417               212
   100      500     200     300    600
    10        83                   88             (offset)
b) Next Fit
                 417               212     90
    100      500     200     300    600
                 83                 88      510

c) Best Fit
     90       417                212
    100      500     200     300    600
    10        83                   88        

d) Worst Fit
(gw blm tau jwbnnya, nnti diupdate yaa)

Pemantauan bitmap
1 GB/ 1KB = 2^20 blok memori
2^20 bit = 2^20/2^3 byte = 2^17 byte
2^17 byte = 128 KB :)

Menghitung physical address
a) 10192
b) 5000
c) 26384
d) Page Fault

Read More

Sistem Operasi - Memory Management

Memori dibagi menjadi 2:
*) No Memory Abstraction -> langsung mengakses ke physical memory
    Umumnya digunakan pada:
    - Komp. mainframe awal (sblm 2960)
    - Minicomputer (sblm 1970)
    - PC awal (sblm 1980)
*) Memory Abstraction

Contoh dlm gambar:

No memory abstraction dapat menjalankan bbrp program dalam waktu bersamaan. Proses di switch dengan swap.

RELOKASI: penyesuaian alamat program pada saat dipindah ke RAM
Relokasi ada 2:
- Jump Absolute
- Jump Relative -> tergantung posisinya

Analogi:
Fixed partition: kelas ada banyak, tapi jumlah bangku di masing" kelas 40.
Dynamic partition: seminar di FH, bangku yg dipake disesuaikan.

Multiple Input Queue:
+ Besarnya job" disesuaikan dengan besarnya partisi, menghemat memori
- Ada kemungkinan partisi yang kosong

Single Input Queue:
+ Tidak ada partisi yang kosong
- Ada kemungkinan job kecil dimasukkan ke partisi yang besar

Analogi fixed dan dyamic partition dlm bahasa C:
Fixed: array, cth int x[100];
Dynamic: linked list, cth:
  int *ptr;
  ptr = (int *) malloc (sizeof(int));
  free(ptr);

Dynamic Partition
Fragmentation
  -> Internal: sisa memory tdk dapat digunakan
  -> eksternal: sisa memory (hole) msh dpt digunakan
*HOLE: free space dr hsl fragmentasi

Algoritma Pengalokasian Memori:
- First Fit: yang paling pertama muat yang dimasukkin
- Next Fit
- Best fit: cari tempat yang kalo dimasukin, sisa free spacenya paling kecil
- Worst fit: kebalikan best fit

Contoh Soal!!
Diketahui hole dengan urutan sbb: 100KB, 500KB, 200KB, 300KB, 600KB
Jika ada 3 proses dgn urutan sbb: 417KB, 212KB dan 90KB
Tentukan hole" mana yg akan dialokasikan jika digunakan algo:
a) First Fit
b) Next Fit
c) Best Fit
d) Worst Fit

(Jawaban di post selanjutnya. Stay tuned! (?))

Read More

Materi Sistem Basis Data (Bahan UTS) (1)

Pengantar
> Database = Kumpulan data" yang saling berhubungan
Contoh: data universitas bagian akademik
 Data mahasiswa -> berhubungan dengan data Matkul -> berhubungan dengan data Dosen Pengampu

> Database Systems = essential components of everyday life in modern society

> Database dibuat untuk tujuan tertentu.

> Database merepresentasikan hal yang ada di dunia nyata -> mini world
   yang disimpan datanya, di dunia nyata ada barangnya

> Database dapat memiliki Size kecil maupun besar
Contoh: buku telepon -> nama, nomor telpon
              Katalog buku perpus -> nama, nomor rak, edisi, dll

Database Management System
> adalah kumpulan program-program yang membantu user membuat dan maintain database
> Meta-data: data tentang data
   contohnya: data gender hanya boleh diisi dengan M/F, tidak dapat diisi dgn yang lain (diatur oleh meta data)
> Query: statement untuk manipulasi data
    Contoh: dari database mahasiswa cuma mau ambil yang huruf depan namanya A

Characteristic of Database Approach:
1. Self-describing nature of database systems
    contoh: ada data 14110110001#Dennis di sebuah file .txt
    kalau di Dev-C, tipe datanya ditentukan saat di program
    kalau di Database, ditentukan tipe datanya langsung di DataBase

2. Program dan data terpisah (program-data independence)
    contoh: file .txt biasanya harus disimpan di file yg sama dengan programnya. Bila di database bisa terpisah

3. Insulation between programs and data, and data abstraction
    Contoh: mau menambahkan kategori baru dalam database

4. Supprot multiple views of Data -> tergantung kebutuhan, data apa yang ditampilkan
    Contoh: bagian keuangan bs liat mahasiswa udh lunas atau belum, tapi dia ga butuh liat nilai mahasiswa. Dosen gabutuh tau lunas/ngganya, tapi butuh liat nilainya

5. Sharing of data and multi user transaction processing
    -> concurrency control = mengatur transaksi mana yang dilakukan duluan apabila ada tabrakan transaksi
    -> ada 2 proses dalam transaksi
        1) pengurangan/ perubahan saldo pengirim
        2) penambahan saldo penerima
        Ingat analogi transfer uang di ATM! Misalnya Kenny punya 10 juta Febrian punya 3 juta. Kenny mau transfer 3 juta ke Feb. Yang dilakukan ATM adalah mengurangi saldo punya Kenny, baru menambahkan saldo Feb

Advantage of using DBMS approach:
1. Controlling redundancy
2. Restricting unauthorized access
3. Providing storage structures for efficient query processing
4. Providing backup and recovery
5. Enforcing integrity constraints -> contohnya bila di DB mahasiswa udah ada data nama, maka di DB nilai tidak perlu ada kolom untuk data nama, ckup pakai primary key nya saja (nanti dibahas mengenai primary key)

When NOT to use DBMS?
- Program yang simpel
- Program yang real-time
- No multiple user access to data

Data Model
> menggambarkan struktur database
> ada 3 macam:
   - High level/ conceptual data models -> paling mudah dimengerti
   - Representational/ implementation data models
   - Low level/ physical data model -> sudah dalam bentuk dtaabase

Contoh High-level:

Contoh Representational:

Database schema: deskripsi dari sebuah database. dibuat saat mendesain database dan tidak diharapkan untuk berganti terus-menerus. isi dari database schema berupa nama dari record types dan data items, serta beberapa tipe constraints

Three Schema Architecture:

Low-level = database di komputer

Data Independence
> kemampuan untuk mengubah schema pada satu level dalam database
> ada 2 macam:
   - Physical data independence = mengubah internal schema tanpa memengaruhi conceptual schema dan external schema

   - Logical data independence = mengubah conceptual schema tanpa memengaruhi external schema/application programs

DBMS Languages
> Data Definition Language (DDL) -> banyak dipakai oleh admin
   Analogi: ticketer kereta api, menentukan siapa bisa masuk
   contoh:
   -> DROP : hapus objek di DB
   -> CREATE
   -> ALTER : mengubah struktur di DB
   -> TRUNCATE

> Data Manipulation Language (DML)
   Contoh:
   -> SELECT
   -> INSERT
   -> UPDATE
   -> DELETE

>Transaction Control
   Contoh
   -> COMMIT (berhasil)
   -> ROLLBACK (gagal)

Database Systems
> Functional Requirements: sistem dapat berfungsi untuk user kategori apa (user/admin) -> what function do users need
> Data Requirements: untuk fungsi tersebut dapat berjalan, data apa saja yang dibutuhkan

Entities
- Entity (persegi panjang) = sesuatu yang memang ada di dunia nyata, bisa disentuh/ abstrak (tangible/intangible) contoh, mahasiswa, mata kuliah
- Attribute (oval) = data-data yang ada pada entity
- Relationship

Jenis-jenis atribut:
1. Simple/atomic attribute: data tdk dapat dipecah-pecah, contohnya umur
2. Composite: data dapat dipecah-pecah, contoh data alamat bisa dipecah jadi jalan, kota, kode pos
3. Multivalue: data dapat terdiri dari lebih dari 1 value, contoh nomor telepon seseorang dapat lebih dari satu
4. Stored attribute: data yang sudah ada/diinput
5. Derived attribute  data yang dapat dihasilkan dari data lain, contoh data umur dapat dihasilkan dari data tanggal lahir
6. Complex attribute: gabungan multivalue dan composite, contoh jika seseorang dpaat memiliki lebih dr 1 rumah dan setiap alamat rumah dipecah datanya menjadi jalan, kode pos, kota

7. NULL values -> tidak sama dengan nol, tidak sama dengan blank space
    Mengapa diperlukan?
    1. Nilai tidak dapat dipakai, contoh mahasiswa masukin form yang harus isi jabatan kerja
    2. Data tidak diketahui, contoh pendaftaran maba, nomor telpon belum diketahui

Entity Types dan Entity Set
- Entity Types: kategori
- Entity Set: detail" datanya
contoh: data karyawan
karyawan -> entity type
Nama: John Smith, Umur: 55, Tempat tinggal: Jln Scientia Residence -> entity set

Key attributes ( data digarisbawah)
= data yang pasti beda satu dengan lainnya

Value Set (domains) of attribute
= restriction" yang ada yntuk tiap data berbeda
= Contoh: gender hanya boleh M/F

Relationship ( belah ketupat )
- Unary (rekursif) : relationship type dengan 1 degree, contoh karyawan supervise karyawan lainnya
- Binary: satu relationship dengan 2 degree/ entity
- Ternary: satu relationship dengan 3 degree
- N-ary: satu relationship dengan > 3 degree

Cardinality Ratios for Binary Relationships
- 1:1
- 1:N atau N:1
- M:N
Contoh:

Attribute dari Relationship
> Hanya akan muncul jika telah terhubung antara 2 entity
   Attribute bukan punya salah satu entity, melainkan relationshipnya

Strong VS Weak entity
> Strong entity: punya key attribute (yang digarisbawah)
> Weak entity: tidak punya key attribute, sehingga digantikan dengan partial key (garis bawah putus-putus)

Simbol-simbol:

Read More

Teori Bahasa dan Automata - Soal Kuis

SOAL KUIS

1. RE = (a+b)^+  a*b
    a. Buat Transition Diagram menggunakan epsilon-NFA !
    b. Buat E-closurenya untuk menentukan DFA ekivalen!
    c. Minimalisasi DFA tersebut!

2. Buatlah minimalisasi dari NFA berikut

3. Buatlah RE dari FSA dibawah ini!

Read More

Teori Bahasa dan Automata - Konversi DFA ke CFG

Tatabahasa Linier

G = ( V, T, P, S )
Dimana V = Variabel yang digunakan
              T = Input yang ada

1. Konversi FSA -> CFG
    Aturan pengubahan:
    - setiap transisi status d(A, a) = B diubah menjadi aturan produksi A -> aB
    - Setiap final state P diubah bentuknya menjadi aturan produksi P -> epsilon
DFA

Tatabahasa Linier untuk FSA diatas adalah
G = ( {S, S1, S2, S3} , {a, b}, P, S )
dengan aturan produksi P:
S -> S1
S1 -> aS2
S2 -> bS3
S3 -> epsilon

NFA

Tatabahasa Linier untuk FSA diatas adalah
G = ( {L1,L2,L3} , {a,b,c}, P, S )
dengan aturan produksi P:
L1 -> aL2 | bL3
L2 -> aL3 | bL1 | bL2
L3 -> aL3 | bL3 | cL1 | bL2 | epsilon

2. Konversi RE ke CFG
Aturan:

Contoh: Diketahui RE = ( 01* | a )* b ( 01 | 10 )? b
CFG =
***PERMISALAN: A = (01* | a)* ; B = b; C = (01 | 10)? ; D = b
      E = 01* | a ; F = 1* ; G = 01 | 10;
***HINT = R? -> R + epsilon

S -> A B C D
A -> EA | epsilon
E -> 0F | a
F -> 1F | epsilon
B -> b
C -> G + epsilon
G -> 01 | 10
D -> b

atau B dan D dihilangkan, menjadi
S -> A b C b (b tidak dimisalkan lagi)

Read More

Teori Bahasa dan Automata - Minimalisasi DFA

INGAT ! yang bisa diminimalisasi hanya bentuk DFA. Jikalau masih dalam bentuk NFA ubahlah ke bentuk DFA dahulu (DFA Ekivalen)

Contoh: Diketahui DFA

Minimalisasi:
1. Pisahkan Non - Final State dan Final State

   Non - FinalState              FinalState
        1, 3                                   2

2. Masukkan input ke setiap state seperti dibawah, jika ada lebih dari 1 state yang mengarah ke state yang sama jika diberi input yang sama, maka dikatakan indistinguishable.

Non-Final State

 -> State 1 dan 3 dikatakan indistinguishable karena jika diberi input a dan b akan mengarah ke state yang sama

Final State







3. Buat tabel Minimalisasi
Caranya: Buat tabel dengan kolom sesuai jumlah state-1 dan Baris sejumlah state-1. Beri tanda X jika pasangan state tidak sama (distinguishable) dan tanda O bila pasangan state ekivalen (indistinguishable)

4. Buat transition diagramnya
Transition Diagram yang diminimalisasi:

Contoh Latihan soal yang lebih rumit (dari slide, silahkan pelajari sendiri dari penjellasan yang sudah diberikan)

Read More

Teori Bahasa dan Automata - Epsilon-NFA

Finite Automata dengan Epsilon Transition: memungkinkan adanya transisi antara input kosong (empty) dari state Q.

Menggunakan Algoritma Thompson:

Contoh Soal:
Diketahui RE = (a+b)*abb
1. Buat Transition Diagramnya! (dengan algoritma Thompson)
2. Buat DFA-Ekivalennya!

1. Transition diagram:

2. DFA Ekivalen
*anggeplah E = lambang epsilon
E-closure -> sampai state berapa bisa tersambung dengan epsilon

Transition Diagram DFA Ekivalen:

State Table:

YANG PERLU DIINGAT !
RE = (a+b)*abb
Transition diagram:

RE = a(a+b)abb
Transition Diagram:

*Input epsilon setelah q0 dan setelah q6 HANYA dikarenakan ada tanda * setelah (a+b). Jika tidak, maka tidak perlu diberi input epsilon terlebih dahulu.

Read More

Teori Bahasa dan Automata - Finite Automata

Sistem Finite State:
- Deterministic Finite Automata (DFA)
- Non-Deterministic Finite Automata (NFA)
- Push-Down Automata (PDA)
- Turing Machine
- Linear Bounded Automata

DFA
- Tiap inputan akan mengarah ke satu tujuan yang pasti, antara ke state lain atau ke diri sendiri
contoh = Diketahui Transition Diagram:

Untuk menuju Final state (Q1), Jalur yang dapat ditempuh adalah:
1. Q0 diberi input 0 ke Q1
2. Q0 diberi inputan 1 ke Q2, Q2 diberi input 1 ke Q1

Definisi formal:

Dimana dari Transition Diagram diatas, definisi formalnya menjadi:
Q = {Q0,Q1,Q2}
sigma = {0,1}
F = {Q1}

Fungsi Transisi dapat dibuat melalui Tabel Transisi:

            |       Input
   State  |   0      |      1
______ |_____|______
  ->Q0     |    Q1   |   Q2
    *Q1     |    Q1   |   Q1
     Q2     |    Q2  |   Q1

-> untuk Start State
* untuk Final State

Input yang Benar (berdasarkan transisi diagram):
- 00
- 1001
- 111

Input yang Salah:
- 001
- 100

Syarat String diterima sebagai bahasa dalan Finite State Automata (FSA)
1. Input String habis terbaca, DAN
2. State berpindah dari start state dan berhenti pada final state

Penelusuran String yang diterima (berdasarkan transition diagram)
Misalkan string "001"

NFA

- Tiap input dapat mengarah ke lebih dari satu state berbeda

Contoh: Tabel Transisi NFA

Definisi formal: ( {Q0,Q1,Q2,Q3,Q4}, {0,1},    , Q0, {Q2, Q4} )

Tabel Transisi
            |       Input
   State  |   0      |      1
______ |_____|______
  ->Q0     | {Q0,Q3} |   {Q0,Q1}
     Q1      |            |   Q2
    *Q2     |    Q2    |   Q2
     Q3     |     Q4   |
    *Q4     |      Q4  |  Q4

Konversi NFA ke DFA Ekuivalen

Transition Diagram DFA Ekivalen:

Jawaban dari Latihan Soal RE
1. (0+1)* 01
2. abb (a+b)*
3. (0+1)* 001 (0+1)*
4. (aa + ab + ba + bb)* b
5. ((01 (0+1)*) + ((0+1)* 01))
6. (0+1)* 1 (00+01+10+11)
7. ((a+b+c)* a (a+b+c)* b (a+b+c)*) +((a+b+c)* b (a+b+c)* a (a+b+c)*)

Read More