Students seem to be unable to use code to express their ideas. Is the teaching methodology improvable? In my beginner experience as a teacher, the thing that's strucking me most is a sensation of my students' inability to express their (valid!) thoughts in code. Let me deepen it a bit.

I inherited a last year class that was supposed to know C from their previous years. Anyway they struggled in manually tracing the execution of the code they see, being it mine or theirs.
After some work I could test and evaluate them again and it now seems to me that they are actually quite good at reasoning about a sort of "abstract idea" of what they want their algorithms to do: they can use our natural language to say things like scan this, sum that, stop here or there, and they are pretty much correct. What they seem to have big difficulties in is saying the same thing using a formal language.

They moreover have this (to me, crazy) habit of writing huge blocks in main() without splitting anything, and even worse the only way they think about of producing output is writing to the world: they don't contemplate returning from a function. One (brilliant!) boy once asked me with big amazement after my seemingly strong assertion: "oh, so you mean that strlen() is a function?".
Of course I may understand where this comes from, but I suspect it's not healthy for their learning.

It seems to me that a possible reason of this observed behaviour might lie in having taught them to build huge state machines without making them have a clue that they are building huge state machines: they can reproduce some they have already seen but are really lost when needing to make a new one. Even having them apply small modifications seems to me more like a blind trial from their part than some reasoning about the meanings. The building blocks of the language do not play well together in their minds or they are just unable to think about the state transitions in the code.

If I have to push myself a bit more I can say that I suspect all this is a reflection of the non composability of state machines, making their use in teaching to absolute novices not effective, whereas functions are known to be composable and would presumably lead to better results, in terms of being a means for mapping an individual's thoughts to formal language.

Is my analysis plausible? Have you experienced anything similar? Is there any available scientific literature on these phenomena? How would you test them to investigate deeper their difficulties and how would you try to show them a more effective route? Is there anything you would do to improve the methodology for next classes?

Should state machines be introduced somehow more explicitly, with better examples, showing how do they actually solve problems before throwing them to the poor students with a burden of syntax that they know nothing about? They even told me clearly that syntax is the only thing they focused all their energies on in their previous years.

What I am doing in younger classes is proposing functions first (as in functional paradigm), to solidify the concept of building a small composable block that has input and output, waiting a bit more in the future to introduce state transitions using the classic drawing turtle of fame with the hope that its visual feedback might make things tangible.
There is a lot to unpack here, but first, YES, the teaching methodology can be improved, but that is always true, an unending quest. 

Next, I'll note that C is a language with enough pitfalls that many people struggle with it at the detail level, finding it harder to think more globally. My preference, perhaps not open to you, is to start with a language at a higher level of abstraction generally and then, later in the curriculum, work both downward toward the machine and upward from where you start. An OO or pure functional language, if well taught, makes abstraction easier. 

However, the biggest recommendation I'd make to address the problems you state is to introduce (at the beginning) unit testing and test driven development (TDD). Find a good testing environment for your language and insist on its use: No Code Without a Failing Test. 

I normally start out a course with TDD, combined with giving assignments in an already logically decomposed way. Instead of a large program to write (large is relative, of course), I give them the "top down" decomposition initially that, in C they would be able to implement by writing a lot of functions. 

Thus, at the beginning, I relieve them of having to face a blank screen with a large problem and nothing but 'main()' to work with. Later you can continue this, but making the pieces bigger, requiring some decomposition (helper functions) be developed. My mantra for a "too big function" is about five lines. My mantra for "too complex function" is nesting more than two levels. You can break these rules for especially boring code, but not for the interesting logic of a program, or it will be impossible to understand and maintain. 

Note that breaking a problem up into parts is how Agile Development (Extreme Programming, Scrum, ...) actually work, with the Customer (in this case you) giving the Team (your students) manageable problems each of which contributes value. 

Also, with TDD, you can provide some tests initially along with simple requirements. Teach them to stop programming when the tests pass. Or, write additional tests and make them pass. But the tests are small and simple, usually without internal logic, and the application code needed to make them pass should also be simple function and uses of functions.