Pushdown automata and hierarchical state machines, at least in the context of game design, are both extensions of finite state machines. Neither contradicts the other, and so you can freely use both.
In hierarchical state machines, the substate/superstate relationship is one such that the substate is just a modified or extended version of the superstate. Lets say you have a superstate that is called RunningState that indicates your player is running. You can jump while running left if the A button is pressed, so one of your transitions is something like if (A_BUTTON_PRESSED) next_state = jump_state; However, you also want there to be an injured running state, for when the player has <50% health, that behaves like RunningState in every way except that a) you run slightly slower, and b) you cannot jump. So you create InjuredRunningState : public RunningState that has if (A_BUTTON_PRESSED) {next_state = NULL;} else { RunningState::transition(); } in its transition method.
You see that InjuredRunningState will behave in every way like RunningState except when the A button is pressed it will do nothing. This example I think encapsulates why you would use a hierarchical state machine. The downside to using a hierarchical state machine is that inheritance can make your code complex and difficult to read / manage relatively quickly. Change RunningState and your implicitly change every state that inherits from it, which may have entirely intended consequences or may not, if those substates were designed with some assumptions about how RunningState behaves.
Pushdown automata, on the other hand, are good because they maintain state history. In other words, a state, instead of being told to transition specifically into state X or state Y given conditions A or B, can be told to do something like "transition into the previous state" given some condition, where the previous state can be any state that transitions into this one. Say you want to be able to jump from standing and from crouching, and the jump animation and physics etc. are identical, but when you land you want to return to whatever state you were in before, be it standing or crouchihg. You could use a pushdown automata for this. Instead of transitioning to a JumpState, you push() a JumpState. When the JumpState is done, instead of transitioning into some explicitly named state, it simply pop()s, and the state underneath it, the state that pushed the JumpState, is returned to, be this StandingState or CrouchingState.
The downside of this is that you have to maintain a stack of states, and make sure that you pop() what you push().
Hopefully it is clear that you can have both at this point. You could have a StandingState and CrouchingState that transition into JumpingState, and then create InjuredStandingState or InjuredCrouchingState that inherit from their respective states (Hierarchical State Machine), while making sure any state that transitions into JumpingState does so by pushing it onto a state, and popping it when the jump is done (Pushdown Automata).
A final note: all the functionality described here could be achieved with regular finite state machines. For example, InjuredStandingState could just be its own completely independent state that repeats all the code of StandingState that it needs without inheriting from it. Similarly, instead of JumpingState you could have JumpingFromStandingState and JumpingFromCrouchState that, when done, transition back into the appropriate previous state. The problem here is repeat code and a rapidly expanding number of states, depending on the kind of behavior you want. It is up to you to decide if these extensions are even necessary. A regular finite state machine may be entirely sufficient for a very simple set of states and transitions.
