2
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So to answer the question in the title it is sufficient to provide a PDA for it? $\endgroup$ – Boris_s Nov 26 '17 at 22:13
  • $\begingroup$ @Boris_s yes it is sufficient. $\endgroup$ – fade2black Nov 26 '17 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 Nov 26 '17 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 Nov 26 '17 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 Nov 26 '17 at 22:50

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.