Question

The minimum number of productions required to produce a language consisting of palindrome strings over \(\Sigma=\{a,b\}\) is

• A. 3
• B. 7
• C. 5
• D. 6

Hint:

Standard palindrome CFG: \[ S\rightarrow aSa\;|\;bSb\;|\;a\;|\;b\;|\;\epsilon \] contains exactly five productions.

Answer 1

The Correct Option is C

Concept: A palindrome reads the same from left to right and right to left. A CFG generating palindromes over \(\{a,b\}\) is: \[ S\rightarrow aSa \] \[ S\rightarrow bSb \] \[ S\rightarrow a \] \[ S\rightarrow b \] \[ S\rightarrow \epsilon \]

Step 1: Count the productions.
There are \[ 5 \] productions.

Step 2: Verify completeness.
The productions generate: \[ a,\;b,\;aa,\;bb,\;aba,\;abba,\ldots \] which are all palindromes.

Step 3: Write the answer.
Hence the minimum number of productions is \[ \boxed{5}. \]