Let L be the language of all strings of a\'s and b\'s such that no prefix (prope

Question

Let L be the language of all strings of a's and b's such that no prefix (proper or not) has more b's than a's. Let G be the grammar with productions

S aS | aSbS |

To prove that L = L(G), we need to show two things:

1. If S =>* w, then w is in L.

2. If w is in L, then S =>* w.

We shall consider only the proof of (1) here. The proof is an induction on n, the number of steps in the derivation S =>* w. Here is an outline of the proof, with reasons omitted. You need to supply the reasons.

Basis: 1) If n=1, then w is because _______.

2) w is in L because _______. Induction:

3) Either (a) S => aS =>n-1 w or (b) S => aSbS =>n-1 w because _______.

4a ) In case (a), w = ax, and S =>n-1 x because _______.

5a) In case (a), x is in L because _______.

6a) In case (a), w is in L because _______.

4b) In case (b), w can be written w = aybz, where S =>p y and S =>q z for some p and q less than n because _______.

5b) In case (b), y is in L because _______.

6b) In case (b), z is in L because _______.

7b) In case (b), w is in L because _______.

For which of the steps above the appropriate reason is contained in the following argument: "All n-step derivations of w produce either (for n=1) or use one of the productions with at least one nonterminal in the body (for n > 1). In case the production S aS is used, then w=ax with x being produced by a (n-1) -step derivation. In case the production S aSbS is used then w=aybz with y and z being produced by derivations with number of steps less than n."

a) 7b

b) 2

c) 5b

d) 4b

Could you answer me

How to slove step by step

Explanation / Answer

Answer is b) 2

Hint :-

2) w is in L because _______ All n-step derivations of w produce either (for n=1) or use one of the productions with at least one nonterminal in the body (for n > 1). In case the production S aS is used, then w=ax with x being produced by a (n-1) -step derivation. In case the production S aSbS is used then w=aybz with y and z being produced by derivations with number of steps less than n_______

This is the the appropriate reason for step 2.

Step 4b, 5b and 7b are not asking for production.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.