Sebelum Kita Membahas Mengenai Terapan Teori Bahasa dan Otomata, Kita Harus mengerti Sejarah yang Menggelutinya dulu.....

Sejarah Teori bahasa dan automata

Otomata bermula sebelum komputer ada pada teori di bidang sistem logika matematika atau formal, ilmuwan David Hilbert telah mencoba menciptakan algoritma umum untuk pembuktian (seluruh) persoalan matematika secara otomatis yaitu mampu menentukan salah benarnya sembarang prosisi matematika.

Tahun 1931, KurtGdel mempublikasikan teori ketidaklengkapan dimana membuktikan prosedur/algoritma yang dikehendaki David Hilbert tersebut tidak akan pernah ada. KurtGdel membangun rumus di kalkulus predikat yang diterapkan pada bilangan bulat yang memiliki pernyataan-pernyataan definisi yang tidak dapat dibuktikan maupun dibantah di dalam sistem logika yang mungkin dibangun manusia.

Formalisasi argumen teorema ketidaklengkapan KurtGdel ini berikut penjelasan dan formalisasi selanjutnya dari prosedur efektif secara intuisi merupakan salah satu pencapaian intelektual terbesar abad 20, yaitu abad dimana formalisasi berkembang semarak.

Pengembangan teori otomata, komputasi dan teori bahasa berikutnya difasilitasi perkembangan bidang psyco-linguistic. Bidang psyco-linguistic berupaya menjawab pertanyan-pertanyan berikut:

- Apakah bahasa secara umum?
- Bagaimana manusia mengembangkan bahasa?
- Bagaimana manusia memahami bahasa?
- Bagaimana manusia mengajarkan bahasa ke anak-anaknya?
- Apa gagasan-gagasan yang dapat dinyatakan dan bagaimana caranya?
- Bagaimana manusia membangun kalimat-kalimat dari gagasan-gagasan yang berada di pikirannya?

Sekitar tahun 1950-an, Noam Chomsky menciptakan model matematika sebagai sarana untuk mendeskripsikan bahasa serta menjawab pertanyaan-pertanyaan di atas. Saat ini dimulai pendalaman bidang bahasa computer.

Perbedaan antara bahasa komputer dan bahasa manusia adalah sampai sekarang belum diketahuinya bagaimana cara manusia mengartikan bahasa, sementara dengan pasti dapat mengartikan bahasa pada komputer.Noam Chomsky mengemukakan perangkat format disebut grammar untuk memodelkan properti-properti bahasa.Grammar berisi sejumlah aturan serta menspesifikasikan bahasa tertentu.Bahasa berisi semua string yang dapat dihasilkan menggunakan aturan-aturan grammar.

Meski pembahasan Chomsky terutama ditujukan untuk bahasa alami, grammar mempunyai nilai/manfaat sangat besar di ilmu informatika/komputer karena pencapaian ini digunakan untuk mendeskripsikan dan mendefinisikan sintaks bahasa pemrograman dan bahasa-bahasa formal lainnya.

Grammar diterapkan pada perancangan kompilator dan bidang-bidang di ilmu komputer.McCulloch dan Pittsmengemukakan Mesin Abstrak sederhana yaitu finite automata untuk memodelkan neuron nets.Finite automata juga digunakan untuk merancang switching circuit.

Studi mengenai teori otomata terkait bidang-bidang lain di ilmu komputer.Kemudian ekivalensi antara finite automata dan ekspresi reguler (reguler expression) dikemukakan Stephen Kleene. Sejak saat itu teori bahasa dikaitkan secara erat dengan teori bahasa formal. ubungan teori otomata dan teori pengkodean (coding theory) juga banyak diteliti.

Turing machine seperti komputer modern saat ini dapat mengolah (simbol-simbol di tape) dan mengahasilkan keluaran (simbol-simbol yang berada di tapenya setelah berakhirnya sebarisan pergerakkan) merupakan karya teoritis dari Alan Turing.

Penerapan Bahasa dan Automata Dalam konsep Keilmuan

Teori automata yang selama ini lebih banyak diterapkan dalam bidang tata bahasa formal khususnya dalam pengembangan sebuah compiler, juga dapat digunakan untuk melakukan pemodelan dan pendekatan pemecahan masalah masalah yang berkaitan dengan aplikasi-aplikasi di dalam bidang kecerdasan Buatan. Bahkan pada beberapa masalah spesifik yang berkaitan dengan keputusan dan model mesin hanya tepat jika solusinya didasarkan pada solusi automata.Kelebihan penggunaan teori automata dibanding pohon keputusan dalam memodelkan ruang keadaan adalah lebih sederhana jika terdapat beberapa keadaan yang berulang. Penerapan teoritis automata untuk pengembangan suatu sistem adalah dengan menggunakan teori automata sebagai sebuah paradigma yang menggabungkan spesifikasi sistem, verifikasi dan sintesis.

A. Kecerdasan buatan

Kecerdasan Buatan adalah bidang ilmu yang mendasarkan bagaimana sebuah komputer bisa bertindak seperti dan sebaik manusia. Dewasa ini, Penggunaan kecerdasan buatan dibutuhkan diberbagai disiplin ilmu. Irisan antara psikologi dan kecerdasan Buatan melahirkan area cognition and psycolinguistic. Irisan antara teknik elektro dengan kecerdasan buatan melahirkan ilmu : pengolahan citra, teori kendali, pengenalan pola dan robotika. Irisan ilmu manajemen dan kecerdasan buatan menghasilkan sistem pendukung keputusan. Adanya irisan penggunaan kecerdasan buatan diberbagai disiplin ilmu menyebabkab cukup rumitnya untuk mengklasifikasikan lingkup bidang ilmu kecerdasan buatan, sehingga pengklasifikasian lingkup kecerdasan buatan didasarkan pada output yang diberikan yaitu pada aplikasi komersial.

Lingkup aplikasi kecerdasan buatan meliputi :

1. sistem pakar

2. Pengolahan bahasa alami

3. Pengenalan ucapan

4. Robotika dan sistem sensor

5. Computer vision

6. Problem solving and planning

7. Permainan

Contoh Penerapan Teori Bahasa & Otomata

seperti : "bikin aplikasi kalkulator pertambahan pake java"

contoh sederhana gw sekarang bikin apliaksi kalkulator pertambahan (simple aja) pake automata

jadi aturan produksinya kayak gini :

S = A + A + A + …
A = 1…n
n = (Max Integer)

jadi sekarang tingal kita buat DFA nya

, singkat cerita dah gw buat kayak gini :

wew, jadi gini keterangannya :

A = State Awal
B = Final State
A(1…9) -> B
B(0…9) -> B
B(+) -> C
C(1…9) -> B

btw, ngerti gak ama diagram DFA diatas? kalo gak ngerti mungkin harus belajar automata dulu

sekarang kita bua refresentasi dari A, B, C

nah karena A, B, C punya kesamaan, yaitu sebagai State jadi kita kita buat aja interface untuk State yang isinya validateCharacter(char), isFinalState(), isStartState()


01 /*

02  *  BACA DENGAN TELITI !!!

03  *

04  *  Anda boleh menggunakan, mengubah, menghapus, menambah, dan

05  *  melakukan hal yang anda inginkan ke dalam source code ini.

06  *

07  *  Dan saya tidak bertanggung jawab atas kesalahan,

08  *  bug, atau keanehan yang ada dalam source code ini, dan

09  *  saya juga TIDAK MENERIMA PERTANYAAN dari Anda

10  *  mengenai isi source code ini.

11  *

12  *  Semoga source code ini bermanfaat bagi Anda, dan juga

13  *  bermanfaat bagi project yang sedang Anda buat.

14  *

15  *  Salam dari kulo.

16  */

17 package org.eecchhoo.wordpress.automata;

18 

19 /**

20  *

21  * @author echo

22  */

23 public interface State {

24 

25     public boolean isStartState();

26 

27     public boolean isFinalState();

28 

29     public State validateChar(Character c) throws Exception;

30 }

Sekarang kita buat untuk penampung karakter nya :


01 /*

02  *  BACA DENGAN TELITI !!!

03  *

04  *  Anda boleh menggunakan, mengubah, menghapus, menambah, dan

05  *  melakukan hal yang anda inginkan ke dalam source code ini.

06  *

07  *  Dan saya tidak bertanggung jawab atas kesalahan,

08  *  bug, atau keanehan yang ada dalam source code ini, dan

09  *  saya juga TIDAK MENERIMA PERTANYAAN dari Anda

10  *  mengenai isi source code ini.

11  *

12  *  Semoga source code ini bermanfaat bagi Anda, dan juga

13  *  bermanfaat bagi project yang sedang Anda buat.

14  *

15  *  Salam dari kulo

16  */

17 package org.eecchhoo.wordpress.automata;

18 

19 import java.util.List;

20 

21 /**

22  *

23  * @author echo

24  */

25 public interface CharHelper {

26 

27     public List acceptedCharacters();

28 

29     public State getState();

30 }

sekarang kita buat implementasinya :

ini implementasi CharHelper :


01 /*

02  *  BACA DENGAN TELITI !!!

03  *

04  *  Anda boleh menggunakan, mengubah, menghapus, menambah, dan

05  *  melakukan hal yang anda inginkan ke dalam source code ini.

06  *

07  *  Dan saya tidak bertanggung jawab atas kesalahan,

08  *  bug, atau keanehan yang ada dalam source code ini, dan

09  *  saya juga TIDAK MENERIMA PERTANYAAN dari Anda

10  *  mengenai isi source code ini.

11  *

12  *  Semoga source code ini bermanfaat bagi Anda, dan juga

13  *  bermanfaat bagi project yang sedang Anda buat.

14  *

15  *  Salam dari kulo

16  */

17 package org.eecchhoo.wordpress.automata;

18 

19 import java.util.List;

20 

21 /**

22  *

23  * @author echo

24  */

25 public class DefaultCharHelper implements CharHelper {

26 

27     private State state;

28 

29     private List acceptedCharacters;

30 

31     public DefaultCharHelper() {

32     }

33 

34     public DefaultCharHelper(State state, List acceptedCharacters) {

35         this.state = state;

36         this.acceptedCharacters = acceptedCharacters;

37     }

38 

39     public void setAcceptedCharacters(List acceptedCharacters) {

40         this.acceptedCharacters = acceptedCharacters;

41     }

42 

43     public void setState(State state) {

44         this.state = state;

45     }

46 

47     public List acceptedCharacters() {

48         return acceptedCharacters;

49     }

50 

51     public State getState() {

52         return state;

53     }

54 }

ini implementasi State :


01 /*

02  *  BACA DENGAN TELITI !!!

03  *

04  *  Anda boleh menggunakan, mengubah, menghapus, menambah, dan

05  *  melakukan hal yang anda inginkan ke dalam source code ini.

06  *

07  *  Dan saya tidak bertanggung jawab atas kesalahan,

08  *  bug, atau keanehan yang ada dalam source code ini, dan

09  *  saya juga TIDAK MENERIMA PERTANYAAN dari Anda

10  *  mengenai isi source code ini.

11  *

12  *  Semoga source code ini bermanfaat bagi Anda, dan juga

13  *  bermanfaat bagi project yang sedang Anda buat.

14  *

15  *  Salam saking kulo

16  */

17 package org.eecchhoo.wordpress.automata;

18 

19 import java.util.LinkedList;

20 import java.util.List;

21 

22 /**

23  *

24  * @author echo

25  */

26 public class DefaultState implements State {

27 

28     private boolean startState;

29 

30     private boolean finalState;

31 

32     private List charHelpers = new LinkedList();

33 

34     public DefaultState(boolean startState, boolean finalState) {

35         this.startState = startState;

36         this.finalState = finalState;

37     }

38 

39     public DefaultState(boolean startState, boolean finalState, List charHelpers) {

40         this.startState = startState;

41         this.finalState = finalState;

42         this.charHelpers = charHelpers;

43     }

44 

45     public void addCharHelper(CharHelper charHelper) {

46         charHelpers.add(charHelper);

47     }

48 

49     public boolean isStartState() {

50         return startState;

51     }

52 

53     public boolean isFinalState() {

54         return finalState;

55     }

56 

57     public State validateChar(Character c) throws Exception {

58         for (CharHelper helper : charHelpers) {

59             if (helper.acceptedCharacters().contains(c)) {

60                 return helper.getState();

61             }

62         }

63         throw new Exception();

64     }

65 }

dan sekarang kita buat StateManagernya :


01 /*

02  *  BACA DENGAN TELITI !!!

03  *

04  *  Anda boleh menggunakan, mengubah, menghapus, menambah, dan

05  *  melakukan hal yang anda inginkan ke dalam source code ini.

06  *

07  *  Dan saya tidak bertanggung jawab atas kesalahan,

08  *  bug, atau keanehan yang ada dalam source code ini, dan

09  *  saya juga TIDAK MENERIMA PERTANYAAN dari Anda

10  *  mengenai isi source code ini.

11  *

12  *  Semoga source code ini bermanfaat bagi Anda, dan juga

13  *  bermanfaat bagi project yang sedang Anda buat.

14  *

15  *  Salam sakeng kulo

16  */

17 package org.eecchhoo.wordpress.automata;

18 

19 import java.util.ArrayList;

20 import java.util.List;

21 import java.util.StringTokenizer;

22 

23 /**

24  *

25  * @author echo

26  */

27 public class StateManager {

28 

29     private State state;

30 

31     public StateManager(State state) {

32         this.state = state;

33     }

34 

35     public Integer calculate(String input) throws Exception {

36         char[] chars = input.toCharArray();

37 

38         for (char c : chars) {

39             // cek input

40             state = state.validateChar(c);

41         }

42 

43         // cek apakah state akhir merupakan final state

44         if (!state.isFinalState()) {

45             // jika tidak berarti error

46             throw new Exception();

47         }

48 

49         return calculateValidString(input);

50     }

51 

52     protected Integer calculateValidString(String input) {

53         StringTokenizer tokenizer = new StringTokenizer(input, "+");

54         List strings = new ArrayList();

55 

56         while (tokenizer.hasMoreTokens()) {

57             strings.add(tokenizer.nextToken());

58         }

59 

60         Integer result = 0;

61         for (String string : strings) {

62             result += Integer.parseInt(string);

63         }

64 

65         return result;

66     }

67 }

setelah itu tinggal buat deklarasi karakter yang diterima ama aplikasi yang kita buat , karena dari diagram tadi kita nerima input cuma 0…9 dan karakter ‘+’ jadi kayak gini dibuatnya, dan sebelumnya kita kumpulkan juga menjadi group :


01 /*

02  *  BACA DENGAN TELITI !!!

03  *

04  *  Anda boleh menggunakan, mengubah, menghapus, menambah, dan

05  *  melakukan hal yang anda inginkan ke dalam source code ini.

06  *

07  *  Dan saya tidak bertanggung jawab atas kesalahan,

08  *  bug, atau keanehan yang ada dalam source code ini, dan

09  *  saya juga TIDAK MENERIMA PERTANYAAN dari Anda

10  *  mengenai isi source code ini.

11  *

12  *  Semoga source code ini bermanfaat bagi Anda, dan juga

13  *  bermanfaat bagi project yang sedang Anda buat.

14  *

15  *  Salam sakeng kulo

16  */

17 package org.eecchhoo.wordpress.automata;

18 

19 import java.util.ArrayList;

20 import java.util.List;

21 

22 /**

23  *

24  * @author echo

25  */

26 public class StateUtilities {

27 

28     private static List zeroToNine;

29 

30     private static List oneToNine;

31 

32     private static List operators;

33 

34     public static List getOneToNine() {

35         if (oneToNine == null) {

36             oneToNine = new ArrayList();

37             oneToNine.add('1');

38             oneToNine.add('2');

39             oneToNine.add('3');

40             oneToNine.add('4');

41             oneToNine.add('5');

42             oneToNine.add('6');

43             oneToNine.add('7');

44             oneToNine.add('8');

45             oneToNine.add('9');

46         }

47         return oneToNine;

48     }

49 

50     public static List getOperators() {

51         if (operators == null) {

52             operators = new ArrayList();

53             operators.add('+');

54         }

55         return operators;

56     }

57 

58     public static List getZeroToNine() {

59         if (zeroToNine == null) {

60             zeroToNine = new ArrayList();

61             zeroToNine.add('0');

62             zeroToNine.add('1');

63             zeroToNine.add('2');

64             zeroToNine.add('3');

65             zeroToNine.add('4');

66             zeroToNine.add('5');

67             zeroToNine.add('6');

68             zeroToNine.add('7');

69             zeroToNine.add('8');

70             zeroToNine.add('9');

71         }

72         return zeroToNine;

73     }

74 }

sekarang tinggal buat aplikasinya :


01 /*

02  *  BACA DENGAN TELITI !!!

03  *

04  *  Anda boleh menggunakan, mengubah, menghapus, menambah, dan

05  *  melakukan hal yang anda inginkan ke dalam source code ini.

06  *

07  *  Dan saya tidak bertanggung jawab atas kesalahan,

08  *  bug, atau keanehan yang ada dalam source code ini, dan

09  *  saya juga TIDAK MENERIMA PERTANYAAN dari Anda

10  *  mengenai isi source code ini.

11  *

12  *  Semoga source code ini bermanfaat bagi Anda, dan juga

13  *  bermanfaat bagi project yang sedang Anda buat.

14  *

15  *  Salamsakeng kulo

16  */

17 package org.eecchhoo.wordpress.automata;

18 

19 import javax.swing.JOptionPane;

20 

21 /**

22  *

23  * @author echo

24  */

25 public class CalculatorPertambahan {

26 

27     /**

28      * @param args the command line arguments

29      */

30     public static void main(String[] args) {

31         // Buat State (Dalam Diagram Sebagai Lingkaran)

32         DefaultState A = new DefaultState(true, false);

33         DefaultState B = new DefaultState(true, true);

34         DefaultState C = new DefaultState(true, false);

35 

36         // Buat helper (Dalam Diagram Sebagai Garis)

37         CharHelper helper1 = new DefaultCharHelper(B, StateUtilities.getOneToNine());

38         CharHelper helper2 = new DefaultCharHelper(B, StateUtilities.getZeroToNine());

39         CharHelper helper3 = new DefaultCharHelper(C, StateUtilities.getOperators());

40         CharHelper helper4 = new DefaultCharHelper(B, StateUtilities.getOneToNine());

41 

42         // masukan garis ke lingkaran

43         A.addCharHelper(helper1);

44         B.addCharHelper(helper2);

45         B.addCharHelper(helper3);

46         C.addCharHelper(helper4);

47 

48         // buat state manager

49         StateManager manager = new StateManager(A);

50 

51         // masukkan input

52         String input = JOptionPane.showInputDialog("Masukkan Input Pertambahan : ");

53         if (input != null) {

54             try {

55                 JOptionPane.showMessageDialog(null, manager.calculate(input));

56             } catch (Exception e) {

57                 JOptionPane.showMessageDialog(null, "input yang dimasukkan tidak valid");

58             }

59         }

60     }

61 }