# Show that 0^n1^n is decidable

I would like to know how would one go about and answer this question. I know that a language is decidable if a turing machine exists that accepts the strings in that language, and rejects otherwise. Would I need to create a turing machine to show this or is it enough to create a PDA and claim a TM can be created from a PDA such that it accepts and halts all strings in it and rejects otherwise. Also, if anyone can refer a good post to learn how to create a PDA from CFL would be greatly appreciated. Thanks!

## 1 Answer

If a language decidable by a PDA then it is also decidable by a TM. In other words TM are more computationally powerful than PDA, i.e., the class of languages decidable by PDA is a proper subclass of the class of languages decidable by TM. You can also easily simulate a PDA on a TM.

However not all languages are decidable by PDA. So your approach does not work in general.

As to CFG to PDA conversion I would recommend the textbook by Sipser (pg 116). Google search for "CFG to PDA" also gives a good result.

• So to answer the question in the title it is sufficient to provide a PDA for it? – Boris_s Nov 26 '17 at 22:13
• @Boris_s yes it is sufficient. – fade2black Nov 26 '17 at 22:14
• Thanks! One last thing, do you know how to determine the computational complexity of the CFG in the title? would it be linear or O(n)? – Boris_s Nov 26 '17 at 22:21
• @Boris_s What do you mean by "computatonal complexity of CFG"? There is a simple $O(n^3)$ algorithm deciding if a string of length $n$ belongs to $L(G)$. – fade2black Nov 26 '17 at 22:29
• I did not mean of CFG in general, I meant for the example provided in the title. I just read in Wiki that "The complexity of an algorithm is often expressed using big O notation." So for an algorithm which increases linearly with its input the complexity would be O(n) right? – Boris_s Nov 26 '17 at 22:50