Est la langue

Est la langue $L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ sans contexte?

Je suppose que ce n'est pas sans contexte car il semble trop compliqué pour un PDA de décider si 2 nombres sont co-amorcés ou non.

J'ai essayé d'utiliser le lemme de pompage en vain.

Toute aide serait grandement appréciée.

Éditer:

Voici l'une de mes tentatives infructueuses avec le lemme de pompage:

Laisser $N$ être une constante. Prenez une prime $p$ tel que $p > N!$ puis prenez le mot $z = 0^p 1^{p+N!} \in L$ . Laisser $z = uvwxy$ être une décomposition de $z$ satisfaisant aux conditions du lemme de pompage.

Si $vx$ ne contient alors que des zéros $|vx| = k$ est un entier entre $1$ et $N$ . Définir $m$ comme $m = N!/k$ . Pour $i = m+1$ le mot $uv^iwx^iy = 0^{p+N!}1^{p+N!} \not\in L$

Cependant, je n'ai pas réussi à trouver un tel entier $i$ pour les autres cas de décomposition.

formal-languages context-free pumping-lemma pushdown-automata Robert777
la source

Bienvenue en informatique ! Permettez-moi de vous orienter vers nos questions de référence qui pourraient couvrir votre problème. Veuillez résoudre les questions connexes répertoriées ici, essayez de résoudre à nouveau votre problème et modifiez-le pour inclure vos tentatives ainsi que les problèmes spécifiques que vous avez rencontrés. Je pense que le théorème de Parikh pourrait fonctionner pour vous.

Raphael

Parikh devrait fonctionner, mais aussi le pompage standard / Ogden, non?

Ran G.

C'est en fait une question de quiz. Puisque nous n'avons pas appris le théorème de Parikh, il existe probablement un moyen de montrer qu'il n'est pas dépourvu de contexte avec le lemme de pompage ou avec les propriétés de fermeture.

Robert777

@Raphael, dans ce cas, le théorème de Parikh n'ajoute vraiment rien au-delà du lemme de pompage direct (c'est-à-dire de

0^{n} 1^{m}

$0^n 1^m$ peut obtenir tout

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

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

a

$a$ ,

b

$b$ pas à la fois zéro et

k \geq - 1

$k \ge -1$ ). Mais je ne vois aucun moyen de forcer

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

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

vonbrand

@vonbrand Nous pouvons travailler sur place; voir ici .

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

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

Raphael

Réponses:

Ridicule que je ne l'ai pas vu plus tôt ...

La preuve que le langage (appelez-le ) n'est pas sans contexte est par contradiction. Supposons que est sans contexte, par le lemme de pompage pour les CFG, il y a une constante telle que chaque chaîne telle que elle puisse être écrite avec tel que pour tout la chaîne . Prenez nombres premiers différents (tels que ) et , et prenez . La chaîne pompée sera $\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}$ pour certaines constantes , , pas toutes les deux nulles, et telles que et (nous avons par la façon dont , ont été sélectionnés). Le cas de l'un d'eux zéro était couvert par OP, alors considérons . Maintenant: $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*}$

Ceci a une solution unique modulo par le théorème du reste chinois (nous avons , et comme est premier, ; de même et ), et ainsi nous pouvons écrire: c'est-à-dire . Contradiction. $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
la source

Merci pour votre réponse. J'ai aimé la façon dont vous avez abordé cela. Cependant, je ne comprends pas comment avez-vous utilisé le théorème du reste chinois si cela ne peut être appliqué que sur un système de congruences linéaires de la forme:

\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, écrivez juste et ainsi de suite.

k a \equiv - m (\mod n)

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

vonbrand

mais vous obtenez une congruence de la forme: et ce n'est pas la même chose. Par exemple, si alors la congruence n'a pas de solutions.

\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, vous avez absolument raison. Changé pour sélectionner , premier. Merci!

m

$m$

n

$n$

vonbrand

Bon, après avoir utilisé le théorème du reste chinois, pourquoi pouvons-nous écrire ces congruences:

\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