# Can a formal language always be generated by a formal grammar?

1. A formal language is often defined by means of a formal grammar. I wonder for a formal language if there is always a formal grammar that generates the language?
2. Does this answer have something to do with "it is not possible to design a recognizer(automaton) for certain formal languages"?

Thanks and regards!

Added: The definition I know for formal grammar is http://en.wikipedia.org/wiki/Formal_grammar#Formal_definition . Are there different definitions?

-

In the most general definition, a formal language is simply an arbitrary set of strings over a particular alphabet. Assuming the alphabet is nonempty, that means there will be infinitely many strings and thus uncountably many sets of strings. There are only countably many formal grammars, so many sets of strings (formal languages) are not definable by formal grammars.

Sometimes authors back away from the most general definition and require that the alphabet has to be countable or finite and the language has to be at least computably enumerable. In that case, you have to have a more specific definition of what a "formal grammar" is to make the question precise. Every c.e. language is generated by an "unrestricted grammar" in the sense of the Chomsky hierarchy, and every language generated by any grammar is c.e., so those classes of languages coincide. But, for example, not every c.e. language is a regular language in the sense of the Chomsky hierarchy.

-
Thanks! The definition I know is en.wikipedia.org/wiki/Formal_grammar#Formal_definition . What are the different definitions? –  Tim Jul 11 '11 at 18:20
Is the relation between a formal language and a formal grammar similar to the relation between a formal language and an automaton, as asked in my Part 2? –  Tim Jul 11 '11 at 18:32
@Tim: The Chomsky hierarchy gives a level-by-level correspondence between certain types of automatons and certain types of formal grammars. The most general definition of a formal grammar is an "unrestricted" grammar; the automaton for these is a Turing machine and the corresponding class of languages is the class of c.e. languages. Look up the article on the Chomsky hierarchy in Wikipedia for more info. –  Carl Mummert Jul 11 '11 at 18:35

No. If you mean what I think you mean by "formal grammar," then there are only countably many formal grammars but uncountably many formal languages. Similarly, there are only countably many Turing machines, so most formal languages cannot be recognized by any Turing machine.

(This is perhaps the simplest proof that there exist undecidable problems. Of course, the Halting theorem provides both a vivid and important explicit example of such a problem.)

-
Thanks! The definition I know is en.wikipedia.org/wiki/Formal_grammar#Formal_definition . Are there different definitions? –  Tim Jul 11 '11 at 18:18
@Tim: one could, in principle, remove any of the words "finite" in that definition if one wished (or replace them with "recursively enumerable," etc.). –  Qiaochu Yuan Jul 11 '11 at 18:25
(1) what's the definition used in your post then? (2) Is this similar to the relation between a formal language and an automaton, asked in my Part 2? –  Tim Jul 11 '11 at 18:30
@Tim: I'm using the definition in the Wikipedia article. –  Qiaochu Yuan Jul 11 '11 at 18:33
Wouldn't the fact that there are countably many formal grammars, and uncountably many languages, mean that you end up with many more languages than grammars, so there will always be a language available to be generated by the grammar? –  corsiKa Jul 11 '11 at 21:57