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!
$\begingroup$ $\endgroup$
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
6 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.
- $\begingroup$ So to answer the question in the title it is sufficient to provide a PDA for it? $\endgroup$Boris_s– Boris_s2017-11-26 22:13:00 +00:00Commented Nov 26, 2017 at 22:13
- $\begingroup$ @Boris_s yes it is sufficient. $\endgroup$fade2black– fade2black2017-11-26 22:14:36 +00:00Commented Nov 26, 2017 at 22:14
- $\begingroup$ 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)? $\endgroup$Boris_s– Boris_s2017-11-26 22:21:48 +00:00Commented Nov 26, 2017 at 22:21
- $\begingroup$ @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)$. $\endgroup$fade2black– fade2black2017-11-26 22:29:19 +00:00Commented Nov 26, 2017 at 22:29
- $\begingroup$ 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? $\endgroup$Boris_s– Boris_s2017-11-26 22:50:07 +00:00Commented Nov 26, 2017 at 22:50