Perbedaan antara ekspresi reguler dan tata bahasa di automata

Saya baru mengenal automata, dan saya telah diberikan pengantar singkat untuk ekspresi reguler hanya kemarin. Saya telah membaca berbagai aturan untuk mendefinisikan ekspresi reguler. Tetapi saya tidak dapat membedakan antara ekspresi reguler dan tata bahasa (saya belum diajarkan tata bahasa untuk ekspresi reguler).

Saya mengerti bahwa tata bahasa membantu kita menghasilkan string yang valid dalam suatu bahasa, tetapi kemudian inilah aturan untuk mendefinisikan keadaan ekspresi reguler. Jadi di mana letak perbedaannya? Saya bertanya kepada profesor saya dan dia mengatakan bahwa regex adalah string paling dasar dalam suatu bahasa dan tata bahasa adalah seperangkat aturan untuk bahasa apa pun, yang tingkatannya lebih tinggi daripada regex. Bisakah seseorang memberikan informasi lebih mendalam?

Ekspresi reguler, tata bahasa reguler, dan automata terbatas hanyalah tiga formalisme berbeda untuk hal yang sama. Ada algoritma untuk mengkonversi dari salah satu dari yang lain ke yang lain.

Alasan dasar bahwa kita memiliki ketiganya adalah bahwa mereka diciptakan secara independen, dengan set pertama kesetaraan (ada beberapa formalisme juga) dibuktikan oleh Kleene (hasil ini, atau bagian daripadanya disebut Kleene's Theorem).

Jadi dalam konteks itu, tergantung pada putaran mana Anda ingin menjalankan model, mereka semua mengenali atau menghasilkan string dari bahasa biasa, dan secara matematis, dalam hal itu, tidak ada perbedaan.

Tentu saja kadang-kadang satu model lebih mudah digunakan daripada yang lain untuk tugas tertentu, karena rincian formalisme. Selain itu cara mereka bekerja di kepala manusia sering sedikit berbeda, automata terbatas "merasa" seperti komputer, ekspresi reguler "merasa" seperti Anda membangun string dari substring yang lebih kecil dan tata bahasa reguler "merasa" seperti tata bahasa yang lebih tradisional derivasi atau klasifikasi suatu kalimat dalam suatu bahasa (tidak mengejutkan ketika Anda melihat sejarahnya).

Jadi untuk membandingkan keduanya, mari kita definisikan:

Ekspresi Reguler

Jadi ekspresi reguler didefinisikan secara rekursif sebagai berikut:

1. $\emptyset$
2. $\varepsilon$
3. $a$$a \in \Sigma$
4. $A$$B$
   • $A\cdot B$
   • $A \mid B$
   • $A^{\ast}$

Bersamaan dengan beberapa semantik (yaitu bagaimana kita menafsirkan operator untuk mendapatkan string), kita mendapatkan cara menghasilkan string dari bahasa reguler.

Tata Bahasa Reguler

$(N,\Sigma, P, S \in N)$$N$$\Sigma$$S$$P$$\Sigma^{\ast}$$P$

Tata Bahasa Linier Kanan

$B$$C$$a$$\varepsilon$

1. $B \rightarrow a$
2. $B \rightarrow aC$
3. $B \rightarrow \varepsilon$

Tata Bahasa Linier Kiri

$B \rightarrow Ca$

Hal-hal untuk Direnungkan

Jadi melihat definisi ini dan bermain dengannya, kita dapat melihat bahwa ekspresi reguler terlihat seperti aturan yang cocok, atau cara berurusan dengan string sedikit demi sedikit.

$S$

Namun ini benar-benar melakukan hal mendasar yang sama, dan bagaimana Anda melihat metafora fungsi mereka benar-benar terserah Anda.