Generate context free grammar for the following language

3
votes
**{a^i b^j c^k d^m | i+j=k+m | i<m}**

The grammar should allow the language in order abbccd not cbbcda. First should be the a's then b's and so on.

I know that you must "count" the number of a's and b's you are adding to make sure there are an equivalent number of c's and d's. I just can't seem to figure out how to make sure there are more c's than a's in the language. I appreciate any help anyone can give. I've been working on this for many hours now.

Edit:

The grammar should be Context Free

I have only got these two currently because all others turned out to be very wrong:

S -> C A D | B

B -> C B D |

C -> a | b

D -> c | d

and

S -> a S d | A

A -> b A c |

(which is close but doesn't satisfy the i < k part)

2
grammar
What kind of grammar do you want? You say you've been working on it, what exactly have you tried? Please add these things to your question. – Jon Egeland
I'm not convinced that the language is context-free. Are you sure that the desired inequality was i<k and not j<k? – rici

2 Answers

2
votes

EDIT: This is for when i < k, not i < m. OP changed the problem, but I figure this answer may still be useful.

This is not a context free grammar, and this can be proven with the pumping lemma which states that if the grammar is context free, there exists an integer p > 0, such that all strings in the language of length >= p can be split into a substring uvwxy, where len(vx) >= 1, len(vwx) <= p, and uvnwxny is a member of the language for all n >= 0.

Suppose that a value of p exists. We can create a string such that:

k = i + 1
j = m + 1
j > p
k > p

v and x cannot contain more than one type of character or be both on the left side or both on the right side, because then raising them to powers would break the grammar immediately. They cannot be the same character as each other, because then multiplying them would break the rule that i + j = k + m. v cannot be a if x is d, because then w contains the bs and cs, which makes len(vwx) > p. By the same reasoning, v cannot be as if x is cs, and v cannot be bs if x is ds. The only remaining option is bs and cs, but setting n to 0 would make i >= k and j >= m, breaking the grammar.

Therefore, it is not a context free grammar.

1
votes

There has to be at least one d because i < m, so there has to be a b somewhere to offset it. T and V guarantee this criterion before moving to S, the accepted state. 

T ::= bd | bTd
U ::= bc | bUc
V ::= bUd | bVd
S ::= T | V | aSd