Consider the grammar with start symbol S and terminals a, b, with the rules: S a
ID: 3810368 • Letter: C
Question
Consider the grammar with start symbol S and terminals a, b, with the rules: S aSb | SS | .
Choose all the correct statements about an arbitrary string in the language generated by this grammar.
The options refer to the following definitions:
A prefix of a string is any string for which there is a string such that =. Similarly, a suffix of a string is any string for which there is a string such that =. For instance, for a string =xyxyz, xyx is a prefix and xyz is a suffix (but not vice versa).
Choose one or more:
a. In any suffix of the string, number of a's number of b's
b. If the string is split into two equal parts, in each part, number of a's = number of b's
c. number of a's = number of b's
d. In any prefix of the string, number of a's number of b's
e. The string starts with an a
f. In any prefix of the string, number of a's = number of b's
Explanation / Answer
a.true
cosider s=aSb->aSSb->aaSbaSbb->aababb,the suffix abb a<b true
b.false
consider above example ,after splittig the sub strings are aab,abb o of a's not equal to no of b's
c.true
consider aSb->aaSbb->aabb,this and above string example proves
no of a's =no of b's
d.true
simple direct keeping s->null,we get s->ab,a>=b;
keeping S->aSb.we get aabb,prefix is aa,a's>b's count and consider aababb,her prefix aab a's>b's
e.false
.As the grammar is S->aSb|null,we can also have a null string.
f.false
consider :
aababb,her prefix is aab a's>b's