Apakah bahasa bebas konteks?

Apakah bahasa bebas konteks? $L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$

Saya kira itu bukan konteks bebas karena tampaknya terlalu rumit untuk PDA untuk memutuskan apakah 2 angka adalah co-prime atau tidak.

Saya mencoba menggunakan lemma pemompaan tetapi tidak berhasil.

Bantuan apa pun dengan senang hati akan dihargai.

Edit:

Ini adalah salah satu upaya saya yang gagal dengan lemma pemompaan:

Biarkan menjadi konstanta. Ambil utama sehinggadan kemudian mengambil kata . Misalkan menjadi dekomposisi memenuhi kondisi dalam lemma pemompaan. $N$ $p$ $p > N!$ $z = 0^p 1^{p+N!} \in L$ $z = uvwxy$ $z$

Jika hanya berisi nol maka adalah bilangan bulat antara dan . Tentukan sebagai . Untuk kata $vx$ $|vx| = k$ $1$ $N$ $m$ $m = N!/k$ $i = m+1$ $uv^iwx^iy = 0^{p+N!}1^{p+N!} \not\in L$

Namun, saya gagal menemukan integer untuk kasus dekomposisi lainnya. $i$

formal-languages context-free pumping-lemma pushdown-automata Robert777
sumber

Selamat Datang di Ilmu Komputer ! Biarkan saya mengarahkan Anda ke pertanyaan referensi kami yang mungkin mencakup masalah Anda. Silakan bekerja melalui pertanyaan terkait yang tercantum di sana, cobalah untuk menyelesaikan masalah Anda lagi dan edit untuk memasukkan upaya Anda bersama dengan masalah spesifik yang Anda temui. Saya pikir teorema Parikh mungkin berhasil untuk Anda.

Raphael

Parikh harus bekerja, tetapi juga pemompaan standar / Ogden, kan?

Ran G.

Ini sebenarnya pertanyaan kuis. Karena kita belum mempelajari teorema Parikh, mungkin ada cara untuk menunjukkan bahwa itu bukan konteks bebas dengan lemma pemompaan atau dengan sifat penutupan.

Robert777

@Raphael, dalam hal ini teorema Parikh tidak benar-benar menambahkan apa pun di luar lemma pemompaan lurus (yaitu, dari bisa mendapatkan semua untuk beberapa , bukan nol dan ). Tapi saya tidak melihat cara untuk memaksa .

0^{n} 1^{m}

$0^n 1^m$

0^{n + k a} 1^{m + k b}

$0^{n + k a} 1^{m + k b}$

a

$a$

b

$b$

k \geq - 1

$k \ge -1$

gcd (n + k a, m + k b) \neq 1

$\gcd(n + k a, m + k b) \ne 1$

vonbrand

@vonbrand Kami dapat mengerjakan sebagai gantinya; lihat di sini .

\bar{L} \cap L (0^{*} 1^{*})

$\overline{L} \cap \mathcal{L}(0^*1^*)$

Raphael

Jawaban:

Konyol bahwa saya tidak melihat ini sebelumnya ...

Bukti bahwa bahasa (sebut saja ) tidak bebas konteks adalah dengan kontradiksi. Asumsikan bebas konteks, oleh lemma pemompaan untuk CFG ada konstanta sehingga setiap string sedemikian rupa sehingga dapat ditulis dengan sedemikian rupa sehingga untuk semua string . Ambil bilangan prima yang berbeda (sehingga ) dan , dan ambil . String yang dipompa akan menjadi $\mathcal{L}$ $\mathcal{L}$ $N$ $\sigma \in \mathcal{L}$ $\lvert \sigma \rvert \ge N$ $\sigma = u v x y z$ $v y \ne \epsilon$ $k \ge 0$ $u v^k x y^k z \in \mathcal{L}$ $m, n$ $\gcd(m, n) = 1$ $m, n > 2N$ $\sigma = 0^m 1^n$ $0^{m + k a} 1^{n + k b}$ untuk beberapa konstanta , , bukan keduanya nol, dan sedemikian sehingga dan (kita memiliki dengan cara , dipilih). Kasus salah satunya nol dicakup oleh OP, jadi pertimbangkan . Sekarang: $a$ $b$ $a < m$ $b < n$ $a, b \le N < m / 2, n / 2$ $m$ $n$ $a, b \ne 0$

\begin{aligned} m + k a & \equiv 0 (\mod n) \\ n + k b & \equiv 0 (\mod m) \end{aligned}

$\begin{align*} m + k a &\equiv 0 \pmod{n} \\ n + k b &\equiv 0 \pmod{m} \end{align*}$

Ini memiliki solusi unik modulo oleh teorema sisa Cina (kita memiliki , dan karena adalah bilangan prima, ; sama dengan dan ), dan dengan demikian kita dapat menulis: yaitu, . Kontradiksi. $k^*$ $m n$ $a < n$ $n$ $\gcd(a, n) = 1$ $b$ $m$

\begin{aligned} m + k^{*} a & \equiv 0 (\mod m n) \\ n + k^{*} b & \equiv 0 (\mod m n) \end{aligned}

$\begin{align*} m + k^* a &\equiv 0 \pmod{mn} \\ n + k^* b &\equiv 0 \pmod{mn} \end{align*}$

m n ∣ gcd (m + k^{*} a, n + k^{*} b)

$m n \mid \gcd(m + k^* a, n + k^* b)$

vonbrand
sumber

Terima kasih untuk balasan Anda. Saya suka cara Anda mendekati ini. Namun, saya tidak mengerti bagaimana Anda menggunakan teorema sisa Cina jika ini hanya dapat diterapkan pada sistem kongruensi linear dari formulir:

\begin{aligned} x & \equiv b 1 (\mod m 1) \\ x & \equiv b 2 (\mod m 2) \end{aligned}

$\begin{align*} x &\equiv b1 \pmod{m1} \\ x &\equiv b2 \pmod{m2} \end{align*}$

Robert777

@ Robert777, cukup tulis dan seterusnya.

k a \equiv - m (\mod n)

$k a \equiv -m \pmod{n}$

vonbrand

tetapi Anda mendapatkan kesesuaian bentuk: dan itu tidak sama. Misalnya jika maka kongruensi tidak memiliki solusi.

\begin{aligned} a x & \equiv b (\mod m) \end{aligned}

$\begin{align*} a x &\equiv b \pmod{m} \\ \end{align*}$

g c d (a, m) ⧸ | b

$gcd(a,m) \not | b$

Robert777

@ Robert777, Anda memang benar. Diubah untuk memilih , prime. Terima kasih!

m

$m$

n

$n$

vonbrand

Oke, setelah kita menggunakan teorema sisa Cina, mengapa kita dapat menulis kongruensi ini:

\begin{aligned} m + k^{*} a & \equiv 0 (\mod m n) \\ n + k^{*} b & \equiv 0 (\mod m n) \end{aligned}

$\begin{align*} m + k^* a &\equiv 0 \pmod{mn} \\ n + k^* b &\equiv 0 \pmod{mn} \end{align*}$

Robert777