Finite State Automata & Non Finite Automata

Pembahasan nya meliputi :

• Penerapan FSA
• DFA (Deterministik Finite Automata)
• NFA (non deterministik Finite Automata)
• Ekuivalen antar DFA
• Reduksi Jumlah State

1. PENERAPAN FSA

Finite State Automata

            FSA adalah model matematika suatu sistem yang menerima input dan output diskrit. FSA juga merupakan mesin automata dari suatu bahasa regular. FSA juga tidak memiliki tempat penyimpanan sehingga kemampuan mengingat terbatas (contoh: elevator/lift). Dalam FSA juga dikenal himpunan state-state tertentu yang disebut sabagai FINAL STATE. Perubahan dari satu state ke state berikutnya mengikuti sturan tertentu yang dirumuskan sebagai suatu FUNGSI transisi M. 

FSA didefinisikan sebagai pasangan 5 Tupel → M = (Q, ∑, δ, S, F).
Keterangan :
Q : Himpunan hingga state.
∑ (Sigma) : Himpunan hingga simbol input (alfabet).
δ (Delta) : Fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input. Biasanya fungsi transisi ini digambarkan dalam bentuk tabel.
S ∈ : State awal.
F ⊆ : Himpunan state akhir.

Contoh I :
Buatlah diagram transisi dari FSA yang didefinisikan sebagai :
M = (K, VT, M, S, Z) dimana :S ={S0, S1, S2, S3}VT ={ 0,1 }K ={S0 , S3}
Dengan fungsi transisi M ada pada tabel transisi sebagai berikut :

Diagram Transisi :

Cara kerja FSA :

Mula-mula dalam state S0
Jika dari S0 menerima 1 : akan ke State-S1
Jika dari S0 menerima 11 : akan ke State-S1 lalu ke S2
Jika dari S0 menerima 0 : akan tetap di State- S0
Jika dari S0 menerima 10 : akan tetap kembali lagi State- S0
Jika dari S0 berturut-turut menerima masukan : 111, maka ia akan kembali ke- S0

Contoh II :

             Seorang petani dengan seekor serigala, kambing dan seikat rumput berada pada suatu sisi sungai. Tersedia hanya sebuah perahu kecil yang hanya dapat dimuati dengan petani tersebut dengan salah satu serigala, kambing atau rumput. Petani tersebut harus menyeberangkan ketiga bawaannya kesisi lain sungai. Tetapi jika petani meninggalkan serigala dan kambing pada suatu saat, maka kambing akan dimakan serigala. Begitu pula jika kambing ditinggalkan dengan rumput, maka rumput akan dimakan oleh kambing. Mungkinkah ditemukan suatu cara untuk melintasi sungai tanpa menyebabkan kambing atau rumput dimakan.

FSA Sebagai Pengenal String

           Mesin FSA tersebut jika menerima masukan sederetan simbol dari simbol-simbol yang diijinkan maka akan menuju suatu state tertentu. Jika state akhir yang ditempuh setelah suatu FSA menerima sederetan simbol adalah state final, maka deretan simbol (string) tersebut dikatakan dikenali oleh FSA, atau dengan kata lain FSA mengenali string tersebut.

String yang dikenali oleh FSA merupakan suatu bahasa yang dikenali oleh FSA tersebut. Jika dimiliki FSA M maka bahasa yang dikenali oleh FSA di notasikan sebagai :

L(M) = { x | x semua string yang mengantar M dari S0 ke (Si ϵ Z) }

Untuk mesin FSA pada contoh :

L(M) = { 0* , 0*(10)0* , 0*(110,111)0* }

Contoh :
Tentukan bahasa L(M) yang dikenali oleh Mesin M berikut ini :

Jawab :

• Dari diagram terlihat bahwa final-state adalah S3. Pergerakan state yang mengantar ke final state adalah S0 S1 S2 S3 yakni string : 011 atau string 111 yang dapat ditulis sebagai (0,1)11.
• Pergerakan yang lain adalah dari S0 langsung ke S2 yaitu : S0 S2 S3 yang dilakukan melalui string : 01 Setelah berada pada final state masih ada pergerakan yang bersifat rekursif pada S3 yaitu apabila diberikan masukan 0,00,000,… atau : 0*.
• Dengan demikian jika seluruh string tersebut digabungkan akan menjadi : (0,1)110* U 010*, sehingga bahasa yang dikenali adalah : L(M)= { (0,1)110* U 010* } = { ((0,1)11 U 01)0* }

FSA terbagi menjadi dua jenis, yaitu :

1. Deterministic Finite Automata

    Artinya: Dari suatu state ada tepat satu state berikutnya untuk setiap simbol input yang          diterima.

2. Non Deterministic Finite Automata (NDFA) / NFA

    Artinya: Dari suatu state bisa terdapat 0,1 atau lebih busur keluar (transisi) berlabel                simbol input yang sama.

2. DFA (DETERMINISTIC FINITE AUTOMATA)

Deterministic Finite Automata (DFA) → M = (Q, ∑, δ, S, F), dimana :

Q : Himpunan state/kedudukan

∑ (Sigma) : Himpunan simbol input

δ (Delta) : Fungsi transisi, dimana δ ∈ Q x ∑ → Q

S ∈ : State awal (initial state)

F ⊆ : Himpunan state akhir (final state)

Language → L(M) : (x | δ (S,x) di dalam F)

Pada DFA, untuk karakter input tertentu, mesin hanya menuju satu state. Fungsi transisi didefinisikan pada setiap state untuk setiap simbol input. Dan juga di DFA null (atau ε) pemindahan tidak diizinkan, DFA tidak dapat mengubah state tanpa karakter input apa pun.

Contoh :
Diketahui DFA :
Q = {q0, q1, q2}
∑ = {a, b}
S = q0
F = {q0, q1}

δ diberikan dalam tabel berikut :

Ilustrasi graf untuk DFA F sebagai berikut :

Penelusuran/Tracing :

Telusurilah, apakah kalimat-kalimat berikut diterima DFA : abababaa, aaaabab, aaabbaba.

Jawab :

M(q0,abababaa) → M(q0,bababaa) → M(q1,ababaa) → M(q0,babaa) → M(q1,abaa) → M(q0,baa) → M(q1,aa) → M(q0,a) → q0

Tracing berakhir di q0 (stata penerima) → kalimat abababaa diterima

M(q0,aaaabab) → M(q0,aaabab) → M(q0,aabab) → M(q0,abab) → M(q0,bab) → M(q1,ab) → M(q0,b) → q1

Tracing berakhir di q1 (stata penerima) → kalimat aaaababa diterima

M(q0,aaabbaba) → M(q0,aabbaba) → M(q0,abbaba) → M(q0,bbaba)→ M(q1,bbaba) → M(q2,baba) → M(q2,aba) → M(q2,ba) → M(q2,a) → q2

Tracing berakhir di q2 (bukan stata penerima) --> kalimat aaabbaba ditolak

Simpul Singkat : Sebuah kalimat diterima oleh DFA di atas jika tracingnya berakhir di salah satu state akhir.

3. NDFA/NFA (NON DETERMINISTIC FINITE AUTOMATA)
Non Deterministic Finite Automata (NFA) → M = (Q, ∑, δ, S, F), dimana :

Q : Himpunan state/kedudukan
∑ (Sigma) : Himpunan simbol input
δ (Delta) : Fungsi transisi, dimana δ ∈ Q x (∑ ⋃ ε) → P(Q)
P(Q) : set of all subsets of Q
S ∈ : State awal (initial state)
F ⊆ : Himpunan state akhir (final state)

Language → L(M) : (x | δ (S,x) di dalam F)

Contoh :
Berikut ini sebuah contoh NFA (Q, ∑, δ, S, F). dimana :
Q = {q0, q1, q2, q3, q4}
∑= {a, b,c}
S = q0
F = {q4}

δ diberikan dalam tabel berikut :

Digram Transisi yang dapat dibuat :

L(M) = {aabb,...}

Sebuah kalimat di terima NFA jika :

Salah satu tracing-nya berakhir di state akhir, atau himpunan state setelah membaca string tersebut mengandung state akhir.

Penelusuran/Tracing :
Telusurilah, apakah kalimat-kalimat berikut diterima NFA di atas :
ab, abc, aabc, aabb

Jawab :

δ(q0 ,ab) ⇒ δ(q0,b) ∪ δ(q1 ,b) ⇒ {q0, q2} ∪ {q1} = {q0, q1, q2}
Himpunan state tidak mengandung state akhir ⇒ kalimat ab tidak diterima

δ(q0, abc) ⇒ δ(q0, bc) ∪ δ(q1, bc) ⇒ {δ(q0, c) ∪ δ(q2, c)} ∪ δ(q1, c)
{{q0, q3} ∪ {q2}} ∪ {q1} = {q0, q1, q2, q3}

Himpunan state tidak mengandung state akhir ⇒ kalimat abc tidak diterima

δ(q0, aabc) ⇒ δ(q0, abc) ∪ δ(q1, abc) ⇒ {δ(q0, bc) ∪ δ(q1, bc)} ∪ δ(q1, bc)
⇒ {{δ(q0, c) ∪ δ(q2, c)} ∪ δ(q1, c)} ∪ δ(q2, c)
⇒ {{{q0, q3} ∪ {q2}} ∪ {q1}} ∪ {q1} = {q0, q1, q2, q3}

Himpunan state tidak mengandung state akhir ⇒ kalimat aabc tidak diterima

δ(q0, aabb) ⇒ δ(q0,abb) ∪ δ(q1, abb) ⇒ {δ(q0, bb) ∪ δ(q1, bb)} ∪ δ(q1, bb)
⇒ {{δ(q0, b) ∪ δ(q2, b)} ∪ δ(q1, b)} ∪ δ(q1, b)
⇒ {{{q0, q2} ∪ {q2, q4}} ∪ {q1}} ∪ {q1} = {q0, q1, q2, q4}

Himpunan state mengandung state akhir ⇒ kalimat aabb diterima

4. EKUIVALEN ANTAR DFA

          Dua buah DFA dikatakan equivalen jika keduanya dapat menerima bahasa yang sama. Misalkan kedua DFA tersebut adalah A dan A’. Misalkan pula bahasa yang diterima adalah bahasa L yang dibangun oleh alfabet VT = {a1, a2, a3, ..., an}. Berikut ini algoritma untuk menguji equivalensi dua buah DFA.

• 1) Berikan nama kepada semua stata masing-masing DFA dengan nama berbeda. Misalkan nama nama tersebut adalah : S, A1, A2, ... untuk DFA A, dan : S’, A1’, A2’, ... untuk DFA A’.
• 2) Buat tabel (n+1) kolom, yaitu kolom-kolom : (v, v’), (va1, va1’), ..., (van, van’), yaitu pasangan terurut (stata DFA A, stata DFA A’).
• 3) Isikan (S, S’) pada baris pertama kolom (v, v’), dimana S dan S’ masing-masing adalah stata awal masing-masing DFA.
• 4) Jika terdapat edge dari S ke A1 dengan label a1 dan jika terdapat edge dari S’ ke A1’ juga dengan label a1, isikan pasangan terurut (A1, A1’) sebagai pada baris pertama kolom (va1, va1’) Lakukan hal yang sama untuk kolom-kolom berikutnya.
• 5) Perhatikan nilai-nilai pasangan terurut pada baris pertama. Jika terdapat nilai pasangan terurut pada kolom (va1, va1’) s/d (van, van’) yang tidak sama dengan nilai pasangan terurut (v, v’), tempatkan nilai tersebut pada kolom (v, v’) baris-baris berikutnya. Lakukan hal yang sama seperti yang dilakukan pada langkah (4). Lanjutkan dengan langkah (5).
• 6) Jika selama proses di atas dihasilkan sebuah nilai pada kolom (v, v’), dengan komponen v merupakan stata penerima sedangkan komponen v’ bukan, atau sebaliknya, maka kedua DFA tersebut tidak ekuivalen. Proses dihentikan.
• 7) Jika kondisi (6) tidak dipenuhi dan jika tidak ada lagi pasangan terurut baru yang harus ditempatkan pada kolom (v, v’) maka proses dihentikan dan kedua DFA tersebut ekuivalen.

Contoh :

Periksalah ekuivalensi kedua DFA berikut :

Jawab :
Dengan menggunakan algoritma di atas maka dapat dibentuk tabel berikut,

Keterangan :

> (2, 5) adalah pasangan terurut baru
> (3, 6) adalah pasangan terurut baru
> (4, 7) adalah pasangan terurut baru
> tidak ada lagi pasangan terurut baru


5. REDUKSI JUMLAH STATE

       Reduksi dilakukan untuk mengurangi jumlah state tanpa mengurangi kemampuan untuk menerima suatu bahasa seperti semula (efisiensi). State pada FSA dapat direduksi apabila terdapat useless state. Hasil dari FSA yang direduksi merupakan ekuivalensi dari FSA semula. Pasangan State dapat dikelompokkan berdasarkan:

1. Distinguishable State yang artinya dapat dibedakan. Dua state p dan q dari suatu DFA            dikatakan indistinguishable apabila : 

    δ(q,w) ∈ F dan δ(p,w) ∈ F atau δ(q,w) ∉ F dan δ(q,w) ∉ F

2. Indistinguishable State yang artinya tidak dapat dibedakan.
    Dua state p dan q dari suatu DFA dikatakan distinguishable apabila :
    Ada string w ∈ S* hingga δ(q,w) ∈ F dan δ(p,w) ∉ F

Relasi :
Pasangan dua buah state memiliki salah satu kemungkinan : distinguishable atau indistinguishable tetapi tidak kedua-duanya.

Dalam hal ini terdapat sebuah relasi :

Jika    p dan q    indistinguishable,
dan    q dan r     indistinguishable
maka     p, r        indistinguishable
dan      p,q,r        indistinguishable

Dalam melakukan eveluasi state, didefinisikan suatu relasi :
Untuk Q yg merupakan himpunan semua state

• D adalah himpunan state-state distinguishable, dimana D Ì Q
• N adalah himpunan state-state indistinguishable, dimana N Ì Q
• maka x Î N jika x Î Q dan x ∉ D

Langkah :

• Hapuslah semua state yg tidak dapat dicapai dari state awal (useless state)
• Buatlah semua pasangan state (p, q) yang distinguishable, dimana p ∈ F dan q ∉F. Catat semua pasangan-pasangan state tersebut.
• Cari state lain yang distinguishable dengan aturan: “Untuk semua (p, q) dan semua a ∈ ∑, hitunglah δ (p, a) = pa dan δ (q, a) = qa” Jika pasangan (pa, qa) adalah pasangan state yang distinguishable maka pasangan (p, q) juga termasuk pasangan yang distinguishable.
• Semua pasangan state yang tidak termasuk sebagai state yang distinguishable merupakanstate-state indistinguishable.
• Beberapa state yang indistinguishable dapat digabungkan menjadi satu state.
• Sesuaikan transisi dari state-state gabungan tersebut.

Contoh :

Sebuah Mesin DFA

DAFTAR PUSTAKA :

https://www.scribd.com/doc/179155911/Reduksi-jumlah-state-pada-DFA

https://www.geeksforgeeks.org/introduction-of-finite-automata/

https://docplayer.info/36555908-Teori-bahasa-dan-automata-finite-state-automata-non-finite-state-automata.html

Pohon Penurunan Tata Bahasa Bebas Konteks

Latihan Membuat Pohon Penurunan Parsing/Parse Tree Tata Bahasa Bebas Konteks

Soal Latihan 1 Parsing/Parse Tree
S → AA
A → AAA | a | bA | Ab


Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "bbabaaba".

Jawab :

Soal Latihan 2 Parsing/Parse Tree

S → AB
A → Aa | bB
B → a | Sb


Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "baabaab".

Jawab :

Soal Latihan 3 Parsing/Parse Tree


S → Ba | Ab
A → Sa | Aab | a
B → Sb | Bba | b


Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "bbaaaabb".

Jawab :

Latihan Membuat Pohon Penurunan Ambiguitas Tata Bahasa Bebas Konteks

Soal Latihan 4 Ambiguitas


S → AB | C
A → aAb | ab
B → cBd | cd
C → aCd | aDd
D → bDc | bc


Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan "aabbccdd".

Jawab : 

Untuk menjawab soal latihan 4 ini ada dua cara penyelesaian :

Pohon 1

Pohon 2

Video Pembahasan Pohon Penurunan Tata Bahasa Bebas

 Konteks

Teknik - teknik penyederhanaan produksi

Latihan Penyederhanaan Tata Bahasa Bebas Konteks

A. Penyederhanaan dengan penghilangan produksi useless

       Soal Latihan :

      1. Penyederhanaan dengan penghilangan produksi Useless 

          S → aB | C

          B → e | Ab

          C → bCb | adF | ab

          F → cFB

      Analisa :

         B → Ab (A tidak punya penurunan
         C → adF (F tidak punya penurunan)
         F → cFB (F tidak punya penurunan ke terminal)

     Hasil Penyederhanaan:
        S → aB | C
        B → e
        C → bCb | ab



    2. Penyederhanaan dengan penghilangan produksi Useless

       S → Aa | B A → ab | D
       B → b | E
       C → bb
       E → aEa

      Analisa :
      A → D (A tidak punya penurunan
      B → E (F tidak punya penurunan)
      C → bb (C → bb adalah redudan)
      E → aEa (E tidak punya penurunan ke terminal) 

     Hasil Penyederhanaan:

     S → Aa | B
     B → ab
     C → b

B. Penyederhanaan dengan penghilangan produksi unit
       Soal Latihan :

      1. Penyederhanaan dengan penghilangan produksi Unit
         S → Aa | B
         B→ A | bb
         A → a | bc | B


       Analisa :

       A → B ==> A → bb
       B → A ==> B → a | bc | bb , Karena B → bb sudah ada maka cukup ditulis B → a | bc
       S → B ==> S → a | bc | bb
       

      Hasil Penyederhanaan :
      S → Aa | a | bc | bb
      B → a | bc | bb
      A → a | bc | bb


    2. Penyederhanaan dengan penghilangan produksi Unit

        S → A | Aa A→ B
        B → C | b
        C → D | ab
        D → b

       Analisa :

       C → D ==> C → b
       B → C ==> B → b | ab , Karena B → b sudah ada maka cukup ditulis B → ab
       A → B ==> A → ab | b
       S → A ==> S → ab | b

      Hasil Penyederhanaan:
      S → ab | b | Aa
      A → ab | b
      B → ab | b
      C → b | ab
      D → b

    

C. Penyederhanaan dengan penghilangan produksi empty (ε)
       Soal Latihan :
     1. Penyederhanaan dengan penghilangan produksi Empty (ε)
        S → AB
        A → abB | aCa | ε
        B → bA | BB | ε
        C → ε

      Analisa :
       Variabel yang nullable: A,B,C, maka:
       A → ε (dihapus)

      Maka, S → AB | B
                  A → abB | ab | aa
                  B → b | BB
                  B → ε (dihapus)

      Maka, S → AB | A
                  B → bA | BB | B
                  A → abB | ab | aa
                  C → ε (dihapus)

      Maka, A → abB | aa

     Hasil Penyederhanaan :
      S → AB | A | B
      A → abB | ab | aa
      B → bA | b | BB | B

  2. Penyederhanaan dengan penghilangan produksi Empty (ε)
      S → aBCD | bb | A | ε
      A → CDa | ef
      B → b | Af | ε
      C → BbC | ea
      D → ε

      Analisa :
      Variabel yang nullable: S,B,D, maka:
      S → ε (dihapus)
      B → ε (dihapus)
      D → ε (dihapus)

      Hasil Penyederhanaan:
        S → aBC | aC | bb | A
        A → Ca | ef
        B → b | Af
        C → BbC | bC | ea

D. Latihan Kompleks
       Lakukan penyederhanaan pada himpunan produksi berikut dengan penghilangan empty +
       unit + useless sekaligus.

        S → BACa
        B → AC
        A → dC | ε
        C → D | ε
        D → d


Untuk menjawab soal latihan kompleks diatas saya harus megerjakannya sesuai urutan penyederhanaan tata bahasa bebas konteks. Pertama menghilangkan produksi empty(ε), setelah itu menghilangkan produksi unit, dan terakhir menghilangkan produksi useless.
Jawab :


     Penghilangan produksi empty(ε) :

      Analisa:
        Variabel yang nullable: A,C, maka:
        A → ε (dihapus)
        C → ε (dihapus)

       Maka:

         S → BACa |BAa | BCa
         B → AC | A | C
         A → dC | d
         C → D
         D → d

    Penghilangan produksi unit :
      Analisa:

       C → D ==> C → d
       B → A ==> B → dC | d
       B → C ==> B → d

      Maka:
       S → BACa |BAa | BCa
       B → AC | dC | d
       A → dC | d
       C → d
       D → d

   Penghilangan produksi useless:

      Analisa:

       D → d (D → d adalah redudan)

   Hasil Akhir Penyederhanaan :
     S → BACa |BAa | BCa
     B → AC | dC | d
     A → dC | d
     C → d

Video Pembahasan Penyederhanaan Tata Bahasa Bebas Konteks

    

Penjumlahan bilangan desimal positif dengan desimal negatif, dan sebaliknya. Lakukan langkah konversi kedalam biner lalu desimalkan

Penjumlahan bilangan desimal positif dengan desimal negatif, Lakukan langkah konversi kedalam biner lalu desimalkan.
misalkan :

65 + (-55) = 10

apakah sama hasilnya antara desimal positif dan negatif tersebut ?


Merubah bilangan positif dan negatif ke biner terlebhih dahulu :

• (65)

= 64 32 16 8 4 2 1
1 0 0 0 0 0 1 (biner) = 65

• (-55)

= 32 16 8 4 2 1
1 1 0 1 1 1 (biner) = 45


biner negatifnya berubah menjadi 0 0 1 0 0 0 + 1 = 0 0 1 0 0 1. dikarenakan negatif desimal adalah complement.



penjelasan tentang complement :

• Semua angka 1 di ubah menjadi 0 dan semua angka 0 diubah menjadi 1.
• Bilangan biner yang telah diubah di tambah 1. Terkait : Penjumlahan dan Pengurangan Bilangan Biner. Jika ada angka satu paling kanan Buang angka 1 paling kanan.

dan terakhir tentukan nilai dari binernya apakah sama


ketentuan penjumlahan bilangan biner :
0+0 = 0
0+1 = 1
1+0 = 1
1+1 = 10 => 0 sisip 1
1+1+1 = 11 => 1 sisip 1.

jumlahkan hasil dari bilangan biner positif dan negatif tadi
1 0 0 0 0 0 1
0 0 1 0 0 1
                         +
0 0 0 1 0 1 0


Mengekonversi :

  0      0     0     0    1   0   1   0
128   64   32   16   8   4   2   1


65 + (-55) = 10
0 0 0 0 0 1 0 1 0 (2) = 10(10)

dan hasilnya sama :)

sumber :

• https://teknikelektronika.com/cara-konversi-bilangan-desimal-ke-bilangan-biner-dan-sebaliknya/
• https://rumusbilangan.com/bilangan-desimal-ke-biner/
• https://katakoala.com/cara-merepresentasikan-bilangan-biner-bertanda-dengan-komplemen-pertama-dan-kedua/

Bilangan Desimal, Biner, Oktal dan hexadesimal

Bilangan Desimal, Biner, Oktal dan hexadesimal

1. Macam-macam bilangan :

• Desimal 

Bilangan desimal (decimal) merupakan bilangan dengan basis 10. Angka untuk bilangan desimal adalah 0, 1, 2, … , 8, 9. Bilangan ini sering kita gunakan dalam kehidupan sehari-hari.
Setiap digit dalam sebuah bilangan dalam basis 10 dapat memiliki besaran tertentu dalam basis 10.
Contoh:
1075 akan terdiri dari 1 ribuan, 0 ratusan, 7 puluhan dan 5 satuan, atau secara matematis dapat ditulis sebagai :
1075 = (1x10³) + (0x10²) + (7x10¹) + (5x10⁰)

Rumus Konversi Desimal ke Basis Bilangan Lainnya
Untuk melakukan konversi dari bilangan desimal ke basis bilangan lainnya, misal basis n, adalah dengan membagi bilangan tersebut dengan n secara berulang sampai bilangan bulat hasil bagi nya sama dengan nol. Lalu sisa hasil bagi dari setiap iterasi ditulis dari terakhir (bawah) hingga ke awal (atas). Untuk lebih jelasnya lihat contoh konversi desimal ke basis lainnya pada penjelasan berikutnya.
  
Konversi Desimal ke Oktal
Dengan rumus yang sama seperti biner kita bisa lakukan juga untuk bilangan berbasis 8 (oktal).
Contoh:
67₁₀ = …….₈ ?

1. Pertama-tama 67/8 = 8, sisa 3
2. Lalu 8/8 = 1, sisa 0,
3. Terakhir 1/8=0, sisa 1.
4. Dengan demikian dari hasil perhitungan didaptkan 67₁₀ = 103₈
5. Anda juga dapat menggunakan fungsi microsoft excel DEC2OCT() untuk konversi bilangan desimal ke oktal.

Konversi Desimal ke Heksadesimal

Seperti halnya biner dan oktal, kita pun akan menggunakan teknik perhitungan yang sama.
Contoh 1:
67₁₀ = …….₁₆ ?

1. Pertama-tama 67/16 = 4, sisa 3
2. Lalu 4/16 = 0, sisa 4,
3. Dengan demikian dari hasil perhitungan didapatkan 67₁₀ = 43₁₆

_{Contoh 2:
9210 = …….16 ?}

1. Pertama-tama 92/16 = 5, sisa 12 (ditulis C)
2. Lalu 5/16 = 0, sisa 5,
3. Dengan demikian dari hasil perhitungan didapatkan 92₁₀ = 5C₁₆

• Biner 

Bilangan biner (binary) merupakan bilangan berbasis dua. Angka dari bilangan biner hanya berupa angka 0 dan 1.

Konversi Biner ke Desimal
Untuk melakukan konversi dari bilangan biner atau bilangan berbasis selain 10 ke bilangan berbasis 10 (desimal) maka anda tinggal mengalikan setiap digit dari bilangan tersebut dengan pangkat 0, 1, 2, …, dst, dari basis mulai dari yang paling kanan.




Contoh :
10110₂ = …….₁₀ ?

10110₂ = + 1x2⁴ + 0x2³ + 1x2² + 1x2¹ + 0x2⁰ = 16 + 0 + 4 + 2 + 0 = 22₁₀

Gunakan fungsi BIN2DEC() di microsoft excel untuk konversi biner ke desimal.

 
Konversi Biner ke oktal
Untuk melakukan konversi biner ke oktal lakukan bagi setiap 3 digit menjadi sebuah angka oktal dimulai dari paling kanan.

Contoh :
10110₂ = …….₈ ?

1. Pertama-tama bagi menjadi kelompok yang terdiri dari 3 digit biner: 10 dan 110.
2. Kemudian konversi setiap kelompok dengan menggunakan perhitungan konversi biner ke desimal.
3. Sehingga didapat 10110₂ = 26₈
4. Anda juga bisa menggunakan fungsi BIN2OCT yang disediakan di microsoft excel

 
 Konversi Biner ke Hexadesimal
Konversi biner ke heksa desimal mirip dengan konversi biner ke oktal. Hanya saja pembagian kelompok terdiri dari 4 digit biner. Selain itu untuk nilai 10, 11, 12, .., 15 diganti dengan huruf A, B, C, …, F.

Contoh :
111010₂ = …….₁₆ ?

1. Pertama-tama bagi menjadi kelompok yang terdiri dari 4 digit biner: 11 dan 1010.
2. Kemudian konversi setiap kelompok dengan menggunakan perhitungan konversi biner ke desimal.
3. Sehingga didapat 111010₂= 3A₁₆
4. Anda juga bisa menggunakan fungsi BIN2HEX() yang disediakan di microsoft excel

• Oktal

Bilangan oktal (octal) adalah bilangan berbasis 8. Sehingga angka digit yang digunakan adalah 0, 1, 2, …, 7, 8.

 
Konversi Bilangan Oktal ke Desimal
Untuk konversi oktal ke binner anda perlu mengalikan digit dengan pangkat dari bilangan 8.

Contoh :
365₈ = …….₁₀ ?

Untuk melakukan konversi bilangan oktal ke bilangan berbasis 10 (desimal) lakukan dengan mengalikan setiap digit dari bilangan tersebut dengan pangkat 0, 1, 2, …, dst, dari basis mulai dari yang paling kanan.

365₈ = (3 x 8²)₁₀ + (6 x 8¹)₁₀ + (5 x 8⁰)₁₀ = 192 + 48 + 5 = 245

Untuk fungsi konversi oktal ke decimal di ms excel gunakan OCT2DEC()

 
Konversi Bilangan Oktal ke Biner
Cara ini merupakan kebalikan cara konversi biner ke oktal. Setiap digit oktal akan langsung dikonversi ke biner lalu hasilnya digabungkan.

Contoh:
54₈ = …….₂ ?

1. Pertama-tama hitung 5₈ = 101₂ (Lihat cara konversi dari desimal ke biner)
2. Lalu hitung 4₈ = 100₂
3. Sehingga didapat 54₈ = 101100₂
4. Anda juga dapat menggunakan rumus di ms excel OCT2BIN() yang akan menkonversi bilangan oktal ke biner

Konversi Bilangan Oktal ke Heksa desimal
Untuk perhitungan secara manual, konversi bilangan oktal ke desimal dilakukan dengan mengkonversi bilangan oktal ke bilangan basis antara terlebih dahulu. Ada dua cara yang sering digunakan untuk konversi oktal ke hexadecimal. Cara pertama konversi dahulu bilangan oktal ke desimal, lalu dari bilangan desimal tersebut dikonversi lagi ke heksadesimal. Cara kedua adalah dengan menkonversi bilangan oktal ke bilangan biner, lalu dari biner di konversi lagi menjadi bilangan heksadesimal. Cara kedua merupakan cara yang paling sering digunakan.

Contoh :
365₈ = …….₁₆

1. Konversi bilangan oktal menjadi bilangan biner
   365₈ = 11 110 101 ₂
   
   angka 3, 6, dan 5 dikonversi terlebih dahulu menjadi biner.
2. Kemudian bilangan biner tersebut dikelompokkan setiap 4 digit dimulai dari yang paling kanan
3. Selanjutnya 4 digit biner transformasikan menjadi heksadesimal 11 110 101 ₂ = F5₁₆

•  Hexadesimal

Konversi Bilangan Heksadesimal ke Biner
Cara ini merupakan kebalikan cara konversi biner ke heksadesimal. Setiap digit heksadesimal langsung dikonversi ke biner lalu hasilnya dipadukan.

Contoh:
F5₁₆ = …….₂ ?

1. Pertama-tama hitung F₁₆ = 1111₂ (F₁₆ = 15₁₀ = 1111₂, Lihat cara konversi dari desimal ke biner)
2. Lalu hitung 5₁₆ = 0101₂ (harus selalu dalam 4 digit biner, bila nilai hasil konversi tidak mencapai 4 digit biner maka tambahkan angka 0 di depan hingga menjadi 4 digit biner)
3. Kemudian didapat F5₁₆ = 11110101₂
4. Fungsi di ms excel yang dapat anda gunakan untuk mengkonversi heksadesimal ke biner adalah HEX2BIN()

 Konversi Bilangan Heksa Desimal ke Oktal
Untuk konversi heksa desimal ke oktal mirip dengan cara konversi oktal ke desimal. Lakukan konversi heksadesimal ke biner terlebih dahulu lalu dari binner di konversi lagi ke oktal.

Contoh :
F5₁₆ = …….₈

1. Konversi bilangan heksadesimal menjadi bilangan biner
   F5₁₆ = 1111 0101₂
   
   angka F dan 5 dikonversi terlebih dahulu menjadi biner.
2. Kemudian bilangan biner tersebut dikelompokkan setiap 3 digit dimulai dari yang paling kanan
3. Selanjutnya 3 digit biner transformasikan menjadi oktal 11 110 101 ₂ = 365₈

 2. Operasi bilangan

BINER

• penjumlahan

Kita ambil sebagai sampel soal yaitu :
1101₍₂₎+1011₍₂₎=……₍₂₎?
1011₍₂₎+0111₍₂₎=…….₍₂₎?
Jawab :
1101₍₂₎
1011₍₂₎
_____+
11000₍₂₎
1+1=0 mempunyai carry(sisa) 1
1+0+1=0 carry 1
1+1+0=0 carry 1
1+1+1=1 carry 1
jadi hasil total adalah : 1111₍₂₎

• pengurangan

Mari kita jawab contoh soal pengurangan sistem bilangan biner berikut :
1110₍₂₎-0101₍₂₎=….₍₂₎?
1011₍₂₎-111₍₂₎=….₍₂₎?
Jawab :
1110₍₂₎
0101₍₂₎
_______+
10001₍₂₎
0-1=1 borrow/pinjam sebelah 1
0-0=0 1 jadi nol karena dipinjam 1
1-1=0
1-0=1
Jadi total adalah :  10001₍₂₎

•  perkalian

Metode yang digunakan dalam perkalian biner juga pada dasarnya sama dengan perkalian desimal, akan terjadi pergeseran ke kiri setiap dikalikan 1 bit pengali. Setelah proses perkalian masing-masing bit pengali selesai, dilakukan penjumlahan masing-masing kolom bit hasil.
Contoh :
1101
1011
———x
1101
1101
0000
1101
————–+
10001111
Perkalian juga bisa dilakukan dengan menambahkan bilangan yang dikalikan ke bilangan itu sendiri sebanyak bilangan pengali.
Contoh barusan, hasilnya akan sama dengan jika kita menambahkan 1112 ke bilangan itu sendiri sebanyak 1101 atau 13 kali.

• pembagian

Serupa dengan perkalian, pembagian pada bilangan biner juga menggunakan metode yang sama dengan pembagian desimal. Bit-bit yang dibagi diambil bit per bit dari sebelah kiri. Apabila nilainya lebih dari bit pembagi, maka bagilah bit-bit tersebut, tetapi jika setelah bergeser 1 bit nilainya masih dibawah nilai pembagi maka hasilnya adalah 0.
Pembagian pada sistem bilangan biner dapat dilakukan sama seperti contoh pembagian sistem bilangan desimal. Sebagai contoh, untuk membagi 110011 (disebut bilangan yang dibagi) dengan 1001 (disebut pembagi), langkah-langkah berikut yang perlu dilakukan.
1 0 1  Hasil
—————-
1 0 0 1  / 1 1 0 0 1 1
1 0 0 1
————— –
0 0 1 1 1 1
1 0 0 1
———–  –
sisa             1 1 0
Sehingga hasilnya adalah 101, dan sisa pembagian adalah 110.
Pembagian bisa juga dilakukan dengan cara menjumlahkan secara berulang kali dengan bilangan pembagi dengan bilangan itu sendiri sampai jumlahnya sama dengan bilangan yang dibagi atau setelah sisa pembagian yang diperoleh lebih kecil dari bilangan pembagi.


OKTAL

• penjumlahan

400(8) + 300 (8) = ..........(8)

Langkah-langkah penyelesaian:

400
300 
----- (+)

Jumlahkan secara berurutan mulai dari digit paling kanan.

0 + 0 = 0
0 + 0 = 0                     (mengambil angka dari bawah ke atas)
4 + 3 = 7

Jadi 400(8) + 300(8) = 700(8)


b. 3456(8) + 1345(8) = ...........(8)

Langkah-langkah penyelesaian:

3456
1345
------(+)

6 + 5       = 11 carry 1 ( 11 – 8 = 3)

1 + 5 + 4 = 10 carry 1 ( 10 – 8 = 2)

1 + 4 + 3 = 8   carry 1 (  8  - 8 = 0)           

1 + 3 + 1 = 5

Hasil akhir nya adalah,  3456(8) + 1345(8) = 5023(8)

• pengurangan

Pada pengurangan bilangan octal lakukan pengurangan secara berurutan mulai dari digit sebelah kanan. Jika bilangan yang dikurangi lebih besar, maka hasilnya akan  ditempatkan sebagai hasil pengurangan Octal, apabila jika bilangan yang dikurangi lebih kecil, maka akan terjadi borrow (pinjam) 1 dari digit di sebelah kirinya. Pada bilangan Decimal, angka satu yang dipinjam bernilai 10 sedangkan pada bilangan Octal angka 1 ini bernilai 8.  Perhatikan contoh di bawah! 6745(8) - 3412(8) = ..........(8)

Langkah-langkah penyelesainan:

6745
3412
----- (-)

6 - 3 = 3
7 - 4 = 3
4 - 1 = 3
5 - 2 = 3

Jadi 6745(8) - 3412(8) = 3333(8)

Contoh :

125 – 67₈
      78      → borrow
    125
      67  –

    36
 125(8) – 67(8)  =  36 (8)

 

Contoh :

1321(8) – 657(8)
      778      → borrow
    1321
      657  –
      442
  1321(8) – 657(8) = 442(8)

•  perkalian

Langkah – langkah : 
kalikan masing-masing kolom secara desimal
rubah dari hasil desimal ke octal
tuliskan hasil dari digit paling kanan dari hasil octal
- kalau hasil perkalian tiap kolol terdiri dari 2 digit, maka digit paling kiri merupakan carry of untuk ditambahkan pada hasil perkalian kolom selanjutnya







 

•  pembagian

DESIMAL 

• penjumlahan

Hitunglah nilai penjumlahan dari:

(a) 12,325 + 8,135

(b) 21,032 + 9,802 + 5,181
Jawab:

(a) Bilangan 12,325 terdiri atas puluhan (angka 1), satuan (angka 2), koma desimal (tanda “,”), persepuluhan (angka 3), perseratusan (angka 2) dan perseribuan (angka 5). Bilangan 8,135 terdiri atas satuan (angka 8), koma desimal (tanda “,”), persepuluhan (angka 1), perseratusan (angka 3) dan perseribuan (angka 5). Untuk menjumlahkannya, elemen-elemen pada kedua bilangan tersebut disusun dalam satu lajur seperti berikut ini.

1	2	,	3	2	5
	8	,	1	3	5	+
2	0	,	4	6	0

Jadi, 12,325 + 8,135 = 20,460 atau bisa kita tulis 20,46.




(b) Bilangan 21,032 terdiri atas puluhan, satuan, koma desimal, persepuluhan, perseratusan dan perseribuan. Bilangan 9,802 terdiri atas satuan, persepuluhan, perseratusan dan perseribuan. Sedangkan bilangan 5,181 juga terdiri atas satuan, persepuluhan, perseratusan dan perseribuan. Lalu jumlahkan ketiga bilangan desimal tersebut dengan cara seperti pada soal 1. (a), yaitu sebagai berikut.

2	1	,	0	3	2
	9	,	8	0	2
	5	,	1	8	1	+
3	6	,	0	1	5

Jadi, 21,032 + 9,802 + 5,181 = 36,015.

•  pengurangan

Hitunglah nilai pengurangan dari:

(a) 24,56 – 23,72
(b) 25,56 – 13,5

Jawab:

(a) Bilangan 24,56 dan 23,72 terdiri atas puluhan, satuan, koma desimal, persepuluhan dan perseratusan. Sama seperti pada penjumlahan, untuk mengurangkan kedua bilangan tersebut caranya susun masing-masing elemen dalam satu lajur, yaitu sebagai berikut.

2	4	,	5	6
2	3	,	7	2	−
	0	,	8	4

Jadi, 24,56 – 23,72 = 0,84.

(b) Bilangan 25,56 terdiri atas puluhan, satuan, koma desimal, persepuluhan dan perseratusan. Sedangkan bilangan 13,5 terdiri atas puluhan, satuan, koma desimal dan persepuluhan. Agar elemen pada bilangan 13,5 sama dengan elemen pada bilangan 25,56 maka kita bisa menambahkan angka nol dibagian paling belakang angka 13,5 sehingga menjadi 13,50. Untuk mengurangkannya sama seperti soal 2. (a) yaitu sebagai berikut.

2	5	,	5	6
1	3	,	5	0	−
1	2	,	0	6

Jadi, 25,56 – 13,5 = 12,06.

• perkalian

Hitunglah 0,0078 × 1000


Jawab:


Pengalinya 1000 dengan jumlah nol tiga, sehingga tanda koma kita geser ke kanan tiga tempat dari posisi semula, sehingga hasilnya adalah sebagai berikut.


0,0078 × 1000 = 0007,8


Angka nol di sebelah kiri angka 7 bukan merupakan angka penting sehingga tidak perlu dituliskan, oleh karena itu hasilnya menjadi seperti berikut.


0,0078 × 1000 = 7,8

pembagian

1,7 : 0,2 = ...

Kita ubah desimal menjadi pecahan

 

Coba lihat tanda bagi ( : ) diubah menjadi kali (x) pada pecahan 2 per 10 diatas
Untuk pembagian pecahan bisa dilakukan seperti itu.
Ketika tanda bagi berubah menjadi kali, maka pecahan yang dibelakangnya angkanya berbalik, bertukar posisi.
Hanya yang dibagian belakang berubah ya. Yang bagian depan tetap seperti semula.

HEXADESIMAL

penjumlahan

PENJUMLAHAN HEXADECIMAL Jumlahkan secara berurutan mulai dari digit paling kanan. Untuk dua bilangan yang dijumlahkan, jika hasil penjumlahan lebih dari 15 akan terjadi carry 1, kemudian hasil penjumlahan dikurangi 16 yang akan disimpan sebagai hasil penjumlahan Hexadecimal. Perhatikan contoh di bawah!


153(16) + 234(16) = ………. (16) Langkah-langkah penyelesaian: 153 234 —- (+) 3 + 4 = 7 5 + 3 = 8 1 + 2 = 3 Karena tidak terdapat carry, maka 153(16) + 234(16) = 387(16)




pengurangan

PENGURANGAN BILANGAN HEXADECIMAL Lakukan pengurangan secara berurutan mulai dari digit paling kanan. Jika bilangan yang dikurangi lebih kecil dari pengurang, maka akan terjadi borrow 1 (pinjam 1 ke bilangan di sebelah kirinya). Borrow 1 ini bernilai 16. Perhatikan contoh di bawah!


FBC(16) – 321(16) = ……….(16)




Langkah-langkah penyelesaian: FBC 3 2 1 —– (-) C – 1 = 12 -1 = 11, hasil pengurangan adalah B B – 2 = 11 – 2 = 9, hasil pengurangan adalah 9 F – 3 = 15 – 3 = 12, hasil pengurangan adalah C Hasil penjumlahan Hexadecimal adalah yang berwarna merah, jadi FBC(16) – 321(16) = C9B(16)




Untuk membuktikan kebenaran dari hasil penjumlahan dan pengurangan Hexadecimal, dapat dilakukan konversi bilangan terlebih dahulu ke bilangan Decimal.




perkalian


Perkalian bilangan hexadesimal dapat dilakukan dengan cara yang sama dengan perkalian bilangan desimal. Caranya adalah sebagai berikut :
Kalikan masing-masing kolom secara desimal.
Kemudian ubah dari hasil desimal ke hexadesimal.
Tuliskan hasil dari digit paling kanan dari hasil hexadesimal.
Jika hasil perkalian tiap-tiap kolom terdiri dari 2 digit, maka digit yang berada pada posisi yang paling kiri merupakan carry of untuk ditambahkan pada hasil perkalian kolom berikutnya.




Contoh ke-1 perkalian bilangan hexadesimal AB dengan 4:

 

• pembagian

Berapakah 1E3₁₆ ÷ 15₁₆

	②	Berapakah 255AC16 ÷ 52716
	15√1E3 = 17 15 – 93 93 – 0  31E316÷ 1516 =1716		527√255AC= 74 2411 – 149C 149C– 0 225AC16÷ 52716 =7416

SUMBER :
https://www.cara.aimyaya.com/2013/02/cara-konversi-bilangan-desimal-biner.html#desimal 
https://www.broexcel.com/penjelasan-bilangan-biner-dan-contoh-soalnya.html
https://a114308201005353.wordpress.com/2011/11/26/penjumlahan-pengurangan-perkalian-dan-pembagian-dalam-bilangan-biner/
http://adaminformasiteknologi.blogspot.com/2015/03/penjumlahan-dan-pengurangan-oktal.html
http://jepritarigan574.blogspot.com/2016/04/cara-perkalian-bilangan-hexadesimal.html
https://solusimatematika85.blogspot.com/2016/05/menyelesaikan-pembagian-desimal-dengan-desimal.htmlhttp://alamsyahirfan27.blogspot.com/2015/11/operasi-bilangan-oktal.html
https://indransite.wordpress.com/2016/09/29/penjumlahan-pengurangan-perkalian-dan-pembagian-bilangan-biner/

153(16) + 234(16) = .......... (16) Langkah-langkah penyelesaian: 153 234 ---- (+) 3 + 4 = 7 5 + 3 = 8 1 + 2 = 3 Karena tidak terdapat carry, maka 153(16) + 234(16) = 387(16)

Source: https://www.linksukses.com/2012/10/penjumlahan-dan-pengurangan-bilangan_9.html

153(16) + 234(16) = .......... (16) Langkah-langkah penyelesaian: 153 234 ---- (+) 3 + 4 = 7 5 + 3 = 8 1 + 2 = 3 Karena tidak terdapat carry, maka 153(16) + 234(16) = 387(16)

• Source: https://www.linksukses.com/2012/10/penjumlahan-dan-pengurangan-bilangan_9.htm

153(16) + 234(16) = .......... (16) Langkah-langkah penyelesaian: 153 234 ---- (+) 3 + 4 = 7 5 + 3 = 8 1 + 2 = 3

Source: https://www.linksukses.com/2012/10/penjumlahan-dan-pengurangan-bilangan_9.html