#ACE test series

Question

The minimum number of productions required to produce a language consisting of palindrome strings over ∑={a,b} with a single variable is______.

Answer 1

Answer: 5

S→ aSa | bSb | a | b | epsilon 

---

1^st production S→ aSa

2^nd  production S→ bSb 

3^rd  production S→ a 

4^th  production S→ b

5^th  production S→ epsilon

Palindrome strings = odd length palindrome( production 1,2,3,4) + even length palindrome (production 1,2,5).

Here single variable is ‘S’ which is start symbol.