Consider the following decision problems:
(P1): Does a given finite state machine accept a given string?
(P2): Does a given context free grammar generate an infinite number of strings?
Which of the following statements is true?
For P1, we just need to give a run on the machine. Finite state machines always halts unlike TM.
For P2, check if the CFG generates any string of length between $n$ and $2n-1$, where $n$ is the pumping lemma constant. If so, L(CFG) is infinite, else finite. Finding the pumping lemma constant is not trivial - but there are other procedures which can do this - http://cs.stackexchange.com/questions/52507/is-it-decidable-whether-a-given-context-free-grammar-generates-an-infinite-numbe/52520
Hence, both P1 and P2 are decidable - (A).
I didn't receive any emails, sir. I would like ...
Sahi baat h....