Senin, 30 Maret 2020

Makalah TEORI BAHASA DAN AUTOMATA


BAB I
PENDAHULUAN
A.    Latar Belakang
Teori bahasa dan automata merupakan salah satu mata kuliah yang wajib dijurusan-jurusan sistem informasi maupun ilmu komputer. Diasumsikan para pembaca telah terbiasa dengan notasi-notasi yang digunakan disini, misalnya mengenai hinpunan, yang telah diperoleh dari kuliah-kuliah sebelumnya. Meskipun demikian bagi mereka diluar disiplin informatika dapat pula segera memahaminya karena telah diusahakan untuk sebisa mungkin memberikan penjelasan yang memadai untuk setiap hal baru yang disampaikan.
Dimakalah ini kami akan fokus untuk menjelaskan berbagai hal mengenai Teori bahasa dan automata. Sub-sub dari teori bahasa dan automata ini seperti String, Grammar dan Mesin turing pun akan kami jelaskan dalam makalah ini.
B.     Rumusan Masalah
Kita harus mengerti dan memahami tentang :
1.      Apa itu teori bahasa?
2.      Apa itu otomata?
3.      Apa itu string?
4.      Apa itu grammar?
5.      Apa itu mesin turing?




BAB II
PEMBAHASAN

A.    TEORI BAHASA DAN AUTOMATA
1.      Teori Bahasa
Teori bahasa membicarakan bahasa formal (formal language), terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor). Bahasa formal adalah kumpulan kalimat. Semua kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama. Sebuah bahasa formal bisa dibangkitkan oleh dua atau lebih tata bahasa berbeda. Dikatakan bahasa formal karena grammar diciptakan mendahului pembangkitan setiap kalimatnya. Bahasa manusia bersifat sebaliknya; grammar diciptakan untuk meresmikan kata-kata yang hidup di masyarakat. Dalam pembicaraan selanjutnya ‘bahasa formal’ akan disebut ‘bahasa’ saja.
2.      Automata
Automata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu. Automata berasal dari bahasa Yunani automatos, yang berarti sesuatu yang bekerja secara otomatis (mesin). Istilah automaton sebagai bentuk tunggal dan automata sebagai bentuk jamak. Teori Automata adalah teori tentang mesin abstrak yang :
·         bekerja sekuensial
·         menerima input
·         mengeluarkan output
Pengertian mesin bukan hanya mesin elektronis/mekanis saja melainkan segala sesuatu (termasuk perangkat lunak) yang memenuhi ketiga ciri di atas. Penggunaan automata pada perangkat lunak terutama pada pembuatan kompiler bahasa pemrograman.
dua fungsi automata dalam hubungannya dengan bahasa, yaitu :
·         fungsi automata sebagai pengenal (RECOGNIZER) string-string dari suatu bahasa, dalam hal ini bahasa sebagai masukan dari automata
·         fungsi automata sebagai pembangkit (GENERATOR) string-string dari suatu bahasa, dalam hal ini bahasa sebagai keluaran dari automata
Untuk mengenali string-string dari suatu bahasa, akan dimodelkan sebuah automaton yang memiliki komponen sebagai berikut :
1.      Pita masukan, yang menyimpan string masukan yang akan dikenali;
2.      Kepala pita (tape head), untuk membaca/menulis ke pita masukan;
3.      Finite State Controller (FSC), yang berisi status-status dan aturan-aturan yang mengatur langkah yang dilakukan oleh automaton berdasarkan status setiap saat dan simbol masukan yang sedang dibaca oleh kepala pita;
4.      Pengingat (memory), untuk tempat penyimpanan dan pemrosesan sementara.
5.      Automaton pengenal, setelah membaca string masukan dan melakukan langkahlangkah pemrosesan yang diperlukan, akan mengeluarkan keputusan apakah string tersebut dikenali atau tidak.
 Konfigurasi adalah suatu mekanisme untuk menggambarkan keadaan suatu mesin pengenal, yang terdiri atas :
·         Status FSC
·         Isi pita masukan dan posisi kepala pita
·         Isi pengingat
Mesin pengenal bersifat deterministik bila dalam setiap konfigurasi, hanya ada satu kemungkinan yang dapat dilakukan mesin, jika tidak mesin pengenal bersifat non deterministik. Bahasa dalam bentuk tulisan terdiri atas simbol-simbol satuan yang jika dikombinasikan akan mempunyai arti yang berbeda-beda.
Simbol-simbol yang bisa dipergunakan dalam sebuah bahasa terbatas jumlahnya, yang membentuk sebuah himpunan dan disebut sebagai abjad (alphabet). Kadangkala digunakan istilah karakter yang maknanya sama dengan simbol. Deretan karakter membentuk string. Bahasa (language) didefinisikan sebagai himpunan semua string yang dapat dibentuk dari suatu abjad. Kaidah/aturan pembentukan kata/kalimat disebut tata bahasa (grammar).
Sebagai keluaran dari automata, Bahasa memungkinkan penyampaian gagasan dan pemikiran, tanpa itu komunikasi akan sulit terjadi. Dalam lingkungan pemprograman komputer, bahasa pemprograman bertindak sebagai sarana komunikasi antara manusia dan permasalahannya dengan komputer yang dipakai untuk membantu memperoleh pemecahan.
Suatu solusi untuk suatu masalah akan menjadi lebih mudah bila bahasa pemprograman lebih dekat dengan permasalahan tersebut. Oleh karena itu, bahasa harus memiliki konstruksi yang merefleksikan masalah dan independen dari komputer yang dipergunakan. Komputer digital, disisi lain, hanya menerima dan memahami bahasa tingkat rendah mereka sendiri, terdiri dari deretan nol dan satu, yang sulit dipahami oleh manusia.
Selain bahasa juga bisa menggunakan otomata sebagai media, otomata adalah ilmu yang mempelajari mengenai mesin abstrak, bisa disebut pula adalah suatu model abstrak dari komputer digital yang dapat menerima input secara sekuensial dan dapat mengeluarkan output. Setiap otomata memiliki beberapa fungsi dasar, dapat membaca input berupa string dari alphabet yang diberikan dari input file.
Otomata merupakan suatu sistem yang terdiri dari sejumlah berhingga status, dimana setiap status tersebut menyatakan informasi mengenai input yang lalu, dan dapat pula dianggap sebagai mesin memori. Input pada mesin otomata dianggap sebagai bahasa yang harus dikenali oleh mesin. Disajikan dengan suatu input string, suatu acceptor apakah akan menerima (mengenali) string tersebut atau menolaknya. Otomata yang lebih umum yaitu yang mampu menghasilkan string output, dikenal dengan Tranducer.
3.      Contoh Penggunaan Automata
Sebagai contoh penggunaan otomata adalah:
a.       Mesin Turing.
b.      Mesin Karakter
c.       Kompiler
d.      Mesin Jaja (Vending Machine)
Setelah kita mengetahui definisi bahasa dan automata, pertanyaan selanjutnya adalah apakah hubungan antara teori automata dan bahasa formal ? Secara garis besar ada dua fungsi automata dalam hubungannya dengan bahasa, yaitu :
a.       Fungsi automata sebagai pengenal (RECOGNIZER) string-string dari suatu bahasa, dalam hal ini bahasa sebagai masukan dari automata.
b.      Fungsi automata sebagai pembangkit (GENERATOR) string-string dari suatu bahasa, dalam hal ini bahasa sebagai keluaran dari automata.
Di dalam praktik teori bahasa dan otomata (tbo) terdapat beberapa pembelajaran yang diajarkan kepada mahsiswa seperti finite state automata, deterministic finite automata, nondeterministic finite automata, grammar, regular expression, mesin turing, dan lain-lain. Di dalam tbo juga dijelaskan juga teori tentang finite state machine (fsm) yang di dalamnya juga dijelaskan beberapa fungsi seperti fsm with output dan fsm with no output, dalam fsm with output dijelaskan dua fungsi yaitu meanly machine dan moore machine, dan juga dalam fsm with no output dijelaskan juga beberapa fungsi yaitu finite state automata, deterministic finite automata, non-deterministik finite sutomata, grammar. Yang sering digunakan dalam pembelajaran di teori dan di praktik adalah finite state machine with no output seperti finite state automata, deterministic automata, dan lain-lain, akan tetapi dalam pembelajaran jarang sekali membahas finite state machine with output.
B.     STRING
1.Pengertian String
        String dalam pemrograman komputer  adalah sebuah deret simbol. Tipe data string adalah tipe data yang digunakan untuk menyimpan barisan karakter.
Bahasa C++ merupakan turunan dari bahasa C sehingga representasi string sebagai larik karakter masih berlaku. Namun bahasa C++ juga menyediakan tipe data string yang terdapat dalam C++ Standard Template Library (STL).
 Di PHP String adalah kumpulan dari karakter, bilangan, spasi, dan yang lainnya yang berada dalam tanda petik.
2.       Pendeklarasian Srting
    Contoh deklarasi string :Akan dideklarasikan array str untuk menampung string sepanjang 6 (enam)       karakter,
maka :
Char str [ 7 ] = “ string “ ; atau
Char str [ 7 ] = {‘s’, ‘t’, ‘r’, ’i’, ‘n’, ‘g’, ‘\0’ } ;
Deklarasi Variabel String :
Karena string merupakan array dari char, maka pendeklarasiannya sama dengan mendeklarasikan array dari char, yaitu :
                                   Char nama_var [ jml_karakter ]
Contoh :
      Char alamat [40] –> deklarasi variabel alamat dengan tipe data string. 
      Nilai Variabel alamat terdiri dari beberapa karakter maksimal 40 karakter (0 s/d 39)
3.       Fungsi-fungsi Manipulasi Pada String
a.      Fungsi strcat()
: berfungsi untuk menggabungkan string
            Untuk menggunakan fungsi strcat harus menambahkan file header <string.h>
B.U    = strcat (tujuan, sumber)
Contoh :
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <iostream.h>
main()
{
char nmdepan[20],nmbelakang[20];
clrscr();
cout<<"Masukkan nama depan    = ";gets(nmdepan);
cout<<"Masukkan nama belakang = ";gets(nmbelakang);
cout<<endl;
cout<<"Nama Lengkap Saya adalah ="<<strcat(nmdepan , nmbelakang);
getch();
}

b.      Fungsi strlen()
berfungsi untuk mengtahui panjang suatu string
Untuk menggunakan fungsi strlen harus menambahkan file header <string.h>
B.U    = strlen (variabel)
Contoh:
#include <stdio.h>
#include <conio.h>
#include <string.h>
main()
{
char nama [80];
int panjang;
printf("Masukan nama anda: ");gets(nama);
panjang=strlen(nama);
printf("Panjang nama anda adalah %i karakter\n",panjang);
getch();
}
c.       Fungsi strcpy()
 berfungsi untuk menyalin isi suatu string ke string lain
Untuk menggunakan fungsi strlen harus menambahkan file header <string.h>
B.U    = strcpy (var_tujuan string_asal)
Contoh:
#include <conio.h>
#include <string.h>
#include <iostream.h>
main()
{
char huruf[20];
char pindah[20];
clrscr();
cout<<"Masukkan Sembarang Kata = ";gets(huruf);
strcpy(pindah, huruf);
cout<<"Pemindahannya =  "<<pindah;
getch();
}
d.      Fungsi strchr()
: berfungsi untuk mencari karakter dari suatu string, jika ditemukan maka akan mengembalikan (menampilkan )string mulai dari karakter yang di cari, jika tidak maka fungsi mengembalika ke  nilai 0
Untuk menggunakan fungsi strlen harus menambahkan file header <string.h>
B.U    = char*strchr(const char* S, int ch)
Contoh:
#include <iostream.h>
#include <conio.h>
#include <string.h>
main()
{
char*s ="saya suka belajar C++ : (T,T) ";
char*cari;
cari=strchr(s,'u');
cout<<cari<<endl;
getch();
}
e.       Fungsi strcmp()
: fungsi ini di gunakan untuk membandingkan string pertama dan string kedua. hasil dari fungsi ini bertipe data integer (int).
0 (nol)                               = jika a1 sama dengan a2
Kurang dari 0 (negative)  = jika a1 lebih keci dari a2
Lebih dari 0 (positif)        = jika a1 lebih besar dari a2
Untuk menggunakan fungsi strcmp harus menambahkan file header <string.h>
B.U    = var_int=strcmp(str1,str2)

Contoh:
#include <iostream.h>
#include <string.h>
#include <conio.h>
main()
{
char a1[] ="ICHSAN";
char a2[] ="ichsan";
clrscr();
cout<<"hasil perbandingan "<<a1<<" dan "<<a1<<"=";
cout<<strcmp(a1,a1)<<endl;
cout<<"hasil perbandingan "<<a2<<" dan "<<a1<<"=";
cout<<strcmp(a2,a1)<<endl;
cout<<"hasil perbandingan "<<a1<<" dan "<<a2<<"=";
cout<<strcmp(a1,a2)<<endl;
getch();
C.    GRAMMAR
1.      Pengertian Grammar
Suatu kumpulan aturan (production) yang menentukan urut-urutan karakter. Suatu formal grammar adalah grammar biasa yang ditentukan dengan menggunakan notasi yang ketat.
2.      Jenis Grammar
Bahasa Pemrograman ditentukan  2 jenis Grammar :
a.       Primary Grammar
Disebut juga phrase-structure grammar, menspesifikasikan bagian utama pada kompilator dan interpreter, yang disebut parser. Grammar ini menspesifikasikan bagaimana kata-kata dalam bahasa pemrograman dapat tergabung dan membentuk  program yang valid secara sintaks. Parsing adalah istilah pada bahasa yang menggambarkan proses analisis sebuah kalimat bahasa menurut grammarnya.
b.       Secondary Grammar
Umumnya digunakan untuk menspesifikasikan bentuk  yang benar, spelling dari kata-kata pada bahasa komputer  à disebut dengan grammar leksikal. Bagian dari kompilator yang menganalisis kata-kata secara individu pada input program disebut scanner.
Ada dua kelas grammar yang berguna untuk teknologi compiler, yaitu:
a)      EBNF Grammar
•EExtended Backus-Naus Form
•Metalanguage: Bahasa yang digunakan untuk mendeskripsikan bahasa lain.
•Menggunakan notasi matematis, ::=, <, >, |, *, +, {, }, [, ] disebut Metasymbol.
•Suatu bahasa yang dideskripsikan dalam EBNF merupakan suatu kumpulan aturan.
b)      Regular Grammar
• Regular Grammar  disebut juga Regular Language.
 •Digunakan pada Teori Bahasa Otomata (Mesin abstrack yang menggunakan model matematika, tetapi menggunakan matematika yang benar-benar berbeda dengan matematika klasik dan kalkulus)
• Bahasa  pemrograman yang menggunakan aturan sintaktik bahasa regular ini antara lain: Javascript & Perl. 
Dalam hierarki-bahasa  Chomsky, grammar regular adalah grammar paling restriktif yang dapat membangkitkan sebuah kalimat.
Dalam hierarki tersebut, grammar regular mempunyai kemampuan pembangkitan kalimat yang sangat  minimal karena:
1.  Sisi kiri hanya boleh berisi sebuah nonterminal,
2.  Sisi kanan dalam setiap aturan produksinya hanya boleh berisi satu nonterminal, dan posisinya hanya boleh berada di akhiratausisi kanan rangkaian.
Deskripsi yang lebih sederhana, parser untuk  grammar ini tidak dapat mengetahui konteks pemunculan nonterminal  yang tengah didefinisikan, dan hanya dapat melihat  symbol terminal yang ada tepat didepannya.
Terminal Symbols, Alphabet dan Strings
Alphabet : representasi letter yang ditulis dalam huruf kecil (a,b,c,…z)
Terminal Simbol (T) : individual karakter, termasuk di dalamnya adalah alphabet {a,b,….z, 0,1,…9}
Strings : urutan simbol terbatas (sequence finite symbol)
  contoh : aba, ab12z, axy
  operasi yang dapat dilakukan pada strings : substrings, concatenation.
Non Terminal (NT) : kumpulan string alphabeth yang ada pada formal language.
  Non Terminal direpresentasikan dalam huruf  besar (A,B,….) dan diapit dengan
  tanda <..> untuk membedakannya dengan string.
Konsep T dan NT direpresentasikan dalam Produksi.
  Bentuk Umum Produksi   NT ::= string T atau NT
Derivasi & Reduksi
•Derivasi merupakan uraian dari suatu Produksi.
•Reduksi proses perubahan string ke dalam NT sehingga menjadi suatu grammar production.
3.       Klasifikasi Grammar
Chomsky (1963) mengklasifikasikan Grammar menjadi 4 kategori :
a.      Grammar Type-0
• Disebut Phrase Structure Grammar atau grammar tidak terbatas
• Bentuknya : a ::= ß
Dimana, a dan ß dapat berupa T atau NT, yang dapat saling bersubstitusi, karenanya tidak relevan untuk bahasa pemrograman.
b.      Grammar Type-1
•Disebut Context Sensitive Grammar (CSG), produksi dari grammar ini adalah derivasi/reduksi dari particular  string yang hanya terdapat pada particular context
•Bentuknya :
  a Aß ::= apß
•Dimana, p menggantikan A untuk menutupi string a dan ß .
•Grammar ini-pun tidak relevan untuk bahasa pemrograman.
c.       Grammar Type-2
•Disebut Context Free Grammar (CFG), grammar ini tidak membutuhkan context pengenal  atau derivasi
•Bentuknya : A ::= p
•Grammar ini digunakan pada ALGOL-60 dan PASCAL
d.      Grammar Type-3
•Disebut Linier atau RegularGrammar, dimana dapat berupa single terminal simbol dan terminal  simbol atau kebalikannya
•Bentuknya : A ::= t B | t  atau A ::= B t | t
•Bentuk ini banyak dijumpai pada bahasa pemrograman.
e.       CFG (Context Free Grammar)
•CFG ditemukan untuk membantu menspesifikasikan bahasa manusia dan ternyata sangat cocok untuk mendefinisikan bahasa komputer, menyederhanakan penerjemahan bahasa komputer dan aplikasi-a
•CFG digunakan untuk menspesifikasikan struktur sintaks bahasa pemrograman serta beragam basis data.
•CFG adalah sekumpulan berhingga variabel yang juga disebut nonterminal atau kategori sintaks, dimana masing-masing mempresentasikan bahasa. Bahasa-bahasa yang direpresentasikan dengan variabel-variabel itu yang dideskripsikan secara rekursif dalam bentukan lain dan symbol-simbol primitif disebut terminal. Aturan-aturan yang berhubungan dengan variabel-variabel itu disebut produksi.

D.    MESIN TURING
1.      Pengertian
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

4.      Komponen-komponen 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.
5.      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
6.      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 proper substraction.  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:












BAB III
PENUTUP
A.    Kesimpulan
Teori bahasa membicarakan bahasa formal (formal language), terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor).  Automata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu. Automata berasal dari bahasa Yunani automatos, yang berarti sesuatu yang bekerja secara otomatis (mesin).  String dalam pemrograman komputer  adalah sebuah deret simbol. Tipe data string adalah tipe data yang digunakan untuk menyimpan barisan karakter.  Grammar adalah suatu kumpulan aturan (production) yang menentukan urut-urutan karakter. Suatu formal grammar adalah grammar biasa yang ditentukan dengan menggunakan notasi yang ketat.  Mesin Turing adalah model yang sangat sederhana dari komputer.  Secara esensial, mesin Turing adalah sebuah finite automata yang miliki sebuah tape tunggal dengan panjang tak terhingga yang dapat membaca dan menulis data.
B.     Saran
Setelah kita mengetahui tentang apa itu teori bahasa dan automata, maka tidak ada salahnya kalau kita berbagi apa yang kita ketahui kepada seseorang yang ingin belajar dan mempraktekkannya seperti apa yang di terangkan oleh teori-teori.







DAFTAR PUSTAKA

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. 2001. Introduction to Automata Theory, Languange, and Computation.


Tidak ada komentar:

Posting Komentar