Write a grammar for the language consisting of strings that always alternate letters a and b.

Question

Write a grammar for the language consisting of strings that always alternate letters a and b.



For example, the strings abab, abababab, and abababababab are in the language but a, aaabb, ba, and abb are not.

Group of answer choices

S -> abS | ab 

S -> aSb | ab

S -> ab

S -> aSbb | abb

S -> aSbb | a | bb

Answer 1

Let's assign these numbers and walk through eliminating the wrong answers:

1. S -> abS | ab 
2. S -> aSb | ab
3. S -> ab
4. S -> aSbb | abb
5. S -> aSbb | a | bb

3 is out right away. The only string in this language is just "ab". Notice there's no recursion to the definition -- no usage of S on the right side as well as the left side. So although "ab" contains alternating a's and b's, we don't have any other strings of alternating a's and b's in the language specified by 3 (which means it doesn't meet the requirement).

4 is out right away, too. On the right of that | (signifying "or"), we see abb. So that means abb is in 4's language, and abb does not consist of alternating a's and b's, as required.

5 is out right away as well. On the right of the last | is bb. That's not alternating a's and b's. Neither is that middle term on the right -- a.

So we're down to 2 or 1.

Let's look at 2. We see that ab is in the language. That's okay -- it's made up of alternating a's and b's. Now let's make use of that fact with the left side of that |. We can substitute in for the S in aSb that ab we just generated. That gives us aabb (I bolded the substitution). Well, that's not in the language they want defined, because it's not alternating a's and b's. So it's out.

So hopefully, 1 does specify alternating a's and b's, since it's our last one. To the right of the | is ab. That meets the requirements. Let's substitute it in the S position for the term on the right of that |, abS. I'll bold the substitution: abab. Oh, that's fine! We have alternating a's and b's. Let's try another substitution into abS, using our new string: ababab. It's good! In fact, it's easy to see that we'll keep prepending an ab onto any other generated string, and the result will be fine: if what we append to is already alternating a's and b's, prepending an alternating ab will result in a longer string of alternating a's and b's. So we get no counterexamples, for sure. We could also try to prove that we get all of the alternating ab strings. I won't get formal here, but it's pretty obvious we do (if you rule out the empty string).

So 1 it is. What might have been confusing here is that this is what's called a recursive definition: we have one string in the definition that does not refer back to S -- that's our base case; then we have another piece of our definition which refers back to S -- that's how we build up new strings from previous strings.