É o idioma

É o idioma $L = \{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ sem contexto?

Eu acho que não é livre de contexto, porque parece muito complicado para um PDA decidir se dois números são co-primos ou não.

Tentei usar o lema de bombeamento sem sucesso.

Qualquer ajuda seria apreciada com prazer.

Editar:

Aqui está uma das minhas tentativas fracassadas com o lema de bombeamento:

Deixei $N$ seja uma constante. Dê uma nobre $p$ de tal modo que $p > N!$ e depois pegue a palavra $z = 0^p 1^{p+N!} \in L$ . Deixei $z = uvwxy$ ser uma decomposição de $z$ satisfazendo as condições do lema de bombeamento.

E se $vx$ contém apenas zeros então $|vx| = k$ é um número inteiro entre $1$ e $N$ . Definir $m$ como . Para a palavra $m = N!/k$ $i = m+1$ $uv^iwx^iy = 0^{p+N!}1^{p+N!} \not\in L$

No entanto, não consegui encontrar um número inteiro para os outros casos de decomposição. $i$

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

Bem-vindo à Ciência da Computação ! Deixe-me direcioná-lo para nossas perguntas de referência que podem cobrir seu problema. Por favor, trabalhe com as perguntas relacionadas listadas lá, tente resolver seu problema novamente e edite para incluir suas tentativas, juntamente com os problemas específicos que você encontrou. Eu acho que o teorema de Parikh pode funcionar para você.

Raphael

Parikh deve funcionar, mas também bombeamento padrão / Ogden, certo?

Ran G.

Na verdade, é uma pergunta do questionário. Como não aprendemos o teorema de Parikh, provavelmente existe uma maneira de mostrar que ele não é livre de contexto com o lema de bombeamento ou com as propriedades de fechamento.

precisa saber é o seguinte

@Raphael, neste caso, o teorema de Parikh realmente não acrescenta nada além do lema de bombeamento direto (ou seja, de

0^{n} 1^{m}

$0^n 1^m$ pode obter tudo

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

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

a

$a$ ,

b

$b$ não tanto zero como

k \geq - 1

$k \ge -1$ ) Mas não vejo nenhuma maneira de forçar

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

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

vonbrand

@vonbrand Podemos trabalhar em

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

$\overline{L} \cap \mathcal{L}(0^*1^*)$ em vez de; veja aqui .

Raphael

Respostas:

Ridículo que eu não vi isso antes ...

A prova de que o idioma (chame-o $\mathcal{L}$ ) não é livre de contexto é por contradição. Presumir $\mathcal{L}$ é livre de contexto, pelo lema de bombeamento para CFGs há uma constante $N$ de modo que cada string $\sigma \in \mathcal{L}$ de tal modo que $\lvert \sigma \rvert \ge N$ pode ser escrito $\sigma = u v x y z$ com $v y \ne \epsilon$ tal que para todos $k \ge 0$ a corda $u v^k x y^k z \in \mathcal{L}$ . Toma $m, n$ primos diferentes (tais que $\gcd(m, n) = 1$ ) e $m, n > 2N$ , e pegue $\sigma = 0^m 1^n$ . A corda bombeada será $0^{m + k a} 1^{n + k b}$ para algumas constantes $a$ , $b$ , não ambos zero, e tal que $a < m$ e $b < n$ (temos $a, b \le N < m / 2, n / 2$ a propósito $m$ , $n$ foram selecionados). O caso de um deles zero foi coberto pelo OP, então considere $a, b \ne 0$ . Agora:

\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*}$

Isso tem uma solução única $k^*$ módulo $m n$ pelo teorema do resto chinês (temos $a < n$ , e como $n$ é primo, $\gcd(a, n) = 1$ ; similarmente $b$ e $m$ ) e, portanto, podemos escrever:

\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*}$ ou seja,

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

$m n \mid \gcd(m + k^* a, n + k^* b)$ . Contradição.

vonbrand
fonte

Obrigado pela sua resposta. Gostei da maneira como você abordou isso. No entanto, eu não entendo como você usou o teorema do restante chinês, se isso só pode ser aplicado a um sistema de congruências lineares da forma:

\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*}$

precisa saber é o seguinte

@ Robert777, basta escrever

k a \equiv - m (\mod n)

$k a \equiv -m \pmod{n}$ e assim por diante.

vonbrand

mas você obtém uma congruência da forma:

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

$\begin{align*} a x &\equiv b \pmod{m} \\ \end{align*}$ e não é o mesmo. Por exemplo, se

g c d (a, m) ⧸ | b

$gcd(a,m) \not | b$ então a congruência não tem soluções.

precisa saber é o seguinte

@ Robert777, você está absolutamente certo. Alterado para selecionar

m

$m$ ,

n

$n$ prime. Obrigado!

vonbrand

Ok, depois de usarmos o teorema do restante chinês, por que podemos escrever essas congruências:

\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*}$

precisa saber é o seguinte