Materi 14: Bahasa Formal & Mesin Status Terhingga

Apa itu Bahasa Formal?

Bahasa Formal adalah bahasa yang harus mengikuti aturan ketat seperti bahasa pemrograman dan bahasa matematis (aljabar, logika proposisi). Berbeda dengan bahasa natural (sehari-hari) yang fleksibel, bahasa formal bersifat kaku dan presisi.

Bahasa Natural

Seperti jalan raya bebas:

Kata-kata bisa menyerobot, berhenti tiba-tiba
Banyak cara mencapai makna yang sama
Sering ambigu: "Makan tuh anjing!"

Bahasa Formal

Seperti rel kereta api:

Harus mengikuti rel (aturan) dengan presisi
Tidak ada pilihan keluar jalur
Satu jalur = satu makna tanpa keraguan

Contoh Perbandingan

Fitur	Bahasa Natural	Bahasa Formal
Aturan	Fleksibel, bisa dilanggar	Kaku, kalau salah = gagal
Ambiguitas	Wajar & sering	Dilarang keras
Tujuan	Komunikasi manusia	Instruksi mesin
Contoh	Novel, chat, puisi	Python, rumus logika, kode IBAN

Demo Cepat: Finite Automata

Finite Automata untuk mengenali bilangan biner genap (berakhir dengan 0):

Q = {q0, q1}
Σ = {0, 1}
q₀ = q0
F = {q0}

Fungsi Transisi δ:
δ(q0, 0) = q0
δ(q0, 1) = q1
δ(q1, 0) = q1
δ(q1, 1) = q0

Fakta Menarik

Level terendah hirarki mesin & bahasa?

Automata Terhingga (Finite Automata) adalah level terendah dalam hirarki mesin dan bahasa formal.

Penemu Mesin Turing?

Alan Turing adalah tokoh yang menemukan konsep Mesin Turing pada tahun 1936.

Proses translasi dalam compiler?

Source Program → Lexical Analyzer → Parser → Code Generator → Object Program

Diagram transisi untuk string valid?

Ditandai dengan lingkaran ganda pada diagram transisi Finite Automata.

Proses Translasi Compiler

Proses translasi dari kode sumber ke kode mesin:

Source Program: Kode yang ditulis programmer
Lexical Analyzer: Memecah kode menjadi token
Parser: Menganalisis struktur sintaks
Code Generator: Menghasilkan kode intermediate
Object Program: Kode mesin yang siap dieksekusi

// Contoh: Python ke Bytecode
import dis
def tambah(a,b): return a+b
dis.dis(tambah)
                                

Simulasi Terkait

Simulasi interaktif terkait mesin Turing dan Enigma:

Simulasi Enigma Simulasi Bombe Turing

Klik link di atas untuk membuka simulasi di tab baru.

Bahasa Formal: Definisi & Contoh

Definisi Formal

Bahasa formal didefinisikan sebagai himpunan string yang dibentuk dari alfabet tertentu menurut aturan (grammar) yang ketat.

Context-Free Grammar (CFG)

CFG = (T, N, P, S) dimana:

T: Terminal (simbol akhir)
N: Non-terminal (simbol variabel)
P: Produksi (aturan)
S: Start symbol

// Contoh CFG untuk ekspresi aritmatika
E → E + T | T
T → T * F | F
F → ( E ) | id
                        

Contoh Bahasa Formal

Bahasa	Alfabet	Aturan	Contoh String Valid
Biner Genap	{0, 1}	Berakhir dengan 0	1010, 1100, 0
Palindrome	{a, b}	Dibaca sama depan-belakang	aba, bb, abba
Ekspresi Matematika	{0-9, +, -, *, /, (, )}	Kurung seimbang	(3+4)*5, 10/(2+3)

Hierarki Bahasa Pemrograman

Level	Nama	Contoh	Dekat Manusia	Dekat Mesin
High-Level	Bahasa Tingkat Tinggi	Python, Java, JavaScript	✅ Super dekat	❌ Jauh
Middle-Level	Assembly	NASM, ARM asm	⚖️ Sedikit	⚖️ Sedikit
Low-Level	Machine Code	Binary (0-1)	❌ Tidak sama sekali	✅ Langsung CPU

Catatan: Komputer hanya mengerti 0 dan 1, tetapi compiler/interpreter menerjemahkan kode high-level ke low-level secara otomatis.

Finite Automata (Mesin Status Terhingga)

Definisi Formal (5-tuple)

FA = (Q, Σ, δ, q₀, F) dimana:

Q: Himpunan status terhingga
Σ: Alfabet input
δ: Fungsi transisi Q × Σ → Q
q₀: Status awal ∈ Q
F: Himpunan status akhir ⊆ Q

Contoh: Vending Machine

Harga: 30, Koin: {10, 20}
Q = {0, 10, 20, 30, >30}
Σ = {10, 20}
q₀ = 0
F = {30}

Transisi:
0 +10→ 10
10 +10→ 20
10 +20→ 30 (terima)
20 +10→ 30 (terima)
30 +koin→ >30 (tolak)

DFA vs NFA

Ciri	DFA (Deterministic)	NFA (Non-Deterministic)
δ(q,input)	1 hasil saja	Bisa 0, 1, atau banyak
ε-move	Tidak ada	Boleh tanpa baca input
Implementasi	Langsung di kode	Ditransform ke DFA dulu

Simulator Finite Automata

Simulasikan DFA untuk string yang mengandung substring "abb":

DFA untuk pola "abb"
q0 --a--> q0
q0 --b--> q1
q1 --b--> q2
q2 --b--> q3 (F)
q2 --a--> q0
q3 --a,b--> q3

Hierarki Chomsky (4 Tipe)

Tipe	Nama	Aturan Produksi	Mesin yang Cukup	Contoh Bahasa
3	Regular	A → aB atau A → a	Finite Automata	a*b+ (regex)
2	Context-Free	A → α (α string apa saja)	Push-Down Automata (stack)	Palindrome aⁿbⁿ
1	Context-Sensitive	α→β dengan \|α\| ≤ \|β\|	Linear-Bounded Automata	aⁿbⁿcⁿ
0	Unrestricted	α→β (bebas)	Mesin Turing	Semua yang bisa dihitung

Analogi Sederhana

Tipe-3

Sepeda motor
(jalan lurus, cepat)

Tipe-2

Truk dengan dongkrak
(bawa stack)

Tipe-1

Truk + GPS terbatas
(lebih fleksibel)

Tipe-0

Kapal luar angkasa
(mana pun bisa)

Kuis Cepat: Tipe Chomsky

Bahasa Python termasuk tipe Chomsky berapa?

Tipe-3 (Regular)

Tipe-2 (Context-Free)

Tipe-1 (Context-Sensitive)

Tipe-0 (Unrestricted)

Jawaban: Python sintaks mayoritas Tipe-2 (CFG), tapi semantic analysis memerlukan Tipe-1 (hybrid).

Latihan Soal - Bahasa Formal & Finite Automata

Berikut adalah 10 soal pilihan ganda berdasarkan materi. Pilih jawaban yang benar!

1. Suatu bahasa yang harus mengikuti aturan bahasa pemrograman dan bahasa matematis seperti aljabar dan logika proposisi disebut bahasa...

A. Formal

B. Natural

C. Verbal

D. Frasa

2. Jenis tatabahasa dalam bahasa formal terdiri dari...

A. 1

B. 2

C. 3

D. 4

E. 5

3. Level terendah dari hirarki mesin dan bahasa disebut...

A. Formal

B. Natural

C. Verbal

D. Frasa

E. Automata terhingga

4. Dalam diagram transisi untuk menyatakan string yang valid telah dikenali ditandai dengan...

A. Busur

B. Lingkaran ganda

C. Simbol

D. Kategori

E. Inisiasi

5. Tokoh penemu mesin Turing adalah...

A. Alan

B. Automata

C. Alan Turing

D. James Turing

E. David Turing

6. Proses mengenali runtunan multisimbol di dalam program ditangani oleh compiler disebut...

A. source program

B. lexical analyzer

C. parser

D. code generation

E. object program

7. Translator menganalisa pola dari token, misal if-then, if then-else, atau perulangan loop disebut...

A. source program

B. lexical analyzer

C. parser

D. code generation

E. object program

8. Suatu proses yang menghasilkan versi translasi dari bagian program disebut...

A. source program

B. lexical analyzer

C. parser

D. code generation

E. object program

9. Semua bagian translasi dibentuk, maka dibentuk versi translasi program yang disebut...

A. source program

B. lexical analyzer

C. parser

D. code generation

E. object program

10. Tata bahasa jenis 3 jika semua produksi didalam tata bahasa berbentuk di bawah ini Kecuali...

A. A -> a

B. A -> aB

C. A -> Ba

D. A -> ab

E. a,b, dan c benar

Kunci Jawaban: ADEBCBCDED

Jawaban yang benar: 1-A, 2-D, 3-E, 4-B, 5-C, 6-B, 7-C, 8-D, 9-E, 10-D