-
Consider the following context-free grammars:
G1 : S → aS | B, B → b | bB
G2 : S → aA | bB, A → aA | B | ε , B → bB | ε
Which one of the following pairs of languages is generated by G1 and G2, respectively?
-
- { am bn | m > 0 or n > 0 } and { am bn | m > 0 and n > 0 }
- { am bn | m > 0 and n > 0 } and { am bn | m > 0 or n ≥ 0 }
- { am bn | m ≥ 0 or n > 0 } and { am bn | m > 0 and n > 0 }
- { am bn | m ≥ 0 and n > 0 } and { am bn | m > 0 or n > 0 }
- { am bn | m > 0 or n > 0 } and { am bn | m > 0 and n > 0 }
Correct Option: D
In G1, there will be atleast 1 b because S->B and B->b. But no. of A's can be 0 as well and no. of A and B are independent. In G2, either we can take S->aA or S- >bB. So it must have atleast 1 a or 1 b. So option (d) is correct.
