Question

The following Context-Free Grammar (CFG):
S $\to$ aB | bA
A $\to$ a | aS | bAA
B $\to$ b | bS | aBB
may generates(s)

• A. Different numbers of a's and b's.
• B. At least one odd numbers of a's and odd numbers of b's
• C. Equal numbers of a's and b's
• D. Even numbers of a's and even number of b's

Answer 1

Answer: (B), (C), (D)

Even numbers of a's and even number of b's

Option (a,b,c)
The following Context-Free Grammar (CFG):
S $\to$ aB | bA
A $\to$ a | aS | bAA
B $\to$ b | bS | aBB
will generate

• Odd numbers of a's and odd numbers of b's i.e. al
• Even numbers of a's and even numbers of b's i.e. e
• Equal numbrs of a's' and b's i.e. ab, ba, bbaa or aal
• It will not generate different numbers of a's and b'