0
$\begingroup$

So considering that set of all turing machines is countably infinite, can we also say that set of all FA machines(DFA/NFA) or set of all PDA machines(DPDA/NPDA) are countably infinite, Considering that we can build all of them with Turing machine?

$\endgroup$
  • $\begingroup$ You are asking two very different questions. Since the one about languages was also posted separetely, I'm removing it here. $\endgroup$ – Raphael Sep 28 '17 at 14:29
  • $\begingroup$ Welcome to Stack Exchange! Please take a few minutes to read the tour and don't hesitate to visit our help center. Please ask one question at a time, and don't edit a question to add another question even if this other question is on a similar topic. If you have a new question, use the “Ask Question” button to create a new thread. $\endgroup$ – Gilles Sep 28 '17 at 18:10
2
$\begingroup$

The answer to your first question is yes, the sets of FAs and PDAs are countable. It's easy to see that since each such machine can be completely described by a finite encoding of its relevant information, like its states and its transition function.

For the second question, there are lots of languages (uncountably many, as the video shows), and almost all of them simply cannot be recognized by any FA. Any non-regular language will suffice as an example, like $\{0^n1^n\mid n\ge 0\}$. The same result holds for the languages recognized by PDAs: there are languages that aren't context-free, like $\{0^n1^n0^n\mid n\ge 0\}$.

$\endgroup$
2
$\begingroup$

The set of all finite automata is indeed countable, but that has nothing to do with the set of all TMs being countable. The two models are only related by the set of languages they accept, but both have infinitely many machines per language so we can't immediately conclude anything about the sets of machines.

You can prove countability with the usual means: working from the formal definition of FAs (something like $A = (Q, \Sigma, \delta, Q_F)$), construct an injection into $\mathbb{N}$. That's tedious, but elementary. For PDAs, it works just in the same way.

$\endgroup$
  • 1
    $\begingroup$ But cant we just prove it by saying since we can make any FA or PDA with turing machine and since set of all turing machines is countable therefore FA and PDAs are countable? $\endgroup$ – Richard Jones Sep 28 '17 at 15:00
  • $\begingroup$ @EdaiBossinShid What do you mean by "make with"? There are certainly other proofs. $\endgroup$ – Raphael Sep 28 '17 at 16:45
  • 1
    $\begingroup$ @EdaiBossinShid You'd need to formally define "make with". For example, define a "silly PDA" to be a pair $(x, M)$, where $x\in\mathbb{R}$ and $M$ is a PDA, and define $(x,M)$ to accept its input iff $M$ accepts that string. Now, there are uncountably many silly PDAs, even though every silly PDA is equivalent to (accepts the same language as) some Turing machine. $\endgroup$ – David Richerby Sep 29 '17 at 12:59
1
$\begingroup$

If you define finite automata as Turing machines with a single working tape that could be just read from left to right, and similar PDAs as Turing machines with an additional working tape that could be just used as a stack, then the countability of Turing machines gives you the countability of FAs and PDAs as they form subsets. But in general if you define these models independently, then you have to explicitly construct for each FA or PDA a corresponding TM, and this construction must be unique (i.e. an injection from the FAs or PDAs to TMs) to employ the fact that TMs are countable.

Let me add that the Turing definable languages are countable, but are not effectively countable, i.e. there is no Turing machine itself that enumerates them. This is a classic result related to the Halting problem. But in the case of finite automata (or PDAs) we can indeed effectively enumerate them. For the regular languages, just built a TM that enumerates finite automata for increasing size of states and alphabet (removing duplicates if you want to, as finite automata equivalence is decidable). Similar for PDAs, but in this effective enumeration their might be machines that describe the same language, and as context-free language equivalence is undecidable I do not see any way to get rid of them.

Hence in some sense we have a "stronger" notion of countability for regular or context-free languages then for general Turing definable languages.

$\endgroup$

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.