Le parole non doppie sono CF

Calcolabilità, modelli di calcolo, complessità, linguaggi formali.

Le parole non doppie sono CF

Dato un alfabeto finito $\Sigma$, dimostrare che il complementare di $\{ ww \mid w \in \Sigma^* \}$ è context-free.
The first rule of first order logic is you can't talk about first order logic
marco

Messaggi: 26
Iscritto il: mer 2 lug 2008, 16:27

Re: Le parole non doppie sono CF

Mi metto in alfabeto binario $\Sigma=\{0,1\}$. Proveremo per prima cosa che il suddetto linguaggio non è regolare, poi che è context-free. (Sorry se in inglese, l'avevo già trascritto... )

To prove that $\overline{\textbf{SQ}}$ is not regular, it is sufficient to prove that $\textbf{SQ}:=\{t \in \{0,1\}^* : \exists w\in\{0,1\}^* \text{ s.t. } t = ww\}$ is not regular, since the regular languages are closed under complement. Suppose $\textbf{SQ}$ is regular, then by the pumping lemma for regular languages there exists $n\geq 1$ such that for every word $t\in\textbf{SQ}$ with $|t|\geq n$ there exist $x,y,z\in\{0,1\}^*$ satisfying $t=xyz, y\neq\epsilon, |xy|\leq n$ s.t. $xy^i z\in\textbf{SQ}$ for every $i\geq 0$. Now we consider the square $t:=(0^n1^n)^2$. Then for any pumping decomposition $t=xyz$ s.t. $|xy|\leq n$, it must be $y=0^{|y|}$. Then $xy^0 z = xz = 0^m 1^n 0^n 1^n$ for some $m\leq n$, hence $xz$ is clearly not a square. This contradicts the pumping lemma so $\textbf{SQ}$ is not regular. Hence $\overline{\textbf{SQ}}$ is not regular. []

[Questo in realtà prova che il suddetto linguaggio non è regolare pure per alfabeti arbitrari. Anche perché se per assurdo fosse regolare per qualche alfabeto non binario, allora esisterebbe un qualche DFA che lo riconosce. Ma allora, cancellando gli archi del DFA con simboli diversi da 0 e da 1 si otterrebbe sempre un DFA che riconosce lo stesso linguaggio su alfabeto binario.]

In order to prove that $\overline{\mathbf{SQ}}$ is context-free consider the following grammar:
$G:$
$S\rightarrow AB \,|\, BA \,|\, A \,|\, B$
$A \rightarrow 0A0 \,|\, 0A1 \,|\, 1A0 \,|\, 1A1 \,|\, 0$
$B \rightarrow 0B0 \,|\, 0B1 \,|\, 1B0 \,|\, 1B1 \,|\, 1$

We claim $\overline{\mathbf{SQ}} \subseteq L(G)$. Let $t\in\overline{\mathbf{SQ}}$ be not-square.
For $b\in\{0,1\}$ define $X_b:=\begin{cases} A , & \mbox{ if } b=0 \\ B, & \mbox{ if } b=1 \end{cases}$.
Now we pose a condition on the parity of $|t|$.
If $|t|=2n+1$ for some $n\geq 0$, then $t=xby$ for some $x,y\in\{0,1\}^*\wedge b\in\{0,1\}$ s.t. $|x|=|y|$. Consider the following production
$\displaystyle S \Rightarrow X_b \Rightarrow x[1]X_by[n] \Rightarrow x[1]x[2]X_b y[n-1]y[n] \Rightarrow \cdots \Rightarrow xX_b y = t$.
Then $t \in L(G)$.
Otherwise $|t|=2n$ for some $n\geq 1$, then $t=xy$ for some $x,y\in\{0,1\}^*$ s.t. $|x|=|y|$. Since $t$ is not a square, there exists the least $1\leq i\leq n$ s.t. $x[i]\neq y[i]$. Now we write $t=ab$ for
$a:=t[1\cdots i-1]\cdot (x[i]=t[i])\cdot t[i+1\cdots 2i-1]$ and
$b:=t[2i\cdots n+i-1]\cdot (y[i] = t[n+i])\cdot t[n+i+1\cdots 2n]$.

Then $S\Rightarrow X_{x[i]} \Rightarrow \cdots \Rightarrow a$ and $S\Rightarrow X_{y[i]} \Rightarrow \cdots \Rightarrow b$. Hence $S\Rightarrow X_{x[i]}X_{y[i]} \Rightarrow \cdots \Rightarrow t$, so $t \in L(G)$ and $\overline{\mathbf{SQ}} \in L(G)$ follows.

Now we claim and prove that $L(G) \subseteq \overline{\mathbf{SQ}}$. Let $t\in L(G)$. Without loss of generality we assume the productions to be of the form $S\Rightarrow AB | BA \Rightarrow \cdots \Rightarrow t$, since otherwise $|t|$ is odd and therefore $t$ is not a square. Let w.l.o.g. to be $S\Rightarrow AB \Rightarrow \cdots \Rightarrow t$. Let $i$ be the height of the parse sub-tree of $t$ starting from $A$ and let $x$ be the word parsed by the same tree, similarly let $j$ be the height of the parse sub-tree of $t$ starting from $B$ and $y$ be the word produced. It must be that $x[i] = 0 \wedge y[j] = 1 \wedge t=xy$.
Now let $n:=\frac{|t|}{2}$.
We claim that $y[j] = t[n+i]$ since $2i-1+2j-1=2n\iff i+j-1=n$ imply $n+i = 2i-1 + j$.
Then $t[i] = x[i] \neq y[j] = t[n+i]$.
This proves that $t$ is not a square. Hence $t\in\overline{\mathbf{SQ}}$. This proves $L(G)\subseteq \overline{\mathbf{SQ}}$. []

This idea should generalize also on $\Sigma=\{\sigma_0,\sigma_1,\ldots, \sigma_{n-1}\}$, by picking the following grammar:
$G:$
$S\rightarrow A^{(i)}A^{(j)} \,|\, A^{(i)} \text{ for each } 0\leq i\neq j < n$
$A^{(i)} \rightarrow \sigma_k A^{(i)}\sigma_j \,|\, \sigma_i \text{ one for each } 0\leq i < n \text{ and for any } 0\leq k,j < n$ []
Carlo Comin

vl4d

Messaggi: 140
Iscritto il: ven 13 giu 2008, 13:54

Torna a Fondamenti dell'Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite