Apakah bahasa unary biasa jika eksponennya adalah fungsi linear?

13

Saat melakukan tugas saat ini untuk bahasa formal dan kursus automata saya, saya agak terjebak pada latihan yang melibatkan bahasa unary (saya harap itu istilah yang tepat), yaitu, bahasa yang dibangun di atas satu huruf. Saya tidak ingin bertanya tentang latihan spesifik, tetapi tentang dugaan yang jauh lebih umum yang saya kemukakan:

Biarkan dan . Dugaan saya adalah: $\Sigma=\{a\}$ $L=\{a^{f(n)}\in\Sigma^*:n\in\mathbb N_0\}$

L is regular \Leftrightarrow \exists x, y \in N_{0} : f (n) = x \cdot n + y

$L\text{ is regular}\Leftrightarrow \exists x,y\in\mathbb N_0:f(n)=x\cdot n+y$

Apakah pertanyaan ini pernah melihat perlakuan ilmiah sebelumnya? Apakah itu "jelas" benar / salah?

Bagi saya, jelas arah " " benar karena kita hanya dapat membangun DFA dengan menyatakan bahwa siklus melalui menyatakan setelah membaca melalui menyatakan dan menerima iff itu pada angka . $\Leftarrow$ $x+y$ $x$ $y$ $y$

formal-languages regular-languages SEJPM
sumber

Kerja bagus, membuat pengamatan ini bukanlah yang saya harapkan dari siswa kebanyakan!

Raphael

Sepakat. Ini pengamatan yang sangat bagus.

Rick Decker

Tidak jelas dari judulnya, tetapi kami sudah memiliki pertanyaan ini sebelumnya, hingga lemma ekuivalensi kecil: Apa set panjang kata yang mungkin dalam bahasa biasa?

Gilles 'SANGAT berhenti menjadi jahat'

9

Linear dekat, tetapi istilah teknis yang Anda cari adalah semilinear:, yaitu, gabungan terbatas dari set linier.

Setengah dari bukti ini adalah akibat wajar dari Teorema Parikh , yang mengatakan bahwa bahasa bebas konteks memiliki peta Parikh semi-linear (yaitu, himpunan vektor yang berisi kemunculan setiap huruf dalam alfabet).

Untuk bahasa unary, peta bahasa parikh adalah bahasa itu sendiri (yaitu setiap kata secara unik diidentifikasi oleh berapa banyak huruf yang dimilikinya), sehingga setiap bahasa reguler unary adalah semi-linear.

Setengah bukti lainnya menunjukkan bahwa Anda dapat membuat bahasa reguler yang berisi setiap set semi-linear unary. Ini membutuhkan sedikit usaha, tetapi tidak terlalu sulit jika Anda menggunakan ekspresi reguler:

mengenali bahasa $a^k$ $\{ k \}$
mengenali $(a^k)^*$ $\{xk \mid x \in \mathbb{N}_0 \}$
mengenali jika mengenali dan mengenali , di mana sini adalah penambahan elemen-bijaksana $R_1 R_2$ $S_1 + S_2$ $R_1$ $S_1$ $R_2$ $S_2$ $+$
mengenali jika mengenali dan mengakui , di manadi sini adalah persatuan ekspresi reguler. $R_1 | R_2$ $S_1 \cup S_2$ $R_1$ $S_1$ $R_2$ $S_2$ $|$

Ya ampun
sumber

6

Anda hampir benar. Anda perlu mempertimbangkan fakta bahwa Anda mungkin memiliki beberapa fungsi linear, seperti atau Anda mungkin memiliki bahasa yang terbatas, seperti (Dalam kedua kasus, kami hanya mengambil penyatuan bahasa biasa, jadi semuanya berjalan seperti seharusnya.)

L = {{Sebuah}^{k} ∣ k = 3 n + 1 atau k = 7 n + 4}

$L=\{a^k\mid k=3n+1\text{ or }k=7n+4\}$

L = {{Sebuah}^{k} ∣ k = 4 n + 2 atau k = 13}

$L=\{a^k\mid k=4n+2\text{ or }k=13\}$

Rick Decker
sumber

Apakah bahasa unary biasa jika eksponennya adalah fungsi linear?

Jawaban: