AUTOMATA dan BAHASA FORMAL”Teorema Kleene”

Author: · Published: April 21, 2009 · Category: Komputer Dasar 

Aris Subiyanto

Suatu Bahasa dapat kita definisikan dengan berbagai cara, dalam pembahasan kali ini menggunakan tiga cara pendefinisisan suatu bahasa yaitu : Dengan menggunakan Ekspresi Reguler, menggunakan Finite Automata, dan menggunakan Graph transisi. “ Jika suatu bahasa dapat didefinisikan oleh salah satu cara pendefinisisan maka akan juga dapat didefinisikan kedua cara yang lainnya “ ( Teorema Kleene 1956). Secara singkat bisa dikatakan bahwa ketiga metode pendefinisian diatas adalah Equivalent.

Teorema Kleene :

Suatu bahasa yang dapat didefinisikan oleh :

1. Ekspresi Reguler; atau

2. Finite Automata; atau

3. Graph Transisi.

Dapat didefinisikan oleh ketiga metode sekaligus.

Proof :

Ketiga bagian pembuktiannya adalah :

Bagian 1 Setiap bahasa yang dapat didefinisikan Finite Automata dapat didefinisikan oleh Graph transisi.
Bagian 2 Setiap bahasa yang dapat didefinisikan oleh Graph transisi dapat didefinisikan oleh Ekspresi reguler.
Bagian 3 Setiap bahasa yang dapat didefinisikan oleh Ekspresi regular dapat didefinisikan dengan Finite Automata.
Secara sederhana bisa diilustrasikan kita ingin membuktikan bahwa himpunan TIC, TAC, TOE adalah sama, maka dicari 1. TIC = TAC, 2. TAC = TOE, 3. TIC = TOE ( TIC ? TAC ? TOE ? TIC ) ?

( TIC = TAC = TOE )

Related Articles

  1. AUTOMATA dan BAHASA FORMAL “Formal Reguler Grammar”
  2. Automata dan Bahasa Formal “Pumping Lemma”
  3. AUTOMATA dan BAHASA FORMAL “Praktika Finite Automata Dengan Output”
  4. Struktur dan Elemen Bahasa Pemrograman
  5. Interkoneksi IPv6 dan IPv4
  6. Python dan MySQL
  7. Operator PHP
  8. Sistem Otomasi
  9. Tips dan Trik JSP
  10. Mencetak Pesan Error
  11. Mobile Business Untuk Aplikasi Horoscope Menggunakan Web Service dan J2ME
  12. Database Link Pada PostgreSQL
  13. Pemrograman Ruby
  14. Tutorial Compiler Bahasa-C Dengan Anjuta IDE
  15. Manajemen Pengetahuan dan Penciptaan Pengetahuan
  16. Database Firebird (Bag. 2)
  17. Visualisasi Metode Pengurutan
  18. Dasar Kriptografi
  19. Latihan bahasa C
  20. Dasar Pemprograman Grafik Pada Bahasa C