Question

Let L be the set of exactly those strings over the alphabet \Sigma = {a, b, c, g}, that satisfy all of the following properties: the length of the string is equal to 5n+3, for some natural number n greater or equal than 0; all of the first (leftmost) 2n symbols are elements of the set {b, c, g}; all of the last (rightmost) 3n symbols are elements of the set {a, b}; the symbols at position 2n+1, 2n+2, and 2n+3 (from the left, i.e., after the first 2n symbols but before the last 3n symbols) are elements of the set {c, g}; Write a complete formal definition of a context free grammar that generates L. If such a context free grammar does not exist, state that the context free grammar does not exist, and prove it.

Answer 1

S -> LSR

S -> M

M -> YYY

Y -> c | g

L -> XX

X -> b | c | g

R -> ZZZ

Z -> a | b

Step-by-step explanation:

This is a long time ago, but I think this does what you want.

Start symbol S expands to LSR and allows you to grow L and R on either side as much as you want. Ultimately S must be replaced by M. Then you have a pattern like LLLLLMRRRRR.

We can then further break down L into 2 times b, c or g, and similar for M and R.