Resemu TBO 20 Maret 2017 Hirarki Chomsky

Resume Hirarki Chomsky

Prefikstring     : PLN, PL, P, Ꞓ

Profer Prefik   : PL, P, Ꞓ

Postfix String  : PLN, LN, N, Ꞓ

Proper Postfix : LN, N, Ꞓ

Head               : PN

Tail                  : LN

Substring                     : PLN, PL, LN P, L, N, Ꞓ

Profer Subtring           : PL, LN , P, L, N, Ꞓ

Subsequence               : PLN, PL, PN, LN, P, L, N, Ꞓ

Profer Subsequence    : PL, PN, LN, P, L, N, Ꞓ

Contoh Grammer (GI) 

-          Vt        : {I, Want, Need, You}

-          Vn       : {S, A, B, C}

-          P          : {S à ABC, A à J, B à Want | Need, C à You}

§  I Want You/I Need You

Hirarki Chomsky
Hirarki Chomsky mempunyai 4 class tingkatan, yaitu :

1.      Tipe 0 (Unrestricted)

Pada tipe 0 ini "simbol  ruas sebelah kiri harus minimal ada sebuah simbol variabel dan tidak ada batasan pada aturan produksi". Tipe 0 menggunakan mesin automata dengan Mesin Turing.

2.   Tipe 1 (Context Sensitive)

Pada tipe 1 ini "simbol pada ruas sebelah kiri harus minimal ada sebuah variabel dan panjang String ruas kiri harus lebih kecil atau sama dengan ruas kanan (|a| <=|B|)". Tipe 1 menggunakan mesin automata dengan Linier Bounded Automata. 

3.   Tipe 2 (Context Free / Bebas Konteks)

Pada tipe 2 ini "simbol sebelah kiri harus simbol variabel". Tipe 2 menggunakan mesin automata dengan Push Down Automata.

4.      Tipe 3 (Regular)

Pada tipe 3 ini "simbol sebelah kiri harus berupa simbol variabel dan simbol sebelah kanan maksimal hanya memiliki sebuah simbol variabel dan bila ada terletak di paling kanan". Tipe 3 menggunakan mesin automata dengan Finite State Automata DFA dan NFA.