Tata Bahasa Reguler vs Bebas Konteks

98

Saya belajar untuk saya ujian bahasa komputasi , dan ada satu gagasan bahwa saya mengalami masalah.

Saya mengerti bahwa tata bahasa biasa lebih sederhana dan tidak dapat mengandung ambiguitas, tetapi tidak dapat melakukan banyak tugas yang diperlukan untuk bahasa pemrograman. Saya juga mengerti itu tata bahasa tanpa konteks memungkinkan ambiguitas, tetapi memungkinkan beberapa hal yang diperlukan untuk bahasa pemrograman (seperti palindrom).

Yang bermasalah dengan saya adalah memahami bagaimana saya dapat memperoleh semua hal di atas dengan mengetahui bahwa tata bahasa nonterminals reguler dapat memetakan ke terminal atau nonterminal diikuti oleh terminal atau bahwa peta nonterminal bebas konteks ke kombinasi terminal dan nonterminal apa pun .

Bisakah seseorang membantu saya menyatukan semua ini?

context-free-grammar regular-language automata Jason Baker
sumber

Jawaban:

70

Tata bahasa reguler adalah linier kanan atau kiri, sedangkan tata bahasa bebas konteks pada dasarnya adalah kombinasi terminal dan non-terminal. Karenanya Anda dapat melihat bahwa tata bahasa reguler adalah bagian dari tata bahasa bebas konteks.

Jadi untuk palindrom misalnya, berbentuk, 

S->ABA
A->something
B->something

Anda dapat melihat dengan jelas bahwa palindrom tidak dapat diekspresikan dalam tata bahasa reguler karena palindrom harus berupa linier kanan atau kiri dan karenanya tidak dapat memiliki non-terminal di kedua sisinya.

Karena tata bahasa reguler tidak ambigu, hanya ada satu aturan produksi untuk non-terminal tertentu, sedangkan bisa ada lebih dari satu dalam kasus tata bahasa bebas konteks.

Sujoy
sumber
13
Pertama: Tata bahasa reguler bisa jadi ambigu (contoh dari Kai Kuchenbecker: S -> aA | aB, B -> a, A -> a). Satu-satunya hal adalah hanya ada satu cara node dalam pohon sintaks dapat diposisikan (misalnya ambiguitas asosiatif tidak ada saat tata bahasa biasa digunakan). Kedua: Mungkin ada lebih dari satu sisi kanan ke non-terminal (A -> a, A -> aA; dan wikipedia bahkan menyertakan epsilon sebagai alternatif ketiga: en.wikipedia.org/wiki/Regular_grammar )
user764754
1
ambiguitas muncul ketika sebuah kalimat dapat diturunkan dari tata bahasa Anda di lebih dari satu jalur derivasi. hanya memiliki lebih dari satu aturan produksi untuk non-terminal tidak membuat tata bahasanya ambigu
Sujoy
11
Contoh ini sebenarnya salah. Jika kita membayangkan aturan lengkapnya A-> a | cdan B->bkemudian tata bahasa ini mengizinkan non-palindrom. Sebagai contoh, saya bisa menghasilkan: S->ABA->aBA->abA->abc. Masalahnya adalah kita tidak ingin menghasilkan dua variabel pada aturan pertama, melainkan dua terminal. Kemungkinan untuk tata bahasa yang memungkinkan palindrom adalah:S -> aSa | bSb | a | b
gdiazc
Ada palindrom yang dapat diekspresikan dalam tata bahasa biasa: palindrom yang terdiri dari satu karakter. Misalnya, S -> aSa | edan a(aa)*akeduanya mendeskripsikan bahasa biasa. Ini menunjukkan bahwa CFG dapat mendeskripsikan bahasa biasa, meskipun itu melanggar linearitas kiri atau kanan. Memang, ini adalah palindrom yang tidak terlalu jelas ..
Martijn
Kalau dipikir-pikir, jawaban ini sebenarnya salah. Dikatakan bahwa tata bahasa "bebas konteks" pada dasarnya adalah kombinasi terminal dan non-terminal. "Namun, tu ^ nvw ^ mxy ^ kz adalah kombinasi terminal dan nonterminal, tetapi tidak bebas konteks.
Charlie Martin
58

Saya pikir yang ingin Anda pikirkan adalah berbagai lemmata pemompaan. Bahasa biasa dapat dikenali oleh robot yang terbatas. Bahasa bebas konteks membutuhkan tumpukan, dan bahasa sensitif konteks membutuhkan dua tumpukan (yang setara dengan mengatakan itu membutuhkan mesin Turing penuh.)

Jadi, jika kita berpikir tentang pumping lemma untuk bahasa biasa , yang dikatakan, pada dasarnya, adalah bahwa setiap bahasa reguler dapat dipecah menjadi tiga bagian, x , y , dan z , di mana semua contoh bahasa berada dalam xy * z (di mana * adalah pengulangan Kleene, yaitu 0 atau lebih salinan y .) Pada dasarnya Anda memiliki satu "nonterminal" yang dapat diperluas.

Sekarang, bagaimana dengan bahasa tanpa konteks? Ada analogi pemompaan untuk bahasa tanpa konteks yang memecah string dalam bahasa menjadi lima bagian, uvxyz , dan di mana semua contoh bahasa berada di uv i xy i z , untuk i ≥ 0. Sekarang, Anda memiliki dua "nonterminals "yang dapat direplikasi, atau dipompa, selama Anda memiliki nomor yang sama .

Charlie Martin
sumber
10
Bahasa sensitif konteks tidak memerlukan mesin Turing lengkap. Sebuah robot berbatas linier sudah cukup. Ini adalah mesin Turing yang pita perekatnya terbatas, ukurannya dibatasi oleh beberapa fungsi linier pada string masukan.
Dave Clarke
16

Perbedaan antara tata bahasa bebas konteks dan reguler: (N, Σ, P, S): terminal, nonterminals, produksi, status awal Simbol terminal

● simbol dasar bahasa yang ditentukan oleh tata bahasa formal

● abc

Simbol nonterminal (atau variabel sintaksis)

● diganti dengan kelompok simbol terminal sesuai dengan aturan produksi

● ABC

tata bahasa reguler: tata bahasa reguler kanan atau kiri tata bahasa reguler kanan, semua aturan mematuhi bentuk

  1. B → a dimana B adalah terminal nonterminal di N dan a terminal di Σ
  2. B → aC di mana B dan C di N dan a di Σ
  3. B → ε dimana B ada di N dan ε menunjukkan string kosong, yaitu string dengan panjang 0

meninggalkan tata bahasa biasa, semua aturan mengikuti bentuknya

  1. A → a dimana A adalah terminal nonterminal di N dan a adalah terminal di Σ
  2. A → Ba dimana A dan B berada di N dan a di Σ
  3. A → ε dengan A di N dan ε adalah string kosong

tata bahasa bebas konteks (CFG)

○ tata bahasa formal dimana setiap aturan produksi berbentuk V → w

○ V adalah simbol nonterminal tunggal

○ w adalah string terminal dan / atau nonterminals (w boleh kosong)

stringRay2014
sumber
5

Tata bahasa reguler: - tata bahasa yang mengandung produksi sebagai berikut adalah RG:

V->TV or VT
V->T

dimana V = variabel dan T = terminal

RG dapat berupa Tata Bahasa Linier Kiri atau Tata Bahasa Garis Kanan, tetapi bukan Tata Bahasa linier Tengah.

Seperti kita ketahui semua RG adalah Linear Grammar tetapi hanya Left Linear atau Right Linear Grammar yang RG.

Tata bahasa biasa bisa jadi ambigu.

S->aA|aB
A->a
B->a

Tata Bahasa Ambigu: - untuk string x ada lebih dari satu LMD atau Lebih dari RMD atau Lebih dari satu pohon Parse atau Satu LMD dan Satu RMD tetapi keduanya Menghasilkan pohon Parse yang berbeda.

                S                   S

              /   \               /   \
             a     A             a     B
                    \                   \
                     a                   a

Grammar ini adalah Grammar yang ambigu karena dua pohon parse.

CFG: - Tata bahasa dikatakan CFG jika Produksinya berbentuk:

   V->@   where @ belongs to (V+T)*

DCFL: - seperti yang kita ketahui semua DCFL adalah LL (1) Grammar dan semua LL (1) adalah LR (1) jadi tidak pernah ambigu. jadi DCFG tidak pernah ambigu.

Kami juga tahu semua RL adalah DCFL sehingga RL tidak pernah ambigu. Perhatikan bahwa RG mungkin ambigu tetapi RL tidak.

CFL: CFl Mungkin atau mungkin tidak ambigu.

Catatan: RL tidak pernah ambigu secara inheren.

Dean Meehan
sumber
4

Ekspresi Reguler

  • Dasar analisis leksikal
  • Mewakili bahasa biasa

Tata Bahasa Bebas Konteks

  • Dasar penguraian
  • Mewakili konstruksi bahasa

masukkan deskripsi gambar di sini

Ahmed Salem
sumber
Tidak, itu deskripsi singkat, harap baca lagi dan periksa gambarnya.
Ahmed Salem
3

Tata bahasa bebas konteks jika semua aturan produksi memiliki bentuk: A (yaitu, sisi kiri aturan hanya dapat berupa satu variabel; sisi kanan tidak dibatasi dan dapat berupa urutan terminal dan variabel apa pun). Kita dapat mendefinisikan tata bahasa sebagai 4-tupel di mana V adalah himpunan hingga (variabel), _ adalah himpunan hingga (terminal), S adalah variabel awal, dan R adalah himpunan aturan hingga, yang masing-masing adalah pemetaan
Tata bahasa reguler V adalah linier kanan atau kiri, sedangkan tata bahasa bebas konteks pada dasarnya adalah kombinasi terminal dan non-terminal. karenanya kita dapat mengatakan bahwa tata bahasa biasa adalah bagian dari tata bahasa bebas konteks. Setelah properti ini kita dapat mengatakan bahwa kumpulan Bahasa Bebas Konteks juga berisi kumpulan Bahasa Reguler

Wafiullah NAeemzi Afghanistan
sumber
-1

Pada dasarnya tata bahasa biasa adalah bagian dari tata bahasa bebas konteks, tetapi kita tidak dapat mengatakan tata bahasa bebas Setiap Konteks adalah tata bahasa biasa. Terutama tata bahasa bebas konteks yang ambigu dan tata bahasa reguler mungkin ambigu.

Babita Mehra
sumber
-4

grammer biasa tidak pernah ambigu karena ia linier kiri atau linier kanan sehingga kita tidak dapat membuat dua pohon keputusan untuk grammer biasa sehingga selalu tidak ambigu. tetapi selain tata bahasa biasa semua mungkin atau mungkin tidak biasa

dinesh
sumber
4
@dinesh Tata bahasa biasa bisa jadi ambigu. Ingatlah bahwa tata bahasa ambigu jika terdapat dua pohon sintaks yang berbeda dan pohon sintaks diberi label. Karenanya pohon isomorfik adalah pohon yang berbeda. Yaitu tata bahasa yang sederhana seperti S -> aA | aB, B -> a, A -> a ambigu karena terdapat dua pohon sintaks untuk kata 'aa' yang isomorfik tetapi berbeda.
Kai Kuchenbecker