Give a CFG for the language A abnabn n 1 Please show step

Give a CFG for the language A = {(ab)ⁿ(ab)ⁿ | n 1 }. Please show steps, or explanations.

Solution

Given conditions are .. (ab)ⁿ(ab)ⁿ where n >= 1

So here is one condition is n should not less than zero. So we didn\'t have any epsilon condition.

Step 1: Let us start with condition n = 1

S -> A
A -> abA | ab

It satisfies.

Step2: Validate this CFG grammar whether it is supporting to n = 2
we can derive (abababab).. as follows

S -> A
S -> abA
S -> ababA
S -> abababA
S -> abababab

Hence this grammar is CFG for given above condition.

S -> A
A -> abA | ab