1
$\begingroup$

Can someone please explain me how to solve this?

In this post here was one user sketching the solution but I still don't understand how to construct a context-free language $L$ in such a way that the words in $L$ of the form $ww$ are $a^mb^mc^ma^mb^mc^m(m≥0)$. How does the grammar for L looks like? What equalities have the grammar to ensure and why?

Thanks!

$\endgroup$
0

2 Answers 2

2
$\begingroup$

Take a look at $$L = \{a^nb^nc^ma^mb^kc^l : n, m, k, l \geq 0\}.$$

Now take some $x \in L$ with $x = ww$, then $x = a^nb^nc^ma^mb^kc^l$ for some $n, m, k, l \geq 0$. There's only one possible way to split $x$ into two equal parts $w$:

$$w = a^nb^nc^m = a^mb^kc^l.$$

Note that for distinct symbols $c_i$, $c_1^{n_1}c_2^{n_2}...c_k^{n_k} = c_1^{m_1}c_2^{m_2}...c_k^{m_k}$ implies $n_i = m_i$ for all $i$. From this we know that

  1. $n = m$,
  2. $n = k$, and
  3. $m = l$.

So from 1. it follows that $A(L) = \{a^nb^nc^n : n \geq 0\}$ which is known to be not context-free. To prove that $L$ is context free, note that $L$ can be generated by the following context-free grammar with start variable $S$:

$$S \to ABCD$$ $$A \to aAb | \varepsilon$$ $$B \to cBa | \varepsilon$$ $$C \to bC | \varepsilon$$ $$D \to cD | \varepsilon$$

$\endgroup$
5
  • $\begingroup$ That makes so sense, thanks! $\endgroup$
    – shinichi
    Feb 13 at 22:38
  • $\begingroup$ @shinichi Glad to hear :) $\endgroup$
    – Knogger
    Feb 13 at 22:51
  • $\begingroup$ Did you mean something along the lines of 1.-3. by "What equalities have the grammar to ensure"? I wasn't entirely sure what was meant by that. $\endgroup$
    – Knogger
    Feb 13 at 22:51
  • $\begingroup$ yes that's what I meant! One clarification question: Why is it $a^m$ and not e.g. $a^s$ with $s \geq 0$? One thing that comes to my mind is to ensure that the only combination to split $x$ in equal parts $w$ is $w=a^n b^n c^m=a^mb^kc^l$. If $L=\{a^nb^nc^m=a^sb^kc^l| n,m,s,k,l \geq 0\}$ then there would be the possiblity of the word $ww=cc$. Is that the reason? $\endgroup$
    – shinichi
    Feb 13 at 23:00
  • $\begingroup$ Yes, exactly! A nice way to get to a solution like mine or the one by Hendrik Jan is by starting off with your example language, setting up equations like 1.-3. for it, and then to figure out what additional restrictions on $m, s, k, l$ you would need to prove $A(L) = \{a^nb^nc^n : n \geq 0\}$. $\endgroup$
    – Knogger
    Feb 13 at 23:20
1
$\begingroup$

Context-free languages are not closed under intersection. We start there. The relevant example is here that $\{ a^p b^p c^q \mid p,q\ge 0 \} \cap \{ a^p b^q c^q \mid p,q\ge 0 \} = K$, where $K = \{ a^m b^m c^m \mid m\ge 0 \}$ is not context-free.

The two languages each force a pair of letters to have the same number.

For your question we set $L = \{ a^p b^p c^q \mid p,q\ge 0 \} \cdot \{ a^p b^q c^q \mid p,q\ge 0 \}$. Or, written differently $L = \{ a^p b^p c^q a^r b^s c^s \mid p,q,r,s\ge 0 \}$. If a string in $L$ is of the form $xx$ the two $abc$-halves must be equal. Thus of the form $x= a^m b^m c^m$.

$\endgroup$
1
  • $\begingroup$ Thanks thats a neat way to solve it! I didnt consider closure properties. The decision to concatenate with $\{a^pb^qc^q | p,q\geq 0\}$ is to ensure that there is no other word in the form $ww$ in $L$ then $abcabc$, right? $\endgroup$
    – shinichi
    Feb 13 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.