Problem Solving in Automata, Languages, and Complexity

3.3 Parsing and Ambiguity 109

4.

(b) {aibjc”de 1 i + k 5 j + e+ 3).

* (c) {dbjc”d~ 1 i + 2k = j + 3&}.

* (d) {aitickde 1 i + 2k # j + 3&).

* (e) {u%kkde 1 i + 2l = j + 3k).

* (f) {uibjckde 1 i + 2t # j + 3k).

k> {bi#b?+, I bi is the binary representation of integer i, i > - 0).

Construct a context-free

over alphabet {a, b}.

grammar to generate all regular expressions

5. For each of the following languages, construct a context-free grammar
   for it-

( a >

0

0 C

(4

( e 1

0

* k>

* Ch)

(zR#y I X, y E (0, l}*, z is a substring of y).

(z”#Y I T Y E {o, q*, x is a subsequence of y}. (A string x =

x1x2 l l l xk is a subsequence of a string y = yly2. l. yn , where each

xi and each yj is a single letter, if there exist 1 5 j, < j2 < l l l <

jk < n such that yje = xl for 1 < e < k )

{umbyIyE(ufb)n-‘,n>m~l).- l

{amby I y E (u+b)n--l,n-x > n 2 1).

{x1#x2#--#xn 1 xl,.. .,xn E (0, l}‘, (31 5 i < j 5 n)

[ X:i = xj”l}.

{xl#x2#-•#x, 1 xl,...,xn E {O,l}*, (31 5 i < j 5 n)

lIxi # xjll-

{o,1}* - {zowzu 120 E {0,1}“}.

L= (0 + 1>* - { (O”T)n I n 2 l}. [Hint: The language

U m+ Om ( l+O+)n l+ is context-free.]

3.3 Parsing and Ambiguity

In Section 3.1, we defined that a string x is in L(G) for some context-free

grammar G = (V, C, R, S) if and only if there is a derivation 5’ 5 x in G.
Such a derivation demonstrates the step-by-step applications of the rules to
generate x from the starting symbol S. We can also display a derivation by
a tree, called a, purse tree, or a derivation tree. For instance, consider the
context-free grammar Gr = ({S}, {a, b, c}, R, S), with

R = {S + SbS 1 ScS I a},

and the string ubucu E L(G1). The derivation

S + SbS 3 SbScS =P ubScS + ubScu a ubucu

can be represented by the tree of Figure 3.4(a), and the derivation

S =+ ScS * SbScS a ubScS 3 ubScu 3 ubucu