and
equivalent? Assume that S is the start symbol in both cases.
22. Show that the grammar G =({S}, {a, b}, S, P), with productions
is equivalent to the grammar in Example 1.13.
23. Show that the grammars
and
are not equivalent.
1.3 Some Applications*
Although we stress the abstract and mathematical nature of formal languages
and automata, it turns out that these concepts have widespread applications in
computer science and are, in fact, a common theme that connects many specialty
areas. In this section, we present some simple examples to give the reader some
assurance that what we study here is not just a collection of abstractions, but is
something that helps us understand many important, real problems.
Formal languages and grammars are used widely in connection with
programming languages. In most of our programming, we work with a more or
less intuitive understanding of the language in which we write. Occasionally
though, when using an unfamiliar feature, we may need to refer to precise
descriptions such as the syntax diagrams found in most programming texts. If we
write a compiler, or if we wish to reason about the correctness of a program, a
precise description of the language is needed at almost every step. Among the
ways in which programming languages can be defined precisely, grammars are