0
$\begingroup$

Consider the language $L$ of rectangular matrices written down as a comma separated list of integers where each list represents a row of the matrix and rows are separated by a semicolon. There may be an arbitrary number of rows, but each row must contain the same number of integers.

For example: $[3, 5, 6; 8, 9, 10; 7, 3, 6] \in L$ and $[3, 5, 6; 7, 8, 10, 12; 7] \notin L$, because each row contains a different number of integers and so the matrix is not rectangular.

Is this language context-free? I have a very strong hunch that it isn't, given that not even the language $A^{n}B^{n}C^{n}$ is context free, but I don't have much experience with proofs using the pumping lemma for context-free languages and I'm hoping there is a simpler way to prove that $L$ is not context free.

$\endgroup$
1
  • $\begingroup$ You tagged pumping-lemma: can you please spell out how far that got you? $\endgroup$ – greybeard Jun 5 '20 at 13:23
1
$\begingroup$

Delete all numbers from your language $L$, and replace $,$ with $a$ and $;$ as $b$. Then intersect it with the regular language $a^*ba^*ba^*$. You obtain a new language $L' = \{a^n b a^n b a^n : n \in \mathbb{N}\}$. If $L$ is context-free, then $L'$ will be context-free too, as it has been obtained by applying a homomorphism and then intersecting with a regular language, both of which preserve context-freeness. However, $L'$ is a standard example of a non-context-free language, so $L$ must be non-context-free as well.

$\endgroup$
0
$\begingroup$

To convert this question into an easier question to answer, practically, we consider the language $\hat L=\{(a^nb)^n|n\in\mathbb N\}$. Proving this is not context free is enough, since we can give a hommomorphism from $L$ to it by $h(",")=a,\space h(";")=b,\space h(x)=\epsilon$ for every other $x$, and then we get $h(L)=\hat L$.

Now, I think it should be easier for you to prove using the pumping lemma. Specifically, we say that if we assume (towards contradiction) that $\hat L$ is context-free, then there is some pumping length $l$, and we will define $w=(a^{l+10000}b)^{l+10000}\in \hat L$ (I chose a big number there for good measure, and for reasons you will se down below. This is usually not required). Now, by the pumping lemma, since $|w| \ge l$ we have some $x,v,y,u,z$ such that $w=xvyuz$ and are satisfying $|vyu|\le l$, $|vu|\ge 1$, $xv^nyu^nz\in \hat L$ for every $n\in\mathbb N$. Let us notice, that taking $n=0$ we get $xyz\in\hat L$ so there is some $k\in \mathbb N$ with $xyz=(a^kb)^k$ but since $|vu|\ge 1$ then $|xyz|\le|w|$ and thus $k<n$. Notice that when we removed $v,u$, we removes at most 2 (or some other small constant compared to 10000) "groups" of $l$ "a" and 1 "b", and since that number is smaller than 10000... there must be some "group" that was not touched. i.e, it still had $l+10000$ "a" in it, therefore we must have $xyz=(a^{l+10000}b)^{l+10000}$ but then $xyz=w$ and so $|vu|=0$ in contradiction!

Thus $\hat L$ is not context free and so is $L$

$\endgroup$
3
  • 1
    $\begingroup$ I don't think this argument is quite correct, but I suspect it can be repaired. You seem to be assuming the question is asking about square matrices, but it is actually asking about rectangular matrices. Consequently the language we obtain is $\hat{L} = \{(a^n b)^m:m,n \in \mathbb{N}\}$. If you intersect with the regular language $a^* b a^* b$ you get $\{a^n b a^n b : n \in \mathbb{N}\}$, which is not context-free, hence neither is $\hat{L}$. $\endgroup$ – D.W. Jun 5 '20 at 18:41
  • $\begingroup$ Oh you are right! This is also a simpler proof from the version I posted here (also without directly applying the pumping lemma!) $\endgroup$ – nir shahar Jun 5 '20 at 19:11
  • $\begingroup$ I will fix my proof to rectangular matrices (still using the pumping lemma though) $\endgroup$ – nir shahar Jun 5 '20 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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