CHAP. 12] LANGUAGES, AUTOMATA, GRAMMARS 319
Fig. 12-10(b) The leaves show thataandbmust be terminals, and the internal vertices show thatSandAmust be variables
withSthe starting variable. The children of each variable show thatS→AbS,A→aS,S→ba, andA→b
must be productions.12.27. Does a derivation tree exist for any wordwderived from the start symbolSin a grammarG?
No. Derivation trees only exist for Type 2 and 3 grammars, that is, for context-free and regular grammars.12.28. Determine the type of grammarGwhich consists of the following productions:
(a) S→aA, A→aAB, B→b, A→a
(b) S→aAB, AB→bB, B→b, A→aB
(c) S→aAB, AB→a, A→b, B→AB
(d) S→aB, B→bA, B→b, B→a, A→aB, A→a(a) Each production is of the formA→α; henceGis a context-free or Type 2 grammar.
(b) The length of the left side of each production does not exceed the length of the right side; henceGis a Type 1
grammar.
(c) The productionAB→ameansGis a Type 0 grammar.
(d) Gis a regular or Type 3 grammar since each production has the formA→aorA→aB.12.29. Rewrite each grammarGin Problem 12.28 in Backus-Naur form.
The Backus-Naur form only applies to context-free grammars (which includes regular grammars). Thus only (a)
and (d) can be written in Backus-Naur form. The form is obtained as follows:
(i) Replace→by ::=.
(ii) Enclose nonterminals in brackets〈〉.
(iii) All productions with the same left-hand side are combined in one statement with all the right-hand sides listed
on the right of ::=separated by vertical bars.
Accordingly:
(a)〈S〉::=a〈A〉, 〈A〉::=a〈A〉〈B〉|a, 〈B〉::=b
(b)〈S〉::=a〈B〉, 〈B〉::=b〈A〉|b|a, 〈A〉::=a〈B〉|aSupplementaryProblems
WORDS
12.30. Consider the wordsu=ab^2 a^3 andv=aba^2 b^2. Find: (a)uv; (b)vu; (c)u^2 ; (d)lu; (e)vlv.
12.31. For the wordsu=ab^2 a^3 andv=aba^2 b^2 , find:|u|,|v|,|uv|,|vu|, and|v^2 |.
12.32. Letw=abcde. (a) Find all subwords ofw. (b) Which of them are initial segments?
12.33. Supposeu=a 1 a 2 ···arand theakare distinct. Find the numbernof subwords ofu.