It is okay to have explicit transitional animations. The idle animation and the walk animations have no motion phases in common, so blending as a whole (i.e. separate blending of single body parts isn't available) could introduce irregularities. Maybe one can live with them because they are short in time or mostly not visible by some other reason.

An explicit transitional animation would get its own state if modeled in an animation state machine. That state will be left after the transitional animation has completed, either controlled by elapsed time or (perhaps better) controlled by a trigger event fired from a respective track of the animation.

I think the main idea behind state machines is that you generally are only in one state, otherwise you'd need something above it again to control which state(s) you're in

The term "state machine" is generic for a couple of things. You're right w.r.t. a simple state machine. But there are other incarnations, too. For example, in a hierarchical state machine (HSM) one has concurrency, so that several states can be active in parallel. However, I've not seen a HSM in use for animation as discussed in this thread.

My posts (and I assume the OP) are about 3D animation not 2D. I guess the original post doesn't say one or the other. In 3D if you just play the animation without blend it'll look bad and jerky, unless you have specific transition animations, which can be wasteful/costly/time consuming to make all transition animations. So in 3D, when you go from idle to walk, you want to play both animations on top of each other, but you have a blend value ranging from 0 to 1. Before you walk you are only playing the idle animation with a blend value of 1 (fully blended in). Then you press a key to move forward and you now play the idle and walk animation but you start reducing the blend value of the idle animation from 1 to 0 and the walk blend value from 0 to 1. This creates a very smooth transition between the 2 animations and doesn't require any special transition animations to exist.

I think perhaps I didn't explain myself too well. I'm talking about the level above the animation blending. I see the configuration of [3d] animation as hierarchical. At the lowest level you have animation clips. Above that you have clips which are blended/layered together (with the 0-1 factor you mentioned) and above that, a state machine to handle everything from an action perspective.

So for example, lets say we have these player states:

Idle
Walk
Shoot
Die

In a very simple system, you may have an animation system which doesn't do any blending and just runs each animation depending on which button is pressed. This obviously wouldn't look too realistic.

You then may have a system where you decide to incorporate a simple blend between each state. This would look more realistic but isn't very scalable for more complex movements.

The you can have a more generic and scalable system and do both animation tree blending and blending between states. So you could have a situation where you have the animation clips that when blended together give you a state. For example, imagine an animation where the player has hurt his leg and is limping. This works well for the normal player but you might have a zombie style walk and if you blend the hurt leg walk with the zombie walk, you get a zombie with a dead leg! This would constitute a walking state still.

So you can combine all these different animations to make different, organic and interesting motions but they are still states in themselves. Eg zombie walk, zombie injured walk, normal walk, normal injured walk, etc.

Above this level is the state manager. So you can easily apply the following states in some script:

Zombie_idle
Zombie_walk
Zombie_shot_in_leg
Zombie_idle_anguish
Zombie_walk_with_limp

The anguish the zombie is experiencing could come from a generic anguish animation but when combined with the zombie idle, it adds a unique flavour.

So in order for these states to look organic and realistic, you would also need to blend between the states themselves so you can see we've got two levels of blending going on. The animation state machine transitions would store default and overridable blend factors for cross-fading/immediate switching, etc.

You could get more complex if you like by blending even more base animations and/or using difference animations for a really organic feel, with such a configurable system, the possibilities multiply exponentially.

I think my original question has been answered by pretty much all of us really, myself included. It was more about what type of animation should be considered as a state. Like walking is a repeating animation and a continual state (as long as you keep doing it obviously), but going from idle to walking is not, it's a one shot thing. I just wanted to clarify that this particular in-between 'motion' should be classed as a state - and I think the answer is yes.

Edit: and as I just saw, confirmed by Haegarr ;-)