Apakah ada cara lain untuk menggambarkan bahasa formal selain tata bahasa?

22

Saya mencari teori matematika yang berhubungan dengan menggambarkan bahasa formal (serangkaian string) secara umum dan bukan hanya hierarki tata bahasa.

mtanti
sumber
Perhatikan bahwa ada banyak, banyak jenis grammer luar yang Chomsky klasik, misalnya beberapa , ditambah dan panjang tergantung bebas konteks tata bahasa, masing-masing (mudah googlable).
Raphael
Menemukan beberapa tabel Wikipedia
Anton

Jawaban:

14

Ada banyak kemungkinan. Yang lain telah menyebutkan automata yang menawarkan banyak pilihan. Pertimbangkan juga kerangka kerja berikut:

  1. Beberapa bahasa dapat didefinisikan secara langsung oleh (co) definisi induktif . Misalnya, titik akses terkecil dari
    adalah bahasa yang sama dengan yang dijelaskan oleh(baa), fixpoint terbesar adalah(baa)ω. Perhatikan bahwa definisi seperti itu juga dapat ditulis dalambentukaturankalkulus atauinferensi:a εLwLawLawLbawLa
    (baa)(baa)ω
    aε,waw,awbawa

  2. Kata- kata mendefinisikan struktur kata yang dapat digunakan sebagai model rumus logis . Pada dasarnya, setiap kata mendefinisikan domain dari posisinya , predikat P sebuah : D { 0 , 1 } sehingga P a ( i ) w i = a untuk semua a Σ , predikat < yaitu < dari NDw={1,,n}Pa:D{0,1}Pa(i)wi=aaΣ<<Nterbatas dan predikat suc : D w × D w{ 0 , 1 } itu benar jika dan hanya jika parameter kedua adalah penerus langsung dari kepalan tangan. Jadi misalnya, jika w = a a b a b a a b kemudianDwsuc:Dw×Dw{0,1}
    w=aababaab
    sebenarnya,rumus orde pertamainimendefinisikan --- melalui himpunan semua struktur kata yang memenuhinya --- bahasa yang sama dengan(baa). Yang sesuaiω-language(ba|a)ωdigambarkan olehrumus LTLaSwi.j. (Pb(i)  suc(i,j))¬Pb(j);a
    (baa)ω(baa)ω
    Beberapa ekuivalensi antara kelas bahasa klasik dan logika tertentu diketahui. Misalnya,FOberkorespondensi dengan bahasa bebas bintang-, lemahMSOuntuk bahasa reguler danMSOuntukohmbahasa -regular. Lihat disiniuntuk referensi.a(Pb(¬Pb))a
    ω

  3. Sesuatu yang ortogonal untuk kelas klasik adalah bahasa pola . Asumsikan alfabet terminal dan alfabet variabel X = { x 1 , x 2 , ... } . String p ( Σ X ) + disebut pola . Biarkan H = { σ σ : X Σ } set pergantian. Kami mendefinisikan bahasa p pola sebagaiΣX={x1,x2,}p(ΣX)+H={σσ:XΣ}p
    Perhatikan bahwaσdiperluas untuk bekerja pada pola; simbol terminal dibiarkan tidak berubah. Sebagai contoh, pertimbangkanL(x1abbax1)={wabbaww{a,b}}.aL(p)={σ(p)σH}.a
    σ
    L(x1abbax1)={wabbaww{a,b}}
    Perhatikan bahwa kami mengizinkan substitusi untuk menghapus variabel; beberapa properti dari kelas bahasa pola sangat berbeda untuk menghapus substitusi vs non-menghapus. Bahasa pola sangat menarik dalam pembelajaran gaya Emas .

Raphael
sumber
5

Anda harus melihat pada teori automata . Ada banyak materi tentang itu.

Dalam contoh, Anda dapat mendefinisikan bahasa reguler dengan otomat terbatas nondeterministik dengan tepi berlabel: string milik bahasa jika otomaton dapat mengikuti transisi yang dilabeli oleh karakternya dan berhenti dalam keadaan akhir.

Juga, tata bahasa bebas konteks dapat dikenali oleh otomat pushdown .

Cara lain untuk mendefinisikan bahasa adalah dengan menggunakan mesin Turing .

Riccardo T.
sumber
5

Dari hierarki Chomsky ada empat jenis bahasa formal (masing-masing adalah subset dari yang setelahnya):

Sebuah bahasa formal biasa dapat dijelaskan oleh:

  1. Tata Bahasa Reguler
  2. Finite Automaton (Deterministic / Nondeterministic)
  3. Ekspresi Reguler

1., 2. dan 3. adalah setara dan dari salah satunya Anda dapat membangun yang lain.

Sebuah bahasa formal bebas konteks dapat dijelaskan oleh:

  1. Tata Bahasa bebas konteks
  2. Automat pushdown

Juga 1. dan 2. adalah setara.

Sebuah bahasa formal konteks-sensitif dapat dijelaskan oleh:

  1. Automaton terikat linier (Mesin Turing dengan pita terbatas)

Sebuah bahasa formal rekursif enumerable dapat dijelaskan oleh:

  1. Mesin Total Turing
Anton
sumber
Dan semua kelas bahasa lainnya?
Raphael
Dan bahasa tanpa kelas?
Dave Clarke
Chomsky tidak mengatakan ini adalah satu - satunya jenis bahasa - mereka hanya empat jenis yang menurutnya penting, dan kami masih menganggapnya penting, tetapi ada banyak jenis lainnya.
reinierpost
5

Lebih jauh ke jawaban lain, seseorang dapat menggambarkan dan mengklasifikasikan bahasa dalam istilah "generator" dan properti penutupan. Misalnya, masuk akal untuk berbicara tentang AFL terkecil yang dihasilkan oleh beberapa bahasa. Tempat yang baik untuk mulai belajar tentang jenis deskripsi ini adalah buku ini , walaupun mungkin sulit menemukan salinannya.

Sam Jones
sumber