Give a CFG for the language A abnabn n 1 SolutionFollowing

Give a CFG for the language A = {(ab)n(ab)n | n 1 }

Solution

Following is CFG for the language A = {(ab)ⁿ(ab)ⁿ | n 1 }

A can be simplified to

=> {(ab)²ⁿ | n 1 }

=> {(abab)ⁿ | n 1 }

S -> ababS | abab

It means one or more abab.