AGUS DIAN RISTANTO

Tak ada yang banyak ingin kutulis di bulan juni-juli ini, yang jelas aku ingin sekali 2 bulan ini segera berlalu, banyak sekali yang berubah dengan isi kepalaku dalam menyikapi berbagai hal, tersudut dan terpuruk. sebelumnya aku ingin melakukan sesuatu yang bijak dan bergenre kedewasaan, namun ternyata aku tak mampu melakukanya. sekali lagi aku ingin 2 bulan buruk ini segera berakhir dan tergantikan dengan kehidupan baruku yang lebih rasional dan

Simbol

Karakter, mesin terbang, tandai.
Sebuah entitas abstrak yang tidak memiliki arti dengan sendirinya, sering disebut ditafsirkan.
Surat dari berbagai huruf, angka dan karakter khusus
yang paling sering digunakan simbol.

Alfabet

Satu set hingga simbol.
Sebuah alfabet sering dilambangkan dengan sigma, belum bisa diberi nama apapun.
B = (0, 1) Says B merupakan abjad dari dua simbol, 0 dan 1.
C = (a, b, c) Says C adalah sebuah alfabet dari tiga simbol, a, b, dan c.
Kadang-kadang ruang dan koma dalam alfabet, sementara yang lain kali mereka
adalah meta simbol yang digunakan untuk deskripsi.

String juga disebut Word

Urutan hingga simbol dari abjad.
01.110 dan 111 adalah string dari abjad B di atas.
aaabccc dan b adalah string dari abjad C di atas.
Sebuah string adalah null string tanpa simbol, biasanya dinotasikan dengan epsilon.
Null string memiliki panjang nol.
Null string biasanya dinotasikan epsilon.
bar vertikal di sekitar string mengindikasikan panjang string dinyatakan sebagai
nomor alam. Sebagai contoh | 00100 | = 5, | AAB | = 3, | epsilon | = 0

Bahasa formal, juga disebut Bahasa

Satu set string dari abjad.
set mungkin kosong, hingga atau tak terbatas.
Ada banyak cara untuk mendefinisikan sebuah bahasa. Lihat definisi di bawah ini.
Ada banyak klasifikasi untuk bahasa. Lihat definisi di bawah ini.

Karena bahasa adalah satu set string, bahasa kata-kata dan mengatur
sering digunakan bergantian dalam berbicara tentang bahasa formal.

L (M) adalah notasi untuk bahasa mesin yang didefinisikan oleh M.
M mesin menerima satu set string tertentu, dengan demikian bahasa.

L (G) adalah notasi untuk bahasa yang didefinisikan oleh tata bahasa sebuah G.
Tata bahasa G mengakui satu set string tertentu, dengan demikian bahasa.

M (L) adalah notasi untuk sebuah mesin yang menerima sebuah bahasa.
Bahasa L adalah satu set string tertentu.

G (L) adalah notasi untuk tata bahasa yang mengakui sebuah bahasa.
Bahasa L adalah satu set string tertentu.

Penyatuan dua bahasa adalah bahasa. L = L1 L2 serikat
Persimpangan dua bahasa adalah bahasa. L = L1 L2 berpotongan
Komplemen dari suatu bahasa adalah bahasa. L = sigma * - L1
Perbedaan dari dua bahasa adalah bahasa. L = L1 - L2

Regular Bahasa, Regular Expression, biasa

Satu set string dari abjad.
set ini dapat kosong, hingga atau tak terbatas.

Bangunan blok bahasa biasa adalah simbol, gabungan dari
simbol untuk membuat string (kata), set string persatuan dan Kleene
penutupan (dilambangkan sebagai *, juga disebut bintang Kleene, harus
diketik sebagai superscript, tetapi ini adalah teks biasa.)

Informal, kami menggunakan sintaks untuk kalimat biasa.
menggunakan sigma sebagai set, (0 1) (suatu abjad dari dua simbol)
01.110 adalah string dimulai dengan simbol 0 dan kemudian concatenating
1, lalu 1, lalu 1, dan akhirnya concatenating 0. Tidak ada tanda baca digunakan
antara simbol-simbol atau string yang concatenated.
(01 10) adalah kesatuan dari dua string 01 dan 10. Set (01, 10)
(00 11) * adalah penutupan Kleene serikat 0 concatenated dengan 0 dan
1 concatenated dengan 1.

Penutupan Kleene (bintang) didefinisikan sebagai gabungan dari
tidak ada, satu, dua, atau nomor string dpt dihitung itu berlaku.
Contoh bintang Kleene:
1 * adalah himpunan string (epsilon, 1, 11, 111, 1111, 11111, dll)
mengatur ini tak terbatas.

(1100) * adalah himpunan string (epsilon, 1100, 11001100, 110011001100, dll)

(00 11) * adalah himpunan string (epsilon, 00, 11, 0000, 0011, 1100, 1111,
000000, 000011, 001100, dll)
perhatikan bagaimana serikat (+ simbol) memungkinkan semua pilihan yang mungkin
pemesanan bila digunakan dengan bintang Kleene.

(0 +1) * adalah semua string yang mungkin dari nol dan yang, sering ditulis sebagai
sigma * mana sigma = (0, 1)

(0 +1) * (00 11) adalah semua string dari nol dan orang-orang yang berakhir dengan baik
00 atau 11. Perhatikan bahwa Rangkaian tidak memiliki operator
simbol.

(W) + adalah singkatan untuk (w) (w) w * adalah setiap string atau ekspresi dan
ditambah yg ditulis, +, berarti satu atau lebih salinan w di set didefinisikan
dengan ungkapan ini.

Secara formal, bahasa biasa didefinisikan pada bagian bawah halaman 28.

Beberapa versi dari grep menerapkan pencarian ekspresi reguler oleh
mensimulasikan Automata Hingga.
Perhatikan bahwa grep menggunakan sintaks yang berbeda dan menggunakan subset dari ASCII
karakter untuk simbol.


Tata bahasa, tata bahasa formal

tata bahasa didefinisikan sebagai G = (V, T, P, S) dimana:
V adalah seperangkat simbol yang disebut variabel, biasanya S, A, B, ...
T adalah seperangkat simbol yang disebut terminal, biasanya 0, 1, a, b, ...
P adalah himpunan produksi
S adalah awal atau variabel tujuan dari V

P produksi adalah dalam bentuk:
w" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'">A -> w

Di mana A adalah variabel
w adalah setiap Rangkaian variabel dan terminal

Sebuah contoh adalah tata bahasa G = (V, T, P, S) di mana V = (S, A) T = (0, 1)
dan produksi, P, adalah:

0A | 0" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'">S -> 0A | 0
10A" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'">A -> 10A

tata bahasa ini sesuai dengan ekspresi reguler 0 (10) * yang pada gilirannya
sesuai dengan automata hingga deterministik
ditunjukkan pada Gambar DFA1.

Regular Grammar

tata bahasa didefinisikan sebagai G = (V, T, P, S) dimana:
V adalah seperangkat simbol yang disebut variabel, v1, v2, ... , Vn
T adalah seperangkat simbol yang disebut terminal, t1, t2,,,,, tm
P adalah himpunan produksi
S adalah awal atau variabel tujuan dari V

P produksi adalah dalam bentuk:
w" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'">A -> w
wB" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'">A -> WB

Dimana A dan B adalah variabel
w adalah setiap terminal kombinasi, mungkin string kosong

Setiap tata bahasa reguler dapat dikonversi ke setara DFA, NFA,
reguler bahasa atau ekspresi reguler.

Konteks Gratis Bahasa, CFL

Satu set string dari abjad.
set mungkin kosong, hingga atau tak terbatas.

A grammar G = (V, T, P, S) dengan produksi terbatas pada:

segera hadir

yacc dan banteng dapat memproses tata bahasa bebas konteks dan memiliki kemampuan
untuk menangani beberapa tata bahasa sensitif konteks juga.

Konteks Gratis Bahasa terkait dengan Push Down Automata.


Greibach Bentuk Normal, GNF

A grammar G = (V, T, P, S) dengan produksi, P, terbatas untuk membentuk:
terminal variable(s)" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'">variabel - variabel terminal> (s)

a alpha where A is a variable in V, a is a terminal in T and" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'">A -> alfa mana A adalah variabel di dalam V, sebuah terminal di T dan
alpha tidak ada, satu atau lebih variabel dalam V.

Chomsky Normal Form, CNF

A grammar G = (V, T, P, S) dengan produksi terbatas pada bentuk:
variable variable" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'">variabel - variabel variabel>
terminal" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'">variabel -> terminal

BCA, B and C are variables in V and exactly two variables are on the right" onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'">A -> BCA, B dan C adalah variabel di dalam V dan tepat dua variabel di sebelah kanan
a A is a variable in V and a is exactly one terminal symbol in T." onmouseover="this.style.backgroundColor='#ebeff9'" onmouseout="this.style.backgroundColor='#fff'">A -> A adalah variabel di dalam V dan adalah tepat satu terminal simbol di T.

CYK Algoritma, Cocke-muda-Kasami

Diberikan CFG G = (V, T, P, S) dan string x di * T, adalah x di L (G)?
Algoritma CYK menggunakan pemrograman dinamis (dari 441 program algoritma)
untuk menyediakan | x algoritma | potong dadu waktu untuk menjawab pertanyaan ini.

lihat p139-140 dalam buku teks

Rekursif Bahasa, rekursif set

Bahasa, set, diterima oleh mesin Turing dan tata bahasa yang terbatas.


Rekursif Enumerable set, r.e. bahasa

Set, bahasa, yang dapat dihasilkan (disebutkan) di mana semua string
di set, bahasa, dari panjang yang diberikan dapat dihasilkan.

Biasanya pencacahan adalah string dengan panjang 1, maka string panjang 2,
dan keempat. Tentu saja mungkin tidak ada string untuk beberapa panjang.

Dalam beberapa kasus, menghasilkan Sigma n ^ dan melewati setiap string ke mesin atau
tata bahasa. Tali diterima adalah string panjang n.

Tidak ada persyaratan bahwa string akan dihasilkan dalam leksikal atau
lainnya untuk.

Jika kedua satu set dan yang melengkapi adalah secara rekursif Enumerable, maka
set rekursif.


Hirarki Chomsky tata bahasa / Bahasa

Jenis 0, tata bahasa yang menghasilkan r.e. set
dan mencirikan r.e. bahasa
Tata bahasa yang tidak terikat bentuk G = (V, T, P, S)
pembatasan ini dihapus dari bentuk produksi.

Tipe 1, tata bahasa yang mencirikan bahasa peka konteks.
Tipe 2, tata bahasa yang mencirikan bahasa bebas konteks.
Tipe 3, tata bahasa yang mencirikan bahasa reguler.

Catatan: Jenis 0 tata bahasa dapat memiliki loop tak terbatas dalam parser untuk
tata bahasa ketika sebuah string tidak dalam tata bahasa adalah masukan untuk parser.

P dan NP kelas bahasa

Sebuah kelas bahasa adalah sekumpulan bahasa yang karakteristik berbagi.
Karena bahasa adalah satu set string dari alfabet terbatas, sebuah kelas
bahasa adalah satu set set.

bahasa kelas P adalah himpunan bahasa yang terdapat sebuah
Mesin Turing deterministik yang menerima bahasa masing-masing sejumlah
transisi dibatasi oleh polinomial tetap panjang string masukan.

Mulailah dengan mesin "standar" Turing dengan kontrol negara hingga yang
adalah deterministik, TM memiliki tabel transisi dengan satu entri untuk setiap
(Negara, input-simbol) pasangan.

Pertimbangkan bahasa khusus yang memiliki berbagai rangkaian panjang. Biarkan
panjang dari setiap string dalam bahasa itu akan dilambangkan n. Jika ada ada yang tetap
polinomial dalam n, misalnya c ^ n * r untuk beberapa konstanta c tetap dan beberapa tetap
r konstan, sehingga mesin Turing menerima atau menolak semua string di
bahasa tertentu di c * r ^ n bergerak, transisi, maka yang spesifik
bahasa di P. set


Bahasa NP kelas berbeda dari kelas bahasa P dalam dua cara:
1) bahasa NP memiliki Mesin Turing dengan finite state nondeterministic
kontrol. Nondeterministic tidak berarti acak.
2) NP bahasa memiliki mesin Turing yang tidak memiliki untuk menolak
string dalam jumlah yang ditentukan dari pergerakan.

Catatan: Tanpa batasan waktu, dibatasi jumlah pergerakan, apapun
nondeterministic mesin Turing memiliki setara deterministik
Mesin Turing. Hal ini diyakini bahwa kelas bahasa tidak P
setara dengan kelas bahasa NP tetapi kepercayaan ini tidak belum terbukti.

Parsing
Parsing adalah konsturksi atau pembentukan Pohon Sintaks untuk suatu kalimat (ekspresi).

Bila terdapat lebih dari satu pohon sintaks untuk sebuah grammar maka dikatakan grammar tersebut Ambiguous.

Dua cara melakukan validitas sintaks dengan parsing :
TOP DOWN Parsing : melakukan derivasi string dari NT
BOTTOM UP Parsing : melakukan reduksi simbol ke NT.


Parsing Top Down
Jika  adalah input string, maka derivasi dari Top Down Parse dapat ditunjukkan sebagai berikut :
S …  …  …  
Parse Tree untuk Top Down Parsing selalu dimulai dari sebelah kiri

Parsing Top Down (cont.)
Contoh : Parsing Top Down untuk identifier x2
Derivasinya :
   x  x2
Parsing Top Down (cont.)
Contoh : ekspresi a + b * c
grammar : E ::= T + E | T
T ::= V * E | V
V ::=
Parsing Bottom Up
Parsing Bottom Up membangun pohon sintaks melalui urutan simbol yang direduksi, atau dimulai dengan sebuah string hingga mencapai simbol start Grammar

Contoh : diketahui identifier x2, dengan parsing bottom up menjadi :
Relasi Preseden dan Pemakaiannya
Teknik parsing pada metode Bottom-Up dilakukan dengan mencari berulang-ulang, handle (leftmost simple phrase) u dari bentuk sentensial saat itu dan mereduksinya menjadi suatu nonterminal U dnegan memakai reduksi U  u

Jadi tujuan utamanya adalah mencari Handle dari sebuah bentuk sentensial yaitu simple phrase terkiri (leftmost) dari bentuk sentensial tersebut.

Masalah tersebut diselesaikan dengan Grammar Preseden


Relasi Preseden dan Pemakaiannya (cont.)
Misal, R dan S berada dalam suatu grammar G. Beberapa bentuk sentensial dapat dibentuk dari simbol R dan G tersebut (…RG…..). Ada tiga kemungkinan yang timbul dalam handle yang dibuat dari R dan S.
R adalah bagian dari suatu handle tapi S tidak (R  S)
dikatakan R > S (R memiliki Preseden atas S).
R harus merupakan ekor dari beberapa produksi U  …R.
Karena handle berada di kiri S,maka S harus merupakan terminal

Relasi Preseden dan Pemakaiannya (cont.)
R dan S keduanya adalah bagian dalam suatu handle (R  S)
dikatakan R dan S memiliki Preseden yang sama, dan harus direduksi secara bersamaan waktu
Harus ada suatu produksi U  …RS...
Relasi Preseden dan Pemakaiannya (cont.)
Contoh : Diketahui, Grammar dengan simbol Start Z dan produksi :
Z  bMb
M  (L | a
L  Ma)
Berikut ini akan ditunjukkan bentuk sentensial, phon sintaks,handel dari relasi yang dapat diturunkan dari produksi.

Bentuk sentensial : bab
Pohon Sintaks :
Relasi Preseden dan Pemakaiannya (cont.)
Bentuk sentensial : b(Lb
Pohon Sintaks :

sebuah petualangan yang asyik dan menegangkan, penuh nilai kepahlawanan, guyonan cerdas.
rasanya seolah kita diajak berpetualang ke negeri-negeri belahan dunia.
Berbagai peristiwa dirangkai dengan amat genius meskipun baru paham setelah membaca buku ini sampai 1/3 isi buku
kalo saya boleh menyebutnya SKI "Senam Kesegaran Imajinasi"

tanggal 11 maret lalu seharusnya saya sudah harus berada di ruang ini untuk melaksanakan amanah di tempat yang baru, namu baru hari ini saya 100% aktif di tempat ini, hari ini memang sibuk, sibuk terdiam membaca lingkungan, situasi, kawan-kawan baru di ruang "perencanaan"

kiranya perlu waktu 1 minggu bagi saya untuk benar-benar bisa menyesuaikan diri dengan situasi di ruangan ini, tapi saya yakin , saya akan belajar banyak di gedung megah ini, saya akan banyak mendapat ilmu dan pengalaman , Aku mohon petunjuk dan ridlo-MU ya Allah