What is the difference between pCFGs and HMMs? • /r/MachineLearning

As other people pointed out, PCFGs can express all probabilistic pushdown automata, while HMMs can express all probabilistic finite state automata. So there are things which PCFGs can model (like recursion) which HMMs can't. On the other hand it's pretty difficult to induce PCFGs from data with EM, as the latent variable space is really huge, while for HMMs this is easy. You can think of a PCFG as a hierarchical HMM in the following way. To generate observations from an HMM you start from the initial state and use the transition probabilities to sample the next state, and then use the state's emission probability to sample a symbol, until the next state sampled is the end of sequence state.