Section 12.1: Modeling Computation- Discrete Mathematics and Its Applications

Rosen, Discrete Mathematics and Its Applications, 6th edition
Extra Examples
Section 12.1—Modeling Computation

#1. Let G = (V, T, S,P) be a grammar where V = {S, A,B, a, b} is the vocabulary and T = {a, b} is the set of terminal elements. Determine whether the following set of productions is a:
(i) a type 0 grammar, but not a type 1 grammar.
(ii) a type 1 grammar, but not a type 2 grammar.
(iii) a type 2 grammar, but not a type 3 grammar.
S → ABA, A → bB, B → ba.

Solution:

It is a type 2 grammar because the left side of each production has a single nonterminal symbol. It is not a type 3 grammar because of the form of the right side of the third production.


p.790, icon at Example 8
#2. Let G = (V, T, S,P) be a grammar where V = {S, A,B, a, b} is the vocabulary and T = {a, b} is the set of terminal elements. Determine whether the following set of productions is a:

(i) a type 0 grammar, but not a type 1 grammar.
(ii) a type 1 grammar, but not a type 2 grammar.
(iii) a type 2 grammar, but not a type 3 grammar.
S → AB, B → bAa, bAa → a.

Solution:
It is automatically a type 0 grammar. It is not a type 1 grammar because the third production is not noncontracting.


p.793, icon at Example 13

#1.
(a) What is the Backus-Naur form of the grammar described as follows:

1. a sentence is made up of a noun phrase followed by a verb phrase or else by a noun phrase followed by a verb phrase followed by a noun phrase. 
2. A noun phrase is made up of a noun, an adjective followed by a noun, or an article followed by a noun.
3. A verb phrase is made up of a verb.
4. Articles are a and the.
5. Adjectives are lengthy, boring, and inaccurate.
6. Nouns are book, newspaper, and information.
7. Verbs are reads and contains.

(b) Explain how “the newspaper contains lengthy information” can be obtained.


Solution:
(a)

1. sentence ::= noun phrase verb phrase | noun phrase verb phrase noun phrase 
2. noun phrase ::= noun | article noun | adjective noun 
3. verb phrase ::= verb 
4. article ::= a | the
5. adjective ::= lengthy | boring | inaccurate
6. noun ::= newspaper | information
7. verb ::= reads | contains

(b) “the newspaper” is a noun phrase since it has the form article noun ; “contains” is a verb phrase since it has the form verb ; “lengthy information” is a noun phrase since it has the form adjective noun .
Therefore “the newspaper contains lengthy information” is a sentence since it has the form noun phrase verb phrase noun phrase