Grammar Definition
lThere is a Òstart
symbolÓ, or ÒrootÓ, say S, which is not in the
alphabet of the language itself.
l¨ is a symbol meaning Òcan be rewritten asÓ.
lGrammar rules, for
example:
1.S ¨ ab
2.S ¨ aSb
3.S ¨ SS
lApplication of rules
is by Òfree
choiceÓ.
lA sequence of
applications is called a derivation.
lThe strings in the
language are those that donÕt include S.