There are several meanings for the word “sentence”. The online Merriam-Webster describes “sentence” as “a group of words that expresses a statement, question, command, or wish”, without restricting its grammatical form. But it also describes “sentence fragment” as “a group of words that is written out as a sentence but that lacks a subject or verb” (as the short version of the definition), thereby implying that a sentence proper has both a subject and a verb (predicate).
In a more grammatical approach, it is the presence of a predicate that makes a sentence. Many languages allow the omission of a subject, since the agent is expressed by the inflected form of the predicate. Even though this might be described so that the subject is present, but implicit, there are also many languages where sentences with no subject are normal, e.g. sentences corresponding to “It is raining” do not require a formal subject.
It is still a matter of definition what you call a sentence. And it is anyway a fact that people frequently use expressions that are not sentences in the grammatical meaning mentioned above (i.e. lack a predicate), yet serve the function of such a sentence. They are very common in short notices, news headings, etc. Usually the predicate can easily be inferred, as regards to the meaning, though we might have different ideas of the exact wording. But the point is that such wording does not matter.
“System shutdown in 60 seconds” can be read as “System shutdown will take place in 60 seconds” or in a few other ways, but the meaning is the same. Omission of the predicate probably makes communication more efficient here: the message is shorter and can thus be read and grasped faster.
However, such expressions are not accepted in normal flow of written nonfiction prose, or in “formal prose” as some people might say. The reason is that such forms of language have been developed to have a certain structure, including “complete sentences”, i.e. sentences in the grammatical sense. This makes them more readable, since this is the form we are used to expect. When you use sentence fragments, you break the normal flow. This may be an important technique in narrative text and even in nonfiction prose at times. But when used just because you don’t care to formulate your messages as normal prose, it makes the impression of… lack of care.
This is why Microsoft Office Word shows an error message in Spelling & Grammar checks, if you try to use such expressions. This can be changed by editing the settings. The way to do this depends on Word version, but the setting in Proofing options is “Fragments and Run-ons”. Even if this setting is checked (as it normally should), Word accepts fragments in many contexts. For example, if you write “Hello world” as a heading, or as paragraph of its own, it will pass. We can say that Word expects it to be a title or something like that and checks just the spelling, not the grammar. But if you end with a period, Word interprets that it is meant to be a sentence and says: “Fragment (consider revising)”.
You might like to know about Context Free Phrase Structure Grammar (CFPSG), which is similar to the approach you're taking, but it allows for intermediate categories, like NP. I'll give an example reformulation for your example:
S -> NP VP
NP -> D N
VP -> V AJ P CNP
D -> an
N -> apple
V -> is
AJ -> red
P -> in
CNP -> color
If there is a way to derive a phrase by starting with S and using rules to make substitutions, then the phrase is said to be generated by the grammar. A set of phrases all of which are generated by such a grammar is said to be a language generated by the grammar.
An advantage of having such intermediate categories as NP available, is that once you have described the fact that "apple" is not a good NP in subject position, it will follow that it is also not good in other sentence positions. *"I'd like apple".
CFPSGs have had much use in grammar and in computer science. The classic Unix tool yacc, "Yet Another Compiler Compiler", is based on CFPSG, for instance, and the languages generated by CFPSGs are those recognized by the push down store automata.
Best Answer
To find the main verb in an English sentence, first find all the Verb Phrases. Each one defines a clause, because only clauses have Verb Phrases.
The main Verb Phrase of the whole Sentence is the Verb Phrase that all the other clauses modify; this makes the clause containing it the Main Clause. So the main verb in the Main Clause in a sentence is the main verb of that sentence.
In each Verb Phrase, the main verb is the last verb; all the other verbs in that Verb Phrase can be ignored. The rule is then that the last verb in the Verb Phrase of the main Clause is the main verb of the sentence.
In the sentences presented,
In (1), is allowed and to change himself back are the verb phrases, and since the second one is the object of the first, that makes the first one the main verb phrase, and the main verb in it is is. (The real predicate in this sentence is actually allowed, but that's a predicate adjective, not a verb.)
In (2) want and to go to school are the VPs, and the second modifies the first again, so the main verb is want.
In (3) needs and to stop, same story. Main verb, needs.