produces a string in which an occurrence of that left-hand side has been replaced with its right-hand side. Unlike a semi-Thue system, which is wholly defined by these rules, a grammar further distinguishes between two kinds of symbols: nonterminal and terminal symbols; each left-hand side must contain at least one nonterminal symbol. It also distinguishes a special nonterminal symbol, called the start symbol. The language generated by the grammar is defined to be the set of all strings without any nonterminal symbols that can be generated from the string consisting of a single start symbol by (possibly repeated) application of its rules in whatever way possible. If there are essentially different ways of generating the same single string, the grammar is said to be ambiguous. In the following examples, the terminal symbols are a and b, and the start symbol is S. Example 1 Suppose we have the following production rules: 1. 2. then we start with S, and can choose a rule to apply to it. If we choose rule 1, we obtain the string aSb. If we then choose rule 1 again, we replace S with aSb and obtain the string aaSbb. If we now choose rule 2, we replace S with ba and obtain the string , and are done. We can write this series of choices more briefly, using symbols: . The language of the grammar is the infinite set , where is repeated times (and in particular represents the number of times production rule 1 has been applied). This grammar is context-free (only single nonterminals appear as left-hand sides) and unambiguous. Examples 2 and 3 Suppose the rules are these instead: 1. 2. 3. This grammar is not context-free due to rule 3 and it is ambiguous due to the multiple ways in which rule 2 can be used to generate sequences of s. However, the language it generates is simply the set of all nonempty strings consisting of s and/or s. This is easy to see: to generate a from an , use rule 2 twice to generate , then rule 1 twice and rule 3 once to produce . This means we can generate arbitrary nonempty sequences of s and then replace each of them with or as we please. That same language can alternatively be generated by a context-free, nonambiguous grammar; for instance, the regular grammar with rules 1. 2. 3. 4.