Design a CFG for palindromes and test for the strings 0110.

The rules that define the palindrome expressed in the CFG notation are shown in figure –
P → ϵ
P → 0
P → 1
P → 0P0
P → 1P1
Figure: A CFG for palindrome
The grammar G_pal for the palindromes is represented by,
G_pal = ({P}, {0, 1}, A, P)
Where, A represents the set of five production that we seen in figure. The first three rules from the basis. They tell us that the class of palindromes include the string ∈, 0 and 1. Some of the right sides of these rules contains a variable which is why they form a basis for the definition. The last two rules from the inductive part of the definition. For instance, rules 4 says that if we take any strings ω from the class P. Rules 5 like-wise tells us that ⌈ω⌉ is also in P.
Test for string 0110.
P → 0P0
→ 01P10 [∵ P → | P |]
→ 01∈10 [∵ P → ∈]
→ 0110