Give a contextfree grammar to generate the language of binar

Give a context-free grammar to generate the language of binary strings whose third rightmost symbol is a 1.

Solution

As the third most symbol should be 1, first 2 symbols can be of any form, i.e. only binary (00,11,01,10) and after 3rd symbol 1 it can be 1 or 0 or . so grammer is

S->A1B

A->00|01|10|11

B->0|1|