If
then
Note that n and m in the above are unrelated; the string aabbaaabbb is in L 2 .
The reverse of L is easily described in set notation as
but it is considerably harder to describe or L* this way. A few tries will
quickly convince you of the limitation of set notation for the specification of
complicated languages.
Grammars
To study languages mathematically, we need a mechanism to describe them.
Everyday language is imprecise and ambiguous, so informal descriptions in
English are often inadequate. The set notation used in Examples 1.9 and 1.10 is
more suitable, but limited. As we proceed we will learn about several languagedefinition mechanisms that are useful in different circumstances. Here we
introduce a common and powerful one, the notion of a grammar.
A grammar for the English language tells us whether a particular sentence is
well-formed or not. A typical rule of English grammar is “a sentence can consist
of a noun phrase followed by a predicate.” More concisely we write this as
with the obvious interpretation. This is, of course, not enough to deal with actual
sentences. We must now provide definitions for the newly introduced constructs
(noun_phrase) and (predicate). If we do so by
then
Note that n and m in the above are unrelated; the string aabbaaabbb is in L 2 .
The reverse of L is easily described in set notation as
but it is considerably harder to describe or L* this way. A few tries will
quickly convince you of the limitation of set notation for the specification of
complicated languages.
Grammars
To study languages mathematically, we need a mechanism to describe them.
Everyday language is imprecise and ambiguous, so informal descriptions in
English are often inadequate. The set notation used in Examples 1.9 and 1.10 is
more suitable, but limited. As we proceed we will learn about several languagedefinition mechanisms that are useful in different circumstances. Here we
introduce a common and powerful one, the notion of a grammar.
A grammar for the English language tells us whether a particular sentence is
well-formed or not. A typical rule of English grammar is “a sentence can consist
of a noun phrase followed by a predicate.” More concisely we write this as
with the obvious interpretation. This is, of course, not enough to deal with actual
sentences. We must now provide definitions for the newly introduced constructs
(noun_phrase) and (predicate). If we do so by