Finite Automata

Finite Automata adalah mesin automata dari suatu Bahasa regular. Finite Automata memiliki jumlah state yang banyaknya berhingga dan dapat berpindah-pindah dari suate state ke state yang lainnya. 

Finite  State  Automata/otomata  berhingga  state,  selanjutnya  disebut  sebagai  FSA  yaitu suatu model matematika dari suatu sistem yang menerima inputdan outputdiskrit. FSA merupakan mesin otomata dari bahas regular. Suatu FSA memiliki state yang banyaknya   berhingga   dan   dapat   berpindah-pindah   dari   suatu   state   ke   state   lain.   Perubahan   state   ini   dinyatakan   oleh   fungsi   transisi.   FSA   tidak   memiliki   tempat   penyimpanan,  sehingga  kemampuan  ‘mengingatnya’  terbatas,  hanya  bisa  mengingat  state yang terkini. Contoh FSA antara lain elevator, text editor, analisa leksikal, protokol komunikasi  jaringan  dan  pencek  parity.  FSA  berdasar  pada  pendefinisian  kemampuan  berubah  state-statenya  bisa  dibagi  menjadi  Deterministic  Finite  Automata  (DFA)  dan  Non-deterministic Finite Automata(NFA). 

Secara formal FSA dinyatakan oleh 5 tupel atau M = (Q, ∑, δ, S, F) dimana:

Q = himpunan state/kedudukan 

∑ = himpunan simbol input/masukan/abjad 

δ  = fungsi transisi

S  = state awal/kedudukan awal (initial state), S є Q

F  =  himpunan  state  akhir,  F  ∩  Q  (jumlah  state  akhir  pada  suatu  FSA  bisa  lebih  dari  satu)

1. Deterministic Finite Automata (DFA) 

Deterministic   Finite   Automata/otomata   berhingga   deterministik,   selanjutnya   disebut  sebagai  DFA.  Pada  DFA,  dari  suatu  state  ada  tepat  satu  state  berikutnya  untuk  setiap  simbol  masukan  yang  diterima.  Suatu  string  x  dinyatakan  diterima  bila  δ(S,  x)  berada pada state akhir/final state.

Berikut contoh dari Deterministic Finite Automata :

2. Non Deterministic Finite Automata (NFA).

Non-deterministic Finite Automata, selanjutnya disebut sebagai NFA. Pada NFA, dari  suatu  state  bisa  terdapat  0  atau  1  atau  lebih  busur  keluar  (transisi)  berlabel  simbol  input  yang  sama.  Suatu  string  diterima  oleh  NFA  bila  terdapat  suatu  urutan  transisi  sehubungan dengan input string tersebut dari state awal menuju state akhir. Untuk NFA, maka   harus   mencoba   semua   kemungkinan   yang   ada   sampai   terdapat   satu   yang   mencapai state akhir.

Berikut contoh dari Non Deterministic Finite Automata (NFA) : 

Berdasarkan contoh Deterministic Finite Automata (DFA) dan Non Deterministic Finite Automata (NFA) yang ada di atas, terlihat perbedaan antara DFA dan NFA yaitu :

•  Pada Deterministic Finite Automata, jika suatu state diberi inputan maka state tersebut akan selalu tepat menuju satu state
• Pada Non Deterministic Finite Automata, jika suatu state diberi inputan maka mungkin saja bisa menuju ke beberapa state berikutnya. Dapat dilihat di S0, jika diberi inputan b bisa menuju ke S1 dan S2.

Sumber : 

https://socs.binus.ac.id/2019/12/21/teknik-kompilasi-perbedaan-dfa-dan-nfa/

https://media.neliti.com/media/publications/226255-telaah-teoritis-finite-state-automata-de-8b056b07.pdf

Push Down Automata

Push Down Automata (PDA)   merupakan mesin otomata dari bahasa bebas konteks.  PDA di gambarkan sebagai tempat penyipanan yangtidak terbatas berupa stack/tumpukan. Stack ialah  kumpulan   dari   elemen-elemen   sejenis dengan   sifat penambahan elemen dan pengambilan elemen melalui suatu tempat yangdisebut top of stack (puncak   stack).  Prinsip pada stack adalah  LIFO. Pengambilan elemen  dari  stack  dinyatakan dengan operasi  pop, sedangmemasukkan elemen ke dalam stack dengan operasi push.

Contoh stack :

• Definisi : PDA adalah pasangan 7 tuple 

M = (Q, S, q0, F, d , G , Z0), dimana :

Q : himpunan hingga state,  

S : alfabet input, 

 G: alfabet/simbol stack, 

q0: state awal, q0 Î Q

Z0 : simbol awal stack,  Z0 Î G 

F : himpunan state penerima, F  Í Q

d : fungsi transisi , d  : Q  ( S È {e})    2^QG* (himpunan bagian dari Q  *)

d(q0, a, Z0) = (q0, AZ0). Push/insert

d(q0, a, A) = (q1, ). Pop /delete

• Untuk state q  Q, simbol input a  , dan simbol stack X , (q, a, X) = (p, ) berarti : PDA bertransisi ke state p dan mengganti X pada stack dengan string .
• Konfigurasi PDA pada suatu saat dinyatakan sebagai triple (q, x, ), dimana : q Î Q : state pada saat tersebut, x Î S * : bagian string input yang belum dibaca, dan  a Î G * : string yang menyatakan isi stack dengan karakter terkiri menyatakan top of stack.
• Misalkan (p, ay, X) adalah sebuah konfigurasi, dimana : a  Î S, y Î S*, X Î G, dan  b Î G*. Misalkan pula d(p, a, X) = (q, g) untuk q Î Q dan   g Î G*. Dapat kita tuliskan bahwa : (p, ay, Xb)  (q, y, gb).

PDA memiliki 2 jenis transisi, yaitu 

1. Ä yang merima simbol input, simbol top of stack, dan state. Setiap pilihan terdiri dari state berikutnya dan simbol simbol. Penggantian isi stack dilakukan dengan opersi push dan pop.
2. å. Transisi å tidak melakukan pembacaan input namun hanya menerima simbol top of stack dan state. Transisi ini memungkinkan PDA untuk memanipulasi isi stack dan berpindah antar state tanpa membaca input.

Sumber :

http://muslim-kekinian.blogspot.com/2016/04/pushdown-automata.html

https://dokumen.tips/documents/makalah-push-down-automata.html

Linear Bounded Automata

Linear Bounded Automata adalah mesin Turing non-deterministik multi-track berisi beberapa pita dengan panjang terbatas. Linear bounded automata memiliki kemiripan dengan mesin Turing dimana sama-sama menggunakan tape, tetapi pada mesin ini adalah finite yakni terbatas.

Linear bounded automata (LBA) adalah mesin yang berdasar pada state,sebuah tape yang berisi input string, dan sebuah read/write head yang bergerak ke kiri dan ke kanan di sekitar tape. Mesin ini membandingkan state saat ini dan simbol pada tape pada posisi head dengan jumlah aturan yang terbatas untuk menentukan state berikutnya,simbol mana yang akan ditulis pada tape, dan ke arah mana head akan bergerak.

Tata bahasa tipe ini dapat direpresentasikan oleh mesin otomata :

Aaac -> bBcd

aaCD -> ddCCA

Linear bounded automata (LBA), pada dasarnya, adalah mesin Turing yang komputasinya dibatasi pada jumlah pita tempat input ditulis. Kita dapat membayangkannya sebagai seperangkat keadaan terbatas, alfabet terbatas (termasuk penanda akhir kanan dan kiri khusus [dan]), keadaan awal yang ditentukan, dan sekumpulan instruksi terbatas dalam bentuk yang sama dengan quadruple untuk Mesin Turing. Kita berasumsi, bagaimanapun, bahwa input ke LBA diberikan antara endmarker yang ditunjuk, yaitu sebagai [w], dan bahwa LBA tidak memiliki instruksi yang memungkinkannya untuk bergerak melewati endmarker ini atau untuk menghapus atau menggantinya. Dengan demikian, kepala pita hanya dapat bergerak di bagian pita yang pada awalnya ditempati oleh w, meskipun suatu formulasi setara LBA menetapkan batas pada pita yang dapat digunakan tidak sama dengan panjang input tetapi lebih sebagai fungsi linier dari panjang input. (Fungsi linier dalam variabel x adalah dari bentuk ax + b, di mana a dan b adalah konstanta. Nilai ax + b untuk setiap nilai x pada kertas grafik memberikan garis lurus, sedangkan fungsi plot  yang melibatkan x2, x3 , dll. memberikan kurva.) Ini adalah sumber nama untuk automata ini  ruang komputasi yang diizinkan dibatasi oleh fungsi linear dari panjang string input.

Panjang = fungsi (Panjang string input awal, konstan c)

Informasi memori ≤ c × Informasi input

Perhitungan dibatasi oleh area yang terikat konstan. Alfabet input berisi dua simbol khusus yang berfungsi sebagai penanda ujung kiri dan penanda ujung kanan, yang berarti transisi tidak bergerak ke kiri dari penanda ujung kiri atau ke kanan penanda ujung kanan pita.

Otomata yang dibatasi linier dapat didefinisikan sebagai 8-tupel (Q, X, ∑, q0, ML, MR, δ, F) di mana,

Q    : Adalah seperangkat status terbatas
X    : Adalah alfabet rekaman
∑    : Adalah alfabet input
q0   : Adalah kondisi awal
ML : Adalah penanda ujung kiri
MR : Adalah penanda ujung kanan di mana MR ≠ ML
δ     : Adalah fungsi transisi yang memetakan setiap pasangan (Status, simbol pita) ke (Status, simbol           pita, Konstan 'c') di mana c dapat berupa 0 atau +1 atau -1
F     : Adalah himpunan status akhir.

Linear Bounded Automata deterministik selalu peka terhadap konteks (context-sensitive) dan Linear Bounded Automata dengan bahasa kosong tidak akan bisa memutuskan.

Akhir Penanda Kiri                                                   Akhir Penanda Kanan

Suatu bahasa disebut bisa memutuskan atau Rekursif (fungsi yang memanggil dirinya sendiri secara langsung ataupun tidak) jika ada mesin Turing yang menerima dan berhenti pada setiap string input w. Setiap bahasa yang dapat memutuskan dinamakan Turing-Acceptable.

Keputusan dari suatu masalah (P) dapat diputuskan jika bahasa (L) dari semua instance ya ke P dapat ditentukan.
Untuk bahasa yang dapat menentukan, untuk setiap string input, TM berhenti pada status accept atau reject seperti yang digambarkan dalam diagram berikut

Contoh 1

Cari tahu apakah masalah berikut ini dapat ditentukan atau tidak :
Apakah angka 'm' prima?

Jawaban

Bilangan prima = {2, 3, 5, 7, 11, 13, ………… ..}
Bagi angka ‘m’ dengan semua angka antara ‘2’ dan ‘√m’ mulai dari ‘2’.
Jika salah satu dari angka-angka ini menghasilkan sisa nol, maka ia pergi ke "Rejected", jika tidak pergi ke "Accepted". Jadi, di sini jawabannya bisa dibuat dengan 'Ya' atau 'Tidak'.

Oleh karena itu, ini adalah masalah yang dapat diputuskan.

Sumber :
https://link.springer.com/chapter/10.1007/978-94-009-2213-6_20
https://prezi.com/drtqfxnwusl3/linear-bounded-automata/
https://www.tutorialspoint.com/automata_theory/linear_bounded_automata.htm

Apa Itu Mesin Turing??

     Bisa di bilang mesin turing ini adalah model yang sangat sederhana dari komputer, Mesin turing ini juga bisa dibilang sebuah model matematika untuk komputasi yang diberikan dalam bentuk Mesin. mesin turing ini ditemukan oleh Alan Turing.

Alan Turing

Seorang ahli matematika asal Inggris. Ia mengembangkan teori tentang "mesin universal" yang mampu memecahkan persamaan matematis. Selain merupakan peneliti komputer modern digital pertama, Alan juga yang pertama kali berpikir menggunakan komputer untuk berbagai keperluan. Bahkan saat menemukan mesin turing, ia belum lulus kuliah. 

   Berfungsi sebagai model ideal untuk melakukan perhitungan matematis. Walaupun model ideal ini diperkenalkan sebelum komputer nyata dibangun, model ini tetap diterima kalangan ilmu komputer sebagai model komputer yang sesuai untuk menentukan apakah suatu fungsi dapat selesaikan oleh komputer atau tidak (menentukan computable function). 

   

       Mesin turing menggunakan pita (tape) sebagai memori yang berbentuk array . Hal ini menyebabkan data pada pita dapat diakses dari mana saja. Sebuah mesin Turing secara formal dinyatakan dalam 7 tupel, yaitu M = (Q, Σ, Γ, δ, S, F, b),  

dimana :

Q = himpunan state

Σ = himpunan simbol input

Γ = simbol pada pita (meliputi pula blank)

δ = fungsi transisi

S = state awal, S ∈ Q

F = himpunan state akhir, F⊆ Q

b = simbol kosong (blank)   bukan bagian dari Σ, b .Σ 

Bagian dari pita yang belum ditulisi dianggap berisi simbol b (blank)

        Mesin Turing terkenal dengan ungkapan "Apapun yang bisa dilakukan oleh Mesin Turing pasti bisa dilakukan oleh komputer."

          Mesin Turing menggunakan notasi seperti ID-ID pada PDA untuk menyatakan konfigurasi dari komputasinya. Stack pada PDA memiliki keterbatasan akses.  Elemen yang dapat diakses hanya elemen yang ada pada top stack. Pada Mesin Turing, memori akan berupa suatu tape yang pada dasarnya merupakan array dari sel-sel penyimpanan.

A. Pembacaan fungsi transisi pada mesin turing

Misal, d (q1,a) = (q1,b,R) dibaca :

Pada state q1 yang menunjukkan karakter a pada pita, maka karakter pada state tersebut berubah menjadi b dan head bergerak ke kanan dengan menunjuk array sebagai  state q1

B. Prinsip Kerja mesin Turing

1. Lihat state semula dan simbol yang ditunjuk head

2. Berdasarkan fungsi transisinya,tentukan:

   - State berikutnya

   - Lakukan penulisan ke pita

   - Gerakkan head ke kanan dan ke kiri

3. Bila dari pasangan state dan simbol yang ditunjuk head tidak ada lagi fungsi transisinya,berarti mesin turing berhenti

4. Bila mesin turing berhenti di dalam state final (F) , berarti input diterima. Sebaliknya jika mesin berhenti tidak pada state akhir,maka berarti inputan tersebut ditolak.

Representasi Mesin Turing :

Sumber : 

https://techno-inmyworld.blogspot.com/2014/06/mesin-turing-cara-kerja-mesin-turing.html

http://trojan-ab.blogspot.com/2015/09/tugas-ii-teknik-kompilasi-mesin-turing_13.html

http://www.komputasi.lipi.go.id/utama.cgi?artikel&1250299068