Consider the grammar G1: S , S aS, S aSbS and the language L that contains exact
ID: 3845967 • Letter: C
Question
Consider the grammar G1: S , S aS, S aSbS and the language L that contains exactly those strings of a's and b's such that every prefix has at least as many a's as b's. We want to prove the claim: G1 generates all strings in L.
We take the following inductive hypothesis to prove the claim:
For n < k, G1 generates every string of length n in L.
To prove the inductive step
"For each string w in L either ____(a1) or ______(a2) holds. In both cases we use the inductive hypothesis and one of the rules to show that string w can be generated by the grammar. In the first case we use rule S aS and in the second case we use rule S aSbS."
Which phrases can replace the ____________ so that this argument is correct?
a) a1: each prefix has more a's than b's.
a2: there is a b in string w such that the part of the string until the b (b also included) has all prefixes with as many a's as b's and the part after b is such that each prefix has as many a's as b's.
b) a1: each prefix has equal number of a's and b's.
a2: there is a b in string w such that the part of the string until the b belongs in L by inductive hypothesis and the part after this b belongs in L by inductive hypothesis.
c) a1: each prefix has equal number of b's and a's.
a2: w can be written as w=aw'bw'' where for both w' and w'' it holds that each prefix has as many a's as b's.
d) a1: there is a b in string w such that for the part of the string until the b (b also included) each prefix has as many a's as b's and for the part after b each prefix has as many a's as b's.
a2: each prefix has more a's than b's.
I tried to slove this problem but, I couldn't do it. Would you plz explain me in detail? What is the answer?
Explanation / Answer
Language L that contains exactly those strings of a's and b's such that every prefix has at least as many a's as b's.
That means every prefix has number of a's are greater than or equal to b's.
here according to the given information and options
option A is correct.
In first case S->aS is useful.
with this we can only prove that each prefix has more a's than b's.
beacuse here before producing anything it will produce a.
definetly we will get more a's than b's.
And in the second case S->aSbS is useful
with this we can prove that there is a 'b' in string w such that the part of the string until the b (b also included) has all prefixes with as many a's as b's
the part after b is such that each prefix has as many a's as b's.
1)S->aSbS
2)S->
if we substistute 2nd production in 1st production it will reduced to ab.
reduction procedure
S->aSbS
S->abS
S->ab
like this we can generate all strings which have same number of a's and b's.
With first case and second case we can conclude that we can generate all the strings which will have prefixes with atleast as many a's as b's
because we have proved that we can generate strings which will have each prefix has more a's than b's and equal number of a's and b's.
Hence proved.
so optiion a is correct
correct answer is
a) a1: each prefix has more a's than b's.
a2: there is a b in string w such that the part of the string until the b (b also included) has all prefixes with as many a's as b's and the part after b is such that each prefix has as many a's as b's.