Question

Show that L= {a^nb^n | n>= 0, n is not a multiple of 5} is context free.

Answer 1

The language is a context free.

L= {a^nb^n | n>= 0, n is not a multiple of 5}

= {aⁿbⁿ, n!=3p where p is an integer}

The strings correspond to the above language L = { $\epsilon$ ,ab,aabb,aaabbb,aaaabbbb,aaaaaabbbbbb................}

Since the language is context free grammar we can write the CFG where the CFG must satisfy all valid strings of the language.

Context Free Grammar:

S -> aAb | aaAbb | aaaAbbb | aaaaAbbbb | ε

A ---> aaaaaAbbbbb | ε

Where

If A is epsilon it derive n = 1,2,3 and 4 are true otherwise  5p+1 or 5p+2 or 5p+3 or 5p+4 where p is any integer. If n=0 it derive S -> ε

A ---> aaaaaAbbbbb | ε

It derve ε or multiples of 5 a's and b's.

Hence proved