Jumat, 26 Mei 2017

TEORI BAHASA AUTOMATA

FINITE STATE AUTOMATA
(FSA)

Finite state automata adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata.
Finite State Automata (FSA) adalah model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasarkan input dan fungsi transisi. Finite state automata tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini.

Finite State Automata dinyatakan oleh pasangan 5 tuple, yaitu:
M = (Q , Σ , δ , S , F )
Q = himpunan state
Σ = himpunan simbol input
δ = fungsi transisi δ : Q × Σ
S = state awal / initial state , S ∈ Q
F = state akhir, F ⊆ Q

Karakteristik Finite Automata
1. Setiap Finite Automata memiliki keadaan dan transisi yang terbatas.
2. Transisi dari satu keadaan ke keadaan lainnya dapat bersifat deterministik atau non-deterministik.
3. Setiap Finite Automata selalu memiliki keadaan awal.
4. Finite Automata dapat memiliki lebih dari satu keadaan akhir.
jika setelah pemrosesan seluruh string, keadaan akhir dicapai, artinya otomata menerima string tersebut.

Setiap FSA memiliki:
1. Himpunan berhingga (finite) status (state)
  • Satu buah status sebagai status awal (initial state), biasa dinyatakan q0.
  • Beberapa buah status sebagai status akhir (final state).
2. Himpunan berhingga simbol masukan
3. Fungsi transisi


Menentukan status berikutnya dari setiap pasang status dan sebuah simbol masukan.

Cara Kerja Finite State Automata
Finite State Automata bekerja dengan cara mesin membaca memori masukan berupa tape yaitu 1 karakter tiap saat (dari kiri ke kanan) menggunakan head baca yang dikendalikan oleh kotak kendali state berhingga dimana pada mesin terdapat sejumlah state berhingga.
Finite Automata selalu dalam kondisi yang disebut state awal (initial state) pada saat Finite Automata mulai membaca tape. Perubahan state terjadi pada mesin ketika sebuah karakter berikutnya dibaca. Ketika head telah sampai pada akhir tape dan kondisi yang ditemui adalah state akhir, maka string yang terdapat pada tape dikatakan diterima Finite Automata (String-string merupakan milik bahasa bila diterima Finite Automata bahasa tersebut).

Finite State Diagram (FSD)

Finite State Automata dapat dimodelkan dengan Finite State Diagram (FSD) dapat juga disebut State Transition Diagram. Sistem transisi adalah sistem yang tingkah lakunya disajikan dalam bentuk keadaan-keadaan (states). Sistem tersebut dapat bergerak dari state yang satu ke state lainnya sesuai dengan input yang diberikan padanya.
Fungsi Transisi (d) adalah representasi matematis atas transisi keadaan.
S = himpunan alfabet.
Q = himpunan keadaan-keadaan.
d = Q x S à Q

Finite State Diagram terdiri dari:
1.Lingkaran menyatakan state
Lingkaran diberi label sesuai dengan nama state tersebut. Adapun pembagian lingkaran adalah:
•Lingkaran bergaris tunggal berarti state sementara
•Lingkaran bergaris ganda berarti state akhir
2.Anak Panah menyatakan transisi yang terjadi.
Label di anak panah menyatakan simbol yang membuat transisi dari 1 state ke state lain. 1 anak panah diberi
label start untuk menyatakan awal mula transisi dilakukan.
Contoh FSA : pencek parity ganjil



Misal input : 1101
Genap 1 Ganjil 1 Genap 0 Genap 1 Ganjil : diterima mesin
Misal input : 1100
Genap 1 Ganjil 1 Genap 0 Genap 0 Genap : ditolak mesin
Dari contoh diatas, maka:
Q = {Genap, Ganjil}
Σ = {0,1}
S = Genap
F = {Ganjil }

atau
δ(Genap,0) = Genap
δ(Genap,1) = Ganjil
δ(Ganjil,0) = Ganjil
δ(Ganjil,1) = Genap
Sebuah FSA dibentuk dari lingkaran yang menyatakan state:
• Label pada lingkaran adalah nama state
• Busur menyatakan transisi/ perpindahan
• Label pada busur yaitu symbol input
• Lingkaran yang didahului sebuah busur tanpa label menyatakan state awal
• Lingkaranb ganda menyatakan state akhir/ final.
Jadi sebuah mesin otomata dapat dinyatakan dalam diagram transisi, fungsi transisi dan tabel transisi.

Jenis FSA
Ada dua jenis FSA :
1. Deterministic Finite Automata (DFA) : dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima. Deterministik artinya tertentu/sudah tertentu fungsi transisinya.
Notasi matematis DFA:
• M = nama DFA
• Q = himpunan keadaan DFA
• S = himpunan alfabet
• d = fungsi transisi
• q0 = keadaan awal
• F = keadaan akhir
M = (Q, S, d, q0, F)
Contoh : Pengujian untuk menerima bit string dengan banyaknya 0 genap, serta banyaknya 1 genap.
0011 : diterima
10010 : ditolak, karena banyaknya 0 ganjil
Diagram transisi-nya :




DFA nya:
Q = {q0 , q1 , q2 , q3 }
Σ = {0,1}
S = q0
F = { q0}
fungsi transisi adalah:




δ( q0,011)= δ( q2,11) =δ( q3,1)= q2 è Ditolak
δ( q0,1010)= δ( q1,010) =δ( q3,10)=δ( q2,0)= q0 èDiterima


2. Non-deterministic Finite Automata (NFA) : dari suatu state ada 0, 1 atau lebih state    berikutnya untuk setiap simbol masukan yang diterima.
Non-Deterministic Finite Automata:
• Otomata berhingga yang tidak pasti untuk setiap pasangan state input, bisa memiliki 0 (nol) atau lebih pilihan untuk state berikutnya.
• Untuk setiap state tidak selalu tepat ada satu state berikutnya untuk setiap simbol input yang ada.
• Dari suatu state bisa terdapat 0,1 atau lebih busur keluar (transisi)
berlabel simbol input yang sama.
• Untuk NFA harus dicoba semua kemungkinan yang ada sampai
terdapat satu yang mencapai state akhir.
• Suatu string x dinyatakan diterima oleh bahasa NFA, M= (Q, _, d, S, F) bila {x | d (S,x) memuat sebuah state di dalam F}
Kedua finite automata di atas mampu mengenali himpunan reguler secara presisi. Dengan demikian kedua finite automata itu dapat mengenali string-string yang ditunjukkan dengan ekspresi reguler secara tepat.
DFA dapat menuntun recognizer(pengenal) lebih cepat dibanding NDFA. Namun demikian, DFA berukuran lebih besar dibanding NDFA yang ekivalen dengannya. Lebih mudah membangun NDFA dibanding DFA untuk suatu bahasa, namun lebih mudah mengimplementasikan DFA dibanding NDFA.


EKSPRESI REGULAR

Hubungan ER dengan FSA
  • Untuk setiap ER ada satu NFA dengan transisi  ε  (NFA ε-move) yang ekivalen. 
  • Sementara untuk setiap DFA ada satu ER dari bahasa yang diterima oleh DFA. 
  • Hubungannya dapat digambarkan sebagai berikut 



Notasi Ekspresi Regular
Notasi yang digunakan untuk ER adalah :

  • * (asterisk) : bisa tidak muncul, bisa juga muncul  berhingga kali (0-n)
  • +   (SuperScript) : minimal muncul satu kali (1-n) 
  • + atau U (union ): atau
  • . (konkatenasi) : titik bisa saja tidak di tuliskan 
  •   misalnya: ab sama  dengan a.b

Ekspresi Aritmatika
(5 + 3) *4 = 32


Ekspresi Reguler
     (0 È 1)0*
semua string yang berawal dengan string 0 atau 1, diikuti sembarang jumlah 0

Contoh ekspresi regular (ER) : 
1.  ER : ab*cc 
 Contoh string yang dibangkitkan : abcc, acc, abbcc, abbbcc (b bisa tidak
 muncul atau muncul sejumlah berhingga kali)  

2.  ER : 010*  
 Contoh string yang dibangkitkan : 01, 010, 0100,01000 (0 bisa tidak
 muncul atau muncul sejumlah berhingga kali)  

3. ER : a*d 
 Contoh string yang dibangkitkan : d, ad, aad, aaad 

4.  ER : a+d 
 Contoh string yang dibangkitkan :  ad,aad, aaad,aaaad

5. ER : a*∪ b* (ingat ∪ berarti atau)
Contoh string yang dibangkitkan : a, b, aa, bb, aaa, bbb, aaaa, bbbb

6. ER : a ∪ b
Contoh string yang dibangkitkan : a, b

7. ER : 01* + 0
Contoh string yang dibangkitkan : 0, 01, 011, 0111, 01111

Language dari (0 È 1)0*
(0 È 1) = ({0} È {1})
0* = {0}* à semua string yang anggotanya   simbol 0.
(0 È 1)0* = (0 È 1) ○ 0*
L = {00, 10, 000, 100, 0000, 1000, … }
Language dari (0 È 1)*
Ekspresi ini dapat dituliskan sebagai S*, dengan S = {0,1} L = {0, 1, 00, 01, 10, 11, … }Kalauditeruskan (3 digit) menjadi :{….,000,001,010,011,100,101,110,111,……} L = {0, 1, 00, 01, 10, 11, … }Kalau diteruskan (3 digit) menjadi :{….,000,001,010,011,100,101,110,111,……}

POHON PENURUNAN
Context Free Grammar ( CFG ) menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis. Bagian sintaks dalam suatu kompilator kebanyakan di definisikan dalam tata bahasa bebas konteks. Pohon penurunan ( derivation tree/parse tree) berguna untuk menggambarkan simbol-simbol variabel menjadi simbol-simbol terminal setiap simbol variabel akan di turunkan menjadi terminal sampai tidak ada yang belum tergantikan.
Contoh, terdapat CFG dengan aturan produksi sebagai berikut dengan simbol awal S :
  • S → AB
  • A → aA | a
  • B → bB | b
Maka jika ingin dicari gambar pohon penurunan dengan string : ‘aabbb’ hasilnya adalah seperti di bawah :


Context Free Grammar (CFG) - Parse Tree
Proses penurunan / parsing bisa dilakukan dengan cara sebagai berikut :
  • Penurunan terkiri (leftmost derivation): simbol variabel terkiri yang di perluas terlebih dahulu.
  • Penurunan terkanan ( rightmost derivation ) : simbol variabel terkanan yang diperluas terlebih dahulu.
Misal : Grammar sbb :
  • S → aAS | a
  • A → SbA | ba
Untuk memperoleh string ‘aabbaa’ dari grammar  diatas dilakukan dengan cara :
  • Penurunan terkiri: S => aAS => aSbAS => aabAS => aabbaS => aabbaa
  • Penurunan terkanan : S => aAS => aAa => aSbAa => aAbbaa => aabbaa
Contoh Lain:
Diketahui grammar G = {I → H | I H | IA,  H → a| b | c | … |z,  A → 0 | 1 | 2| …|9}
dengan I adalah simbol awal.Berikut ini kedua cara analisa sintaks untuk string x23b.



Derivasi dan Parsing
Ambiguitas
Ambiguitas terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu string.
Misalkan terdapat tata bahasa sebagai berikut :
  • S → A | B
  • A → a
  • B → a
Untuk memperoleh untai ‘a’ bisa terdapat dua cara penurunan sebagai berikut :
  •  S => A => a
  •  S => B => a
 Contoh ambiguitas lain:
Diketahui grammar G = {S → SOS|A ,  O → *|+,   A → 0|1|2|…|9}
String : 2*3+7 mempunyai dua pohon sintaks berikut  :


             
Sebuah string yang mempunyai lebih dari satu pohon sintaks disebut string ambigu (ambiguous). Grammar yang menghasilkan paling sedikit sebuah string ambigu disebut grammar ambigu.


TEORI CHOMSKY
PADA KESEHARIAN

Avram Noam Chomsky adalah seorang profesor linguistik dari Massachusetts Institute of Technology. Salah satu reputasi Chomsky di bidang linguistik terpahat lewat teorinya tentang generative grammar.
Kepakarannya di bidang linguistik ini mengantarkannya merambah ke studi politik. Chomsky telah menulis lebih dari 30 buku politik, dengan beragam tema. Dan sejak 1965 hingga kini, dia menjelma menjadi salah satu tokoh intelektual yang paling kritis terhadap kebijakan luar negeri Amerika Serikat. Buku-buku bertema politiknya kerap dianggap terlalu radikal untuk diresensi atau ditampilkan media AS.
Noam Chomsky yang kemudian sering disebut Chomsky dikenal sebagai tokoh intelektual yang berani "melawan arus" mapan (atau istilah populernya sebagai antikemapanan), baik terhadap kalangan kolega yang disebut-sebutnya sebagai "pembebek garis resmi kebijakan Amerika Serikat" ataupun para elit pemerintahan di Amerika Serikat.
Noam Chomsky lahir pada 7 Desember 1928 di Pennsylvania, Amerika Serikat. Dibesarkan di tengah keluarga berpendidikan tinggi, pasangan Dr William Zev Chomsky dan Elsie Simonofsky.
Chomsky merupakan penganut nativisme. Menurutnya, bahasa hanya dapat dikuasai oleh manusia, binatang tidak mungkin dapat menguasai bahasa manusia. Pendapat Chomsky didasarkan pada beberapa asumsi. Pertama, perilaku berbahasa adalah sesuatu yang diturunkan (genetik), setiap bahasa memiliki pola perkembangan yang sama (merupakan sesuatu yang universal), dan lingkungan memiliki peran kecil di dalam proses pematangan bahasa. Kedua, bahasa tidak dapat dikuasai dalam waktu yang relatif singkat.Ketiga, lingkungan bahasa anak tidak dapat menyediakan data yang cukup bagi penguasaan tata bahasa yang rumit dari orang dewasa.
Menurut aliran ini, bahasa adalah sesuatu yang kompleks dan rumit sehingga mustahil dapat dikuasai dalam waktu yang singkat melalui “peniruan”. Nativisme juga percaya bahwa setiap manusia yang lahir sudah dibekali dengan suatu alat untuk memperoleh bahasa (language acquisition device, disingkat LAD). Mengenai bahasa apa yang akan diperoleh anak bergantung pada bahasa yang digunakan oleh masyarakat sekitar. Sebagai contoh, seorang anak yang dibesarkan di lingkungan Amerika sudah pasti bahasa Inggris menjadi bahasa pertamanya.
Chomsky juga beranggapan bahwa pemakai bahasa mengerti struktur dari bahasanya yang membuat dia dapat mengkreasi kalimat-kalimat baru yang tidak terhitung jumlahnya dan membuat dia mengerti kalimat-kalimat tersebut. Jadi, kompetensi adalah pengetahuan intuitif yang dipunyai seorang individu mengenai bahasa ibunya (native languange). Intuisi linguistik ini tidak begitu saja ada, tetapi dikembangkan pada anak sejalan dengan pertumbuhannya, sedangkan performansi adalah sesuatu yang dihasilkan oleh kompetensi.
Tahapan dalam perolehan bahasa menurut chomsky diantaranya yaitu:
·         Cooing
      Tahapan ini dilalui bayi oleh seluruh dunia tidak terpengaruh pada jenis bahasa yang ada pada sekitarnya
·         Babbling
      Tahapan ini berlangsung pada usia 1-6 bulan menunjukan kecenderunhgan bayi untuk mengeluarkan fonem yang digabungkan antara huruf hidup dan konsonan.biasanya mengeluarkan bunyi seperti “ba ba”,”da da”.
·         One-Word Utterances
      Tahapan ini berlangsung pada umur 1 tahun yang menunjukan kecenderungan bayi untuk mengeluarkan fonem yang berguna pada bahasanya baik huruf hidup maupun konsonan misalnya anak mengatakan “aku mau makan”
·         Two-Word Utterances
      Tahapan ini berlangsung pada usia 1,5 atau 2,5 tahun dimana bayi dan balita menggabungkan dua atau tiga buah kata, pada tahap ini anak mulai memahami sintaks.misalnya “aku mau main ke rumah tito(teman mainya)”
·         Developing Grammar
Pada usia 2 dan 3 tahun, anak mulai menghasilkan ujaran kata-ganda (multiple-word utterances) atau disebut juga ujaran telegrafis. Anak juga sudah mampu membentuk kalimat dan mengurutkan bentuk-bentuk itu dengan benar. Kosakata anak berkembang dengan pesat mencapai beratus-ratus kata dan cara pengucapan kata-kata semakin mirip dengan bahasa orang dewasa
Antara 2 dan 3 tahun, anak-anak biasanya mulai menempatkan tiga kata-kata yang lebih bersamaan, mengatakan hal-hal seperti "Aku membuat susu". Kadang-kadang mereka mengatakan hal-hal seperti "Eve adalah gadis" (cokelat, 1973, p 314), sekarang tampaknya menggunakan subyek dan kata kerja yang melampaui agen dan tindakan (eve tidak melakukan apa-apa). anak-anak berbahasa Inggris biasanya mengikuti urutan subjek-verba-objek kata, yang merupakan bagian integral dari struktur dalam bahasa kita (Brown, Cazden, & Klima Bellugi, 1969, hal 42).
Begitu anak-anak mulai meletakkan tiga atau lebih kata bersama-sama, mereka menunjukkan rasa struktur-ketergantungan-yang-frasa nomina seluruh unit. Mereka mengungkapkan hal ini, misalnya, mereka berhenti, seperti ketika anak berkata, "Pasang ... topi merah ... pada," daripada "Pasang ... topi merah ... pada" Anak itu tahu bahwa ungkapan "topi merah." fungsinya sebagai unit yang tidak akan putus.Kemudian, ketika anak-anak mulai melakukan transformasi, mereka akan menghormati integritas unit-unit. Selama fase ini anak-anak juga mulai memanfaatkan akhiran
Kemungkinan ini memukul Klima dan Bellugi (1966) ketika negatif anak-anak periksa. Awalnya anak-anak bertindak seolah-olah pemerintahan mereka adalah: Pasang negatif di depan kalimat penuh (atau setelah itu). Misalnya, mereka berkata, "Tidak bermain itu," "Tidak mau kepala berdiri," dan "Mobil tidak pergi."
Sesaat kemudian anak-anak tampaknya merupakan aturan baru: Pasang negatif setelah frase kata benda pertama dan sebelum segala sesuatu yang lain. Mereka mengatakan hal-hal seperti "Dia tidak menggigit Anda" dan "Aku ingin berdiri amplop.
Pada tahapan yang berbeda, kemudian, struktur negatif anak dengan cara mereka sendiri. Sebagai Klima dan bellugi (1966) mengatakan, "Tampaknya itu kepada kita bahwa bahasa anak-anak telah systematicity sendiri, dan bahwa kalimat-kalimat anak-anak tidak hanya salinan tidak sempurna dari orang-orang dewasa"
  • Transformasi
Antara sekitar 3 dan 6 tahun, tata bahasa anak-anak dengan cepat menjadi sangat kompleks, terutama, anak-anak mulai melakukan transformasi. Bellug Klima (1968) telah mempelajari bagaimana anak-anak bentuk di mana, Apa, dan Mengapa pertanyaan, yang transformasi representasi mereka yang dalam struktur. Misalnya, 'Di mana saya dapat menyimpannya pada dasarnya adalah trasfomation dari Aku bisa menempatkannya di mana?
Anak-anak tidak menguasai operasi transformasional sekaligus, dan mereka tampaknya agak melewati tahap-tahap seperti yang berkaitan dengan negatif. Misalnya, mereka pergi melalui suatu masa di mana mereka mengatakan hal-hal seperti, "Dimana saya dapat menaruhnya?
•              Near adult Grammar
Walaupun anak-anak menguasai sebagian besar aspek tata bahasa pada usia 5 atau 6 tahun, beberapa transformasi paling kompleks masih di luar jangkauan mereka.Misalnya, mereka tampaknya mengalami kesulitan dengan suara pasif sampai usia 7 atau lebih (Turner & Rommetveit, 1967). Tahun-tahun 05-10 Mei menjadi penting untuk akuisisi keterampilan gramatikal subtlest dan paling kompleks (C. Chomsky)
•              Universal
Tahapan ini mulai muncul mulai 4 tahun ditunjang oleh penambahan perolehan kosa kata yang meningkat. Sebagaimana ditunjukkan, psikolinguis banyak orang percaya mungkin ada universal dalam proses perkembangan. Sejauh ini bukti yang paling kuat untuk tahap awal. Anak-anak di mana-mana mungkin melanjutkan dari mengoceh untuk satu kata untuk dua ucapan-ucapan kata. Mengoceh dan dua struktur kata, khususnya, ternyata sangat mirip di seluruh kata (Brown & Herrnstein, 1975, hlm. 477 479; Sachs, 1976).
Pencarian untuk universal sintaksis setelah fase dua kata menjadi sangat sulit, dan pencarian benar-benar baru saja dimulai. Beberapa bukti menunjukkan bahwa anak-anak di mana-mana awalnya negatif dapat menangani dengan cara yang sama, dan mereka mungkin overregularize beberapa bagian pidato (Slobin, 1973,1985). Oleh anak-anak waktu menguasai transformasi, mereka menggunakan aturan-aturan yang jelas agak berbeda dari bahasa ke bahasa. Namun, mungkin ada kendala universal, seperti ketergantungan struktur, yang membatasi aturan mereka akan membentuk.

Perkembangan Bahasa
Periode Umur
Perkembangan/Perilaku Anak
0-6 Bulan
Sekedar bersuara
Membedakan huruf hidup
Berceloteh pada akhir periode
6-12 Bulan
Celoteh bertambah dengan mencakup suara dari bahasa ucap
Isyarat digunakan untuk mengkomunikasikan suatu objek
12-18 Bulan
Kata pertama diucapkan
Rata-rata memahami 50 kosakata lebih
18-24 Bulan
Kosakata bertambah sampai rata-rata 200 buah
Kombinasi dua kata
2 Tahun
Kosakata bertambah cepat
Penggunaan bentuk jamak secara tepat
Penggunaan kata lampau (past tense)
Penggunaan beberapa preposisi atau awalan
3-4 Tahun
Rata-rata panjang ucapan naik dari 3 sampai 4 morfem per kalimat
Menggunakan pertanyaan “ya” dan “tidak” dan pertanyaan “mengapa, di mana, siapa, kapan “
Menggunakan bentuk negatife dan perintah
Pemahaman pragmatis bertambah
5-6 Tahun
Kosakata mencapai rata-rata 10.000 kata
Koordinasi kalimat sederhana
6-8 Tahun
Kosakata terus bertambah cepat
Lebih ahli menggunakan sintaksis (tata kalimat)
Keahlian bercakap meningkat
9-11 Tahun
Definisi kata mencakup sin

Adapun Gambaran tingkah laku pada kehidupan sehari-hari dapat dilihat seperti pada mekanisme bahasa
  • Pada tahapan cooing atau berbunyi biasanya dengan ekpresi menangis
  • Pada tahap babbling contohnya anak mengeluarkan kata-kata seperti da da, ba ba, mu mu, bu bu, ma ma, pa pa,dll
  • Pada tahan ujar satu kata contohnya anak mulai bisa mengatakan seperti mam” (Saya minta makan); “pa” (Saya mau papa ada di sini), “Ma” (Saya mau mama ada di sini).
  • Pada tahap ujar dua kata misalnya anak mengatakan seperti  “Ani mainan” yang berarti “Ani sedang bermain dengan mainan” atau kata sifat + kata benda, seperti “kotor patu” yang artinya “Sepatu ini kotor” dan sebagainya.
  • Pada tahap developing grammar misalnya anak mengatakan :
 Cat stand up table” (Kucing berdiri di atas meja);
“What that?” (Apa itu?);
“He play little tune” (dia memainkan lagu pendek);
“Andrew want that” (Saya, yang bernama Andrew, menginginkan itu);
“No sit here” (Jangan duduk di sini!)
  • Pada tahap stuktur kalimat dewasa misalnya anak mengatakan “aku tidak mau bermain dengan dia, karena dia itu nakal”

MESIN TURING
Mesin Turing adalah model yang sangat sederhana dari komputer.  Secara esensial, mesin Turing adalah sebuah finite automaton yang miliki sebuah tape tunggal dengan panjang tak terhingga yang dapat membaca dan menulis data.  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.
Visualisasi dari sebuah mesin Turing diberikan oleh gambar berikut:



Mesin terdiri dari sebuah finite control, yang dapat berada dalam sebuah himpunan berhingga dari state.  Terdapat sebuah tape yang dibagi ke dalam kotak-kotak atau sel-sel.  Setiap sel dapat menampung sebuah dari sejumlah berhingga dari simbol.  Pada awalnya, input yang merupakan string dari simbol dengan panjang berhingga dipilih dari input alphabet, ditempatkan pada tape. Sel-sel tape yang lain, perluasan secara infinite ke kiri dan ke kanan, pada awalnya menampung simbol khusus yang dinamakan blank. Blank bukan sebuah input symbol, dan mungkin terdapat simbol tape yang lain disamping input symbol dan blank.  Terdapat sebuah tape head yang selalu ditempatkan pada salah satu dari sel-sel tape.  Mesin turing dikatakan men-scan sel tersebut. Pada awalnya, tape head berada pada sel paling kiri yang menampung input. Sebuah pergerakan mesin Turing adalah sebuah fungsi dari state dari finite control dan tape symbol yang di-scan.
Dalam satu pergerakan, mesin Turing akan:
  • Merubah state.  Next state dapat sama dengan current state.
  • Menulis sebuah tape symbol dalam sel yang di-scan.  Tape symbol ini mengganti symbol apapun yang ada dalam sel tersebut.  Secara opsional, simbol yang dituliskan dapat sama dengan simbol yang sekarang ada dalam tape.
  • Memindahkan tape head ke kiri atau ke kanan.
Notasi formal Mesin Turing
Mesin Turing dijelaskan oleh 7-tuple:
M = (Q, S, G, d, q0, B, F)
Komponen-komponennya adalah:
  • Q:  Himpunan berhingga dari state dari finite control.
  • S: himpunan berhingga dari simbol-simbol input.
  • G: Himpunan dari tape symbol.  S merupakan subset dari G.
d:  Fungsi transisi.  Argumen d(q, X) adalah sebuah state q dan sebuah tape symbol X.  Nilai dari d(q, X), jika nilai tersebut didefinisikan, adalah triple (p, Y, D), dimana:
  • p adalah next state dalam Q
  • Y adalah simbol, dalam G, ditulis dalam sel yang sedang di-scan, menggantikan simbol apapun yang ada dalam sel tersebut.
  • D adalah arah, berupa L atau R, berturut-turut menyatakan left atau right, dan menyatakan arah dimana head bergerak.
q0: start state, sebuah anggota dari Q, dimana pada saat awal finite control ditemukan.
B: simbol blank.  Simbol ini ada dalam G tapi tidak dalam S, yaitu B bukan sebuah simbol input.
F: himpunan dari final state, subset dari Q.
Deskripsi Instantaneous (ID) untuk Mesin Turing
ID digunakan untuk mengetahui apa yang mesin Turing kerjakan.  ID direpresentasikan oleh string X1X2X3… Xi-1qXiXi+1 … Xn, dimana:
–        q adalah state dari TM
–        Tape head men-scan simbol ke-i dari kiri.
–        X1X2 …Xn adalah bagian dari tape di antara nonblank pada sel paling kiri dan paling kanan.
Pergerakan TM M = (Q, S, G, d, q0, B, F) dinyatakan oleh notasi ├ atau ├. ├*M atau ├*digunakan untuk menunjukkan nol, satu atau lebih pergerakan dari TM.
Anggap d(q, Xi) = (p, Y, L), yaitu pergerakan selanjutnya adalah ke kiri.  Maka
X1X2… Xi-1qXiXi+1 … Xn
├ X1X2… Xi-2pXi-1 YXi+1 … Xn
Pergerakan ini menyatakan perubahan ke state p. Tape head sekarang diposisikan di sel i-1.
Jika i = n dan Y = B maka simbol B yang ditulis pada Xn berhubungan dengan urutan tak hingga dari blank–blank yang mengikuti dan tidak muncul dalam ID selanjutnya.  Dengan demikian
X1X2 …Xn-1 q Xn├ X1X2… Xn-2p Xn-1
Terdapat dua pengecualian:
–          Jika i=1, maka M bergerak ke blank ke bagian kiri dari X1.  Dalam kasus ini,
qX1X2 …Xn├ pBYX2… Xn
–          Jika i = n dan Y = B maka simbol B yang ditulis pada Xn berhubungan dengan urutan tak hingga dari blank–blank yang mengikuti dan tidak muncul dalam ID selanjutnya.  Dengan demikian
X1X2 …Xn-1 q Xn├ X1X2… Xn-2p Xn-1
Anggap d(q, Xi) = (p, Y, R), yaitu pergerakan selanjutnya adalah ke kanan.  Maka
X1X2… Xi-1qXiXi+1 … Xn ├ X1X2… Xi-1 YpXi+1 … Xn
Tape head telah bergerak ke sel i+1.  Terdapat dua pengecualian:
–               Jika i = n, maka sel ke-i+1 menampung sebuah blank, dan sel tersebut bukan bagian dari ID sebelumnya.  Dengan demikian
X1X2 … Xn-1 qXn├ X1 X2… Xn-1YpB
–               Jika i = 1 dan Y = B maka simbol B yang ditulis pada X1 berhubungan dengan urutan tak hingga dari blank–blank dan tidak muncul dalam ID selanjutnya.  Dengan demikian
qX1X2 …Xn├ pX2… Xn
Diagram Transisi untuk Mesin Turing
Diagram transisi terdiri dari sebuah himpunan dari node–node yang menyatakan state–state dari Mesin Turing .sebuah arc dari state q ke state p diberi label oleh satu atau lebih item dengan bentuk X/Y D, dimana X dan Y adalah tape symbol, dan D adalah arah, kiri (L) atau kanan (R).  Bahwa bila d(q, X) = (p, Y, D) diperoleh label X/Y D pada arc dari q ke p. Dalam diagram arah D dinyatakan dengan tanda ¬ untuk “left” dan ® untuk “right”.  Start state ditandai dengan kata “start” dan sebuah panah yang masuk ke dalam state tersebut.  Final state ditandai dengan putaran ganda.
Contoh:
Mesin Turing berikut menghitungan fungsi   , yang dinamakan monus atau propersubstraction.  Fungsi ini didefinisikan oleh  m   n = max(m – n, 0).  Bahwa, m   n = m – n jika m ³ n dan 0 jika m < n.  Mesin Turing yang melakukan operasi ini adalah
M = ({q0, q1, … , q6}, {0, 1}, {0, 1, B}, d, q0, B)
Aturan untuk fungsi transisi d:

Diagram transisi dari mesin Turing M:


Source :
https://riskasimaremare.wordpress.com/2013/04/23/finite-state-automata/
https://guruinformatika.blogspot.co.id/2015/04/materi-ekspresi-reguler-teori-bahasa.html
https://fairuzelsaid.wordpress.com/2011/06/16/tbo-context-free-grammar-cfg/
http://www.theorypsyc.xyz/2013/01/avram-noam-chomsky.html
https://nurmnabil27.wordpress.com/2013/06/07/mesin-turing/
Diposting oleh di

Tidak ada komentar:

Posting Komentar

Langganan: Posting Komentar (Atom)