Ist die Sprache

Ist die Sprache $L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ kontextfrei?

Ich denke, dass es nicht kontextfrei ist, weil es für einen PDA zu kompliziert erscheint, um zu entscheiden, ob zwei Zahlen Co-Prime sind oder nicht.

Ich habe erfolglos versucht, das Pump-Lemma zu verwenden.

Jede Hilfe wäre gerne dankbar.

Bearbeiten:

Hier ist einer meiner fehlgeschlagenen Versuche mit dem Pump-Lemma:

Sei $N$ eine Konstante. Nehmen Sie eine Primzahl $p$ so, dass $p > N!$ und dann nimm das Wort $z = 0^p 1^{p+N!} \in L$ . Sei $z = uvwxy$ eine Zerlegung von $z$ die die Bedingungen im Pump-Lemma erfüllt.

Wenn nur Nullen enthält, dann eine ganze Zahl zwischen und . Definiere als . Für das Wort $vx$ $|vx| = k$ $1$ $N$ $m$ $m = N!/k$ $i = m+1$ $uv^iwx^iy = 0^{p+N!}1^{p+N!} \not\in L$

Ich habe jedoch keine solche Ganzzahl für die anderen Zerlegungsfälle gefunden. $i$

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

Willkommen in der Informatik ! Lassen Sie mich Sie auf unsere Referenzfragen hinweisen, die Ihr Problem abdecken könnten. Bitte bearbeiten Sie die dort aufgeführten Fragen, versuchen Sie, Ihr Problem erneut zu lösen, und bearbeiten Sie sie, um Ihre Versuche zusammen mit den spezifischen Problemen, auf die Sie gestoßen sind, einzuschließen. Ich denke, Parikhs Theorem könnte für Sie funktionieren.

Raphael

Parikh sollte funktionieren, aber auch Standardpumpen / Ogden, oder?

Ran G.

Es ist eigentlich eine Quizfrage. Da wir den Satz von Parikh nicht gelernt haben, gibt es wahrscheinlich eine Möglichkeit zu zeigen, dass er mit dem Pump-Lemma oder den Verschlusseigenschaften nicht kontextfrei ist.

Robert777

@Raphael, in diesem Fall fügt der Satz von Parikh nichts anderes als ein gerades Pump-Lemma hinzu (dh von

können alle

für einige

nicht sowohl Null als auch

). Aber ich sehe keine Möglichkeit,

zu erzwingen . 0n1m $0^n 1^m$

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

a $a$

b $b$

k≥−1 $k \ge -1$

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

vonbrand

@vonbrand Wir können stattdessen an

; siehe hier . L¯¯¯¯∩L(0∗1∗) $\overline{L} \cap \mathcal{L}(0^*1^*)$

Raphael

Antworten:

Lächerlich, dass ich das vorher nicht gesehen habe ...

Der Beweis, dass die Sprache (nennen wir es ) nicht kontextfrei ist, ist ein Widerspruch. Angenommen, ist kontextfrei, durch das Pump-Lemma für CFGs gibt es eine Konstante so dass jeder String so ist, dass kann sie geschrieben werden , mit so dass für alle die Zeichenfolge . Nehmen $\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}$ verschiedene Primzahlen (so dass ) und und nehmen . Der gepumpte String ist für einige Konstanten , , nicht beide Null, und so, dass und (wir haben $m, n$ $\gcd(m, n) = 1$ $m, n > 2N$ $\sigma = 0^m 1^n$ $0^{m + k a} 1^{n + k b}$ $a$ $b$ $a < m$ $b < n$ $a, b \le N < m / 2, n / 2$ by the way $m$ , $n$ were selected). The case of one of them zero was covered by OP, so consider $a, b \ne 0$ . Now:

m + k a n + k b \equiv 0 (mod n) \equiv 0 (mod m)

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

This has a unique solution $k^*$ modulo $m n$ by the chinese remainder theorem (we have $a < n$ , and as $n$ is prime, $\gcd(a, n) = 1$ ; similarly $b$ and $m$ ), and thus we can write:

m + k * a n + k * b \equiv 0 (mod m n) \equiv 0 (mod m n)

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

mn∣gcd(m+k∗a,n+k∗b) $m n \mid \gcd(m + k^* a, n + k^* b)$ . Contradiction.

vonbrand
quelle

Thanks for your reply. I liked the way you approached this. However, I don't understand how did you use the chinese remainder theorem if this can only be applied on a system of linear congruences of the form:

x x \equiv b 1 (mod m 1) \equiv b 2 (mod m 2)

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

Robert777

@Robert777, just write

ka≡−m(modn) $k a \equiv -m \pmod{n}$ and so on.

vonbrand

but you get a congruence of the form:

a x \equiv b (mod m)

$\begin{align*} a x &\equiv b \pmod{m} \\ \end{align*}$ and it's not the same. For example if

gcd(a,m)/|b $gcd(a,m) \not | b$ then the congruence has no solutions.

Robert777

@Robert777, you are absolutely right. Changed to select

m $m$ ,

n $n$ prime. Thanks!

vonbrand

Okay, after we've used the chinese remainder theorem, why can we write these congruences:

m + k * a n + k * b \equiv 0 (mod m n) \equiv 0 (mod m n)

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

Robert777