If L is a formal language and a is a symbol from Σ, their quotient L/a is defined as the set { w : wa ∈ L } of all strings that can be made members of L by appending an a.
The set Ldiv3 of all naturals divisible by 3 is an infinite formal language over Σ; it can be finitely described by the following regular grammar with start symbol S0: Examples for finite languages are {ε,1,2} and {0,2,4,6,8}; their product {ε,1,2}{0,2,4,6,8} yields the even numbers up to 28.
The quotient of the set of prime numbers up to 100 by the symbol 7, 4, and 2 yields the language {ε,1,3,4,6,9}, {}, and {ε}, respectively.
Greibach's theorem is independent of a particular approach to describe a formal language.
Then L = Σ* if and only if φ(L) ∈ P: Hence, if membership in P would be decidable for φ(L) from its description, so would be L’s equality to Σ* from its description, which contradicts the definition of C. [3] Using Greibach's theorem, it can be shown that the following problems are undecidable: See also Context-free grammar#Being in a lower or higher level of the Chomsky hierarchy.