1
$\begingroup$

I began a chapter in a textbook on computational theory where they begin to talk about decidable languages.

The problems in this section are pretty confusing and I honestly don't know how to begin them because I'm not 100% on what they mean when they say "countable".

Can anyone help walk me through this problem in the book, that simply states;

Show that the number of push-down automatons is countable.

|cite|improve this question|||||
$\endgroup$
  • $\begingroup$ This is a question about math, more appropriate for math.se. Try googling "countable set". $\endgroup$ – Yuval Filmus Mar 4 '14 at 5:12
  • $\begingroup$ Imagine two infinite but enumerable sets. In a certain Sense such sets are equivalent and grasping this insight should let you See what the class of problems of which you have provided a Sample specimen is about. In Case This comment so far means Double dutch to you, consider reading a textbook on elementary set theory or on combinatorics first (the latter will be beneficial anyway if you wish to study topics in computational theory). $\endgroup$ – collapsar Mar 4 '14 at 5:53
  • 3
    $\begingroup$ @YuvalFilmus: Coming up with enumerations of CS objects should well fall into our scope, given that we deal with quite a number of pure maths questions provided they are relevant in CS contexts. $\endgroup$ – Raphael♦ Mar 4 '14 at 7:37
  • 1
    $\begingroup$ Related questions: 1 2. They refer to Turing machines but there's no significant difference. $\endgroup$ – David Richerby Mar 4 '14 at 8:26
  • 1
    $\begingroup$ Before even trying to answer the question you have highlighted, first make sure you know what all the terms mean (What's a push-down automaton? What does it mean to be countable?) After that, if you still have problems, you can ask a more focused question. $\endgroup$ – Juho Mar 4 '14 at 9:17
4
$\begingroup$

Actually the proof is not so easy. It is not technically hard, but you have to be very careful about definitions.

First, of course, you need to know what countable means, and that was given in @Raphael's answer.

The proof relies on the fact that the set of finite sequences of elements of a countable set is itself countable. You may try to prove this. Look at the proof that rational numbers are countable.

You can read that more intuitively as implying that anything that has a finite description using a finite set of symbols is countable.

Then a possible way to answer your question is to check whether this is the case for pushdown automata.

We know from the definition that they are all finitely described. Then the remaining question is whether the set of symbols used is itself countable. But short of defining that set (how?), we cannot answer that question.

The simple answer is to state that PDAs are defined up to an isomorphism. Actually a very simple isomorphism, which is a simple renaming of symbols used in the description, which has to be finite for each PDA. Then it is always possible to take the symbols in a given countable set, for example the integers.

|cite|improve this answer|||||
$\endgroup$
  • 3
    $\begingroup$ In fact, PDAs can be coded over a finite alphabet. For example, descriptions of PDAs in textbooks are coded eventually in binary. $\endgroup$ – Yuval Filmus Mar 4 '14 at 14:31
  • $\begingroup$ @YuvalFilmus This is correct. Indeed, anything that was ever written by mankind can be represented in binary (though it is a bit harder for hieroglyphs as relative locations may matter). Pretty close to Borges' Library of Babel: so many of its books have meaning, up to isomorphism. However, I think that your remark is definitely a syntactic rather than semantic one. The two "syntactic" symbols 0 and 1 are only used to represent the "semantic" symbols of the pushdown machine, as well as the specification of transitions, etc. What we write is only syntax, what it says is semantics. ... $\endgroup$ – babou Mar 4 '14 at 20:36
  • $\begingroup$ ... Of course, we may discuss syntax. PDAs are used to describe or recognize the syntax of languages, but they are the semantics for our present discussion. I see the idea of defining the PDA up to isomorphism as a semantic one. The symbols of the PDA may be taken from any set, including the reals, which are not all finitely representable, though I do not know whether there is any use for it. One thing that bothers me in all this, is that, as remarked by other users, the isomorphism has nothing to do with PDAs, but rather with properties of finite and countable sets. $\endgroup$ – babou Mar 4 '14 at 20:38
  • $\begingroup$ The problem of arbitrary alphabet can always be overcome by demanding that the alphabet be ordered. We can then refer to the first symbol, the second symbol, and so on. (This is an implementation of your isomorphism idea.) $\endgroup$ – Yuval Filmus Mar 4 '14 at 20:40
  • $\begingroup$ Regarding encoding, we need several properties: (1) completeness: all PDAs can be encoded (up to change of alphabet), (2) finiteness: encodings are finite (over a fixed alphabet), (3) encodings should allow effective reasoning, e.g., given the encoding of a PDA, we should be able to run it on a given input. $\endgroup$ – Yuval Filmus Mar 4 '14 at 20:42
5
$\begingroup$

Since you don't provide any attempt on your own part, note two things.

  1. The definition of countability.

    A set $A$ is countable if and only if $A$ is finite or there is a bijection $f : A \to \mathbb{N}$.

  2. How do you represent pushdown automata in a formal way?

If you digest the first item and answer the second, the answer should become apparent.

|cite|improve this answer|||||
$\endgroup$

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