to
Chapter 7: Pushdown Automata l;! 265
6. The intersection of a context-free language and a regular language is
(a) context-free
(b) regular but not context-free
(c) neither context-free nor regular.
(d) both regular and context-free.
Fill up the blanks:
7. In bottom-up parsing. we build the deviation from
8. In LR(l) grammar. we can decide the production to be applied in the
next step by _._ .._.
9. W E T(A). where A is a pda if (qo. w. Zo) ~
10. 11' E N(A). where A is a pda if (%. w. 2 0 ) ~
EXERCISES
7.1 If an initial ill of the pda A in Example 7.2 is (qo. aaeaa. 2 0 ). what
is the ill after the processing of aacaa? If the input string is (i) abeba.
(ii) abeb. (iii) acba. (iv) abac. (v) abab. will A process the entire
string? If so. what \vill be the final ill?
7.2 What is the ill that the pda A given in Example 7.5 reaches after
processing (i) a 3 b:. (ii) a:b 3 . (iii) as. (iv) b 5 . (v) b 3 a:. (vi) ababab if
A starts with the initial ill?
7.3 Construct a pda accepting by empty store each of the following
languages.
(a) {a"blllalli m. 11 :2: I}
(b) {allb:" I11 :2: I}
(c) {allb
lJl e" ITn. 11 2: I}
(d) {a'llb ll 1m > 11 :2: I}
7.4 Construct a pda accepting by final state each of the languages given in
Exercise 7.3.
7.5 Construct a context-free grammar generating each of the following
languages. and hence a pda accepting each of them by empty store.
(a) {a" b ll In :2: I} u {a'll b:
m
1m :2: I}
(b) {d 'b'''all 1m. n :2: l} u {aile" In :2: I}
(c) {a"Ylle lll d" 1m. n :2: l}
7.6 Let L = {d"b!! In < m}. Construct (i) a context-free grammar accepting
L (ii) a pda accepting L by empty store. and (iii) a pda accepting L
by final state.