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.
0 pro