I was given the question

Where does the following language fit in the Chomsky hierarchy?

Nonnegative solutions $(x,y)$ to the Diophantine equation $3x-y=1$.

I understand languages like $L = \{ 0^n1^n \mid n \ge 1\}$, but this language confuses me. What do the words in the language look like? How could I represent it using a grammar or regular expression?


The first thing you'll want to do is look at the phrase itself, and ignore all the references to languages for a moment.

So, what are the non-negative solutions to the diophantine equation $3x-y=1$? If we fix some $x$, then $y = 3x-1$. This means that the set of solutions is $\{ (x, 3x-1)\ |\ x > 0 \}$ (note that $x=0$ yields a negative $y$, and a positive $x$ yields a positive $y$).

Now, we can associate a string with any non-negative number pair $(x, y)$: for instance, $(100, 299)$ can be associated with the string (100, 299). If we apply this to every pair in the set, the resulting set of strings is the language of this set. Note that the question does not really make it clear how to associate a string with a solution, but I'm pretty sure they mean the above.

Now all you have to do is figure out in which level of the Chomsky Hierarchy this language falls. As I have a mild suspicion that this is a homework question, I'll not immediately spill the beans. If you can confirm this is not a homework question and you still need help, I'll edit the answer in.

  • $\begingroup$ It's for homework. I know the generation problem for this is only solvable by a turing machine or equivalent. I can see how the recognition problem would be too, so my thought would be that it's most specific chomsky class is Recursive. I have no clue how to show that it's not Context-sensitive though. $\endgroup$ – justausr Mar 21 '12 at 18:38
  • $\begingroup$ @justausr The language is context sensitive: a language is context sensitive iff it can be parsed by some program using non-determinism and at most linear space (so no time bound). I'm pretty sure I can parse the 100, compute 100*3-1, and check whether it's equal to 299 in linear time, and therefore linear space, which makes this language context-sensitive. $\endgroup$ – Alex ten Brink Mar 21 '12 at 19:01
  • $\begingroup$ my thoughts on homework questions for what it's worth, meta.cs.stackexchange.com/a/174/596 $\endgroup$ – justausr Mar 21 '12 at 19:15
  • $\begingroup$ @AlextenBrink: Multiplication takes quadratic time on TMs, but linear space should work nevertheless. $\endgroup$ – Raphael Mar 21 '12 at 23:27
  • $\begingroup$ @Raphael Multiplication of two arbitrary unbounded integers is quadratic, but multiplying one arbitrary unbounded integer by some fixed constant would be linear, wouldn't it? $\endgroup$ – Ben Mar 22 '12 at 2:18

The problem statement is indeed incomplete, but when you see this, you can safely assume that “representing integers in decimal notation” or “representing integers in binary notation” was meant.

So here, if we assume binary notation, the alphabet is contains 5 characters: 0, 1, (, ) and ,. If we assume decimal notation, the alphabet would additionally contain the digits 2 through 9.

The language in question is a subset of the language matched by the regular expression $\mathtt{(}(0|1)^*\mathtt{,}(0|1)^*\mathtt{)}$ (going with binary notation). If we assumed the simpler case of the equation $2x-y=0$, then the language would be all pairs of numbers $(x,y)$ such that $y = 2x$. In binary, this means $y$ is $x$ with an additional 0 at the end. In other words, the language would consist of words of the form ($x$,$x$0). Where does this fit in the Chomsky hierarchy?

Here, we have a more complicated example: you have to recognize whether $y = 3x-1$. How do binary (or decimal) expansions of $x$ and $y$ compare when $y=3x-11$?


The question is not complete, since a language is a set of words, not pairs. If you encode it as $x\$y$ where $x,y$ are in binary, it is context-sensitive but not context-free (see Gilles's answer), if you encode it as $x\$y^R$ it is context-free but not regular (exercise), if you suitably intersperse bits of $x$ and $y$, it is regular! See here.

  • $\begingroup$ The answer is even more trivial if the encoding is unary. But then, this answer should be here, where it would be redundant. $\endgroup$ – Raphael Mar 22 '12 at 22:14
  • $\begingroup$ Raphael: I disagree, that question has a well-defined encoding of input. This question doesn't, and I am pointing out it is important. $\endgroup$ – sdcvvc Mar 22 '12 at 22:17
  • $\begingroup$ But your comments regarding the classes the resulting language would fall in are not helpful for this question; it is only about how to encode things like this at all. $\endgroup$ – Raphael Mar 22 '12 at 22:37

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.