UAS

TEORI BAHASA DAN AOUTOMATA

Grammar (Tata Bahasa)

Tata bahasa (grammar) bisa didefinisikan secara formal sebagai kumpulan dari

himpunan-himpunan variabel, simbol-simbol terminal, simbol awal, yang dibatasi oleh

aturan-aturan produksi

Suatu tata bahasa (grammar) didefinisikan dengan 4 Tupel yaitu : V, T, P, dan S

Di mana,

V = Himpunan simbol variabel / non terminal

T = Himpunan simbol terminal

P = Kumpulan aturan produksi

S = Simbol awal

                                                          Diagram Grammar

                             

           

                      

Penulisan Formal

Secara formal tata bahasa yang diperoleh dari otomata adalah sebagai berikut.

V = {S, A, B,D}

T = {a, b}

P = { S → A|aA, A→bD, D→aA|D, B→aD}

S = S

Uji input

FSA (Finite State Automata)

Finite state automata adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata.

Finite State Automata dinyatakan oleh pasangan 5 tuple, yaitu:

M=(Q , Σ , δ , S , F )
Q = himpunan state
Σ = himpunan simbol input
δ = fungsi transisi δ : Q × Σ
S = state awal / initial state , S ∈ Q
F = state akhir, F ⊆ Q

DIAGRAM

Penulisan Formal

M = (Q, ∑, δ, S, F),

•       Q = {q0,q1, q2, q3}

•       ∑ = {A,B}

•       S = q0

•       F = {Q3}

•       δ  =

Q	A	B
Q0	Q1	-
Q1	-	Q3
Q2	Q3	-
Q3	Q1

Uji input

SEKIAN DAN TERIMA KASIH