Mungkinkah ada 'kondisi mati' dalam tata bahasa bebas konteks?

Bisakah tata bahasa bebas konteks menyertakan "keadaan mati" dari otomat, seperti

G = ({Sebuah, b, c}, {SEBUAH, B, C}, {SEBUAH \to Sebuah B, B \to b, B \to C, C \to c C}, SEBUAH) ?

$G = \big(\{a, b, c\}, \{A, B, C\}, \{A\to aB, B\to b, B\to C, C\to cC\}, A\big)\,?$

Aturan produksi dan akan berulang selamanya dan tidak pernah menghasilkan kata. Apakah ini diperbolehkan atau HARUS aturan produksi berakhir dengan terminal di beberapa titik? $B\to C$ $C\to cC$

context-free automata formal-grammars r3r57
sumber

Jawaban:

Tata bahasa bebas konteks diperbolehkan mengandung aturan yang tidak produktif . Ini diterima, karena setiap CFG menghasilkan bahasa yang sama seperti beberapa CFG yang tepat yang tidak mengandung aturan tidak produktif, tidak ada produksi string kosong, dan tidak ada siklus; jadi aman untuk mengasumsikan bahwa CFG adalah tepat tanpa kehilangan keumuman.

ilke444
sumber

Tidak cukup: CFG yang tepat harus memenuhi dua persyaratan lagi. Jadi saya akan merumuskan kembali ini.

reinierpost

@reinierpost: Saya kira maksud Anda ada kelas-kelas CFG yang melarang aturan tidak produktif, tetapi masih termasuk CFG non-Proper? Saya kira reformulasi dapat sesederhana: "kecuali, misalnya, mereka adalah"

mhelvens

Maksud saya tidak setiap CFG tanpa aturan tidak produktif adalah wajar, yang bertentangan dengan pernyataan Anda; tetapi definisi CFG yang tepat, dengan secara eksplisit mengecualikan aturan yang tidak produktif, memperjelas bahwa ini dimungkinkan dalam CFG yang sewenang-wenang, jadi itulah yang saya tulis.

reinierpost

Terima kasih atas peningkatan Anda. Saya bermaksud mengatakan bahwa ada subkelas CFG yang tidak diizinkan mengandung aturan semacam itu.

ilke444

Apakah ada CFG yang tepat yang tidak mengandung aturan tidak produktif, tidak ada produksi string kosong, dan tidak ada siklus yang menghasilkan bahasa yang sama dengan ({a}, {A}, {A-> epsilon}, A)? Saya suka kalimat pertama. Mungkin kalimat kedua adalah "Ini karena definisi CFG memungkinkan string terminal dan non-terminal yang terbatas sebagai sisi kiri produksi."

Theodore Norvell

Ya tentu saja. Setiap NFA dapat ditulis sebagai CFG. Dan membangun DFA dengan 'kondisi mati' (istilah yang saya ajarkan, adalah 'tenggelam') adalah sepele.

G = ({Sebuah}, {SEBUAH}, {SEBUAH \to SEBUAH}, SEBUAH)

$G = (\{a\}, \{A\}, \{A\to A\},A)$

{a}

$\{a\}$

$\epsilon$

David
sumber