[Solved]: Why are pushdown automata countable?

Problem Detail: 

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.

Asked By : navlag

Answered By : babou

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22255

 Ask a Question

 Download Related Notes/Documents