Grammar Dan Bahasa

Grammar Dan Bahasa

Dalam teori bahasa, tata bahasa (Grammar) adalah seperangkat aturan yang menjelaskan bagaimana membangun sebuah bahasa. Tata bahasa terdiri dari satu set simbol, yang disebut terminal dan non-terminal, dan satu set aturan produksi yang menentukan cara menghasilkan string terminal dari non-terminal. Aturan produksi menentukan cara menggabungkan simbol untuk membentuk string yang valid dalam bahasa. Tata bahasa dapat diformalkan menggunakan bahasa formal, seperti tata bahasa bebas konteks, tata bahasa peka konteks, atau tata bahasa reguler.

Bahasa adalah sekumpulan string yang dapat dikenali oleh otomata. Otomat adalah model matematika yang mengenali bahasa. Otomat dapat dianggap sebagai mesin yang membaca simbol masukan dan transisi antar keadaan berdasarkan masukan. Otomat menerima atau menolak string berdasarkan status yang dicapai setelah memproses seluruh input. Konsep bahasa terkait erat dengan konsep tata bahasa, karena bahasa dapat dihasilkan oleh tata bahasa dan dikenali oleh otomat.

Singkatnya, tata bahasa dan bahasa adalah konsep penting dalam teori bahasa dan automata. Tata bahasa digunakan untuk menjelaskan cara membuat bahasa, sedangkan bahasa adalah rangkaian string yang dikenali oleh automata. Hubungan antara tata bahasa dan bahasa merupakan pusat studi bahasa formal dan automata.

Grammar (G) didefiniskan sebagai pasangan 4 tuple:

VT, VN, S, dan Q,

dan dituliskan sebagai G(Vt, Vn, S, Q), dimana:

Vt = himpunan simbol-simbol terminal (atau himpunan token-token, atau alfabet)

Vn = himpunan simbol-simbol non terminal

S = simbol awal (atau simbol start)

Q = himpunan produksi

Simbol Vn adalah simbol yang masih dapat diturunkan, biasanya identik dengan huruf besar ('A', 'B', 'C')

Contoh

Bahasa G = ({S, A, B}, {a, b}, P, S), di mana P adalah himpunan aturan produksi:

S → AB

A → aA | e

B → BB | e

Untuk menurunkan kalimat dalam bahasa yang dihasilkan oleh G, kita bisa mulai dengan simbol awal S dan menerapkan aturan produksi untuk menghasilkan urutan simbol yang akhirnya menghasilkan kalimat yang valid.

Contoh kalimat derivasi:

Simbol awal: S

Terapkan aturan S → AB

string baru: AB

Terapkan aturan A → aA

string baru: aAB

Terapkan aturan A → ε

string baru: AB

Terapkan aturan B → ε

String terakhir: AB

Derivasi ini menghasilkan kalimat "AB", yang dalam bahasa dihasilkan oleh G.

Untuk menentukan bahasa yang dihasilkan oleh G, kita dapat menganalisis kumpulan string yang dapat dihasilkan oleh tata bahasa.

Simbol non-terminal S menghasilkan string "AB", yang terdiri dari urutan "a" diikuti oleh urutan "b", dengan sejumlah pengulangan yang diperbolehkan. Simbol non-terminal A menghasilkan urutan "a", sedangkan simbol non-terminal B menghasilkan urutan "b". Karena A dan B dapat menghasilkan string kosong (ε), bahasa yang dihasilkan oleh G menyertakan string kosong juga.

Dengan demikian, bahasa yang dihasilkan oleh G adalah himpunan semua string yang memiliki urutan "a" diikuti oleh urutan "b", dengan sejumlah pengulangan diperbolehkan, termasuk string kosong. Bahasa ini biasanya dilambangkan sebagai {a^n b^n | n ≥ 0}.

Singkatnya, derivasi kalimat dan penentuan bahasa adalah konsep penting dalam teori bahasa formal. Menggunakan tata bahasa bebas konteks sebagai contoh, kami menunjukkan cara menurunkan kalimat dan menentukan bahasa yang dihasilkan oleh tata bahasa.