Making a simplest possible CFG to recognize the language L = {a^i b^j c^k | i + j ≥ 2k}

Question

The language given is $L = \{a^i b^j c^k\mid i+j \ge 2k\}$ for which I need to construct a simplest possible Context Free Grammar.

I tried understanding but I could only go as far as making sense of $i+ j = 2k$ but I am unable to come up with anything that caters for the condition where it it can be less than 2k.

Answer 1

Grammar

Main rules:
S -> AASc | T      two A for each c
T -> ABUc | U      AB for one c (at most once)
U -> BBUc | ε      two B for each c
A -> Aa | a        one or more a for each A
B -> Bb | b        one or more b for each B

Additional rules:
S -> A | B | AB

The main rules for S, T and U produce $A^i B^j c^k$ with $i+j=2k$. The rules for A and B turn them into $a$ and $b$, allowing additional ones to make it $\ge$.

The additional rules are for $k=0$, since with $i+j=2k$, that also means $i=j=0$. I'll try to think of a neater way to cover those cases.

Testing results / tool

I wrote a little tool that computes all words produced by the grammar up to a certain length and compares that to the correct set of words up to that length. Result:

Correct for words up to length 15: True
(That's 471 words.)
missing 0 words: []
invalid 0 words: []

Code (Try it online!):

import re
from itertools import product

start = "S"
rules = {
    "S": ["AASc", "T", "A", "B", "AB"],
    "T": ["ABUc", "U"],
    "U": ["BBUc", ""],
    "A": ["Aa", "a"],
    "B": ["Bb", "b"],
}
empties = "[UTS]"

max_length = 15

# Generate words with the grammar
words = horizon = {start}
while horizon:
    horizon = {
        new_word
        for word in horizon
        for match in re.finditer("[A-Z]'?", word)
        for symbol, start, stop in [[match[0], *match.span()]]
        for body in rules[symbol]
        for new_word in [word[:start] + body + word[stop:]]
        if len(re.sub(empties, '', new_word)) <= max_length
    } - words
    words |= horizon
generated_words = {word for word in words
                   if not word or word.islower()}

# Generate words in a simple was as reference
correct_words = {
    'a'*i + 'b'*j + 'c'*k
    for i, j, k in product(range(max_length + 1), repeat=3)
    if i + j + k <= max_length and i + j >= 2 * k
}

# Show the comparison results
print(f'Correct for words up to length {max_length}:',
      generated_words == correct_words)
print(f"(That's {len(correct_words)} words.)")
def sort(words):
    return sorted(words, key=lambda word: (len(word), word))
missing = sort(correct_words - generated_words)
invalid = sort(generated_words - correct_words)
print(f'missing {len(missing)} words:', missing)
print(f'invalid {len(invalid)} words:', invalid)

Testing gnasher729's grammar

Using this:

start = "S"
rules = {
    "S": ["aaSc", "a", "X", "abXc"],
    "X": ["bbXc", "Y"],
    "Y": ["bY", ""],
}
empties = "[YXS]"

Result (Try it online!):

Correct for words up to length 15: False
(That's 471 words.)
missing 265 words: ['aa', 'ab', 'aaa', 'aab', 'abb', 'aaaa', 'aaab', 'aabb', 'abbb', 'aaaaa', 'aaaab', 'aaaac', 'aaabb', 'aaabc', 'aabbb', 'abbbb', 'aaaaaa', 'aaaaab', 'aaaaac', 'aaaabb', 'aaaabc', 'aaabbb', 'aaabbc', 'aabbbb', 'abbbbb', 'aaaaaaa', 'aaaaaab', 'aaaaaac', 'aaaaabb', 'aaaaabc', 'aaaabbb', 'aaaabbc', 'aaabbbb', 'aaabbbc', 'aabbbbb', 'abbbbbb', 'aaaaaaaa', 'aaaaaaab', 'aaaaaaac', 'aaaaaabb', 'aaaaaabc', 'aaaaaacc', 'aaaaabbb', 'aaaaabbc', 'aaaaabcc', 'aaaabbbb', 'aaaabbbc', 'aaabbbbb', 'aaabbbbc', 'aabbbbbb', 'abbbbbbb', 'aaaaaaaaa', 'aaaaaaaab', 'aaaaaaaac', 'aaaaaaabb', 'aaaaaaabc', 'aaaaaaacc', 'aaaaaabbb', 'aaaaaabbc', 'aaaaaabcc', 'aaaaabbbb', 'aaaaabbbc', 'aaaaabbcc', 'aaaabbbbb', 'aaaabbbbc', 'aaabbbbbb', 'aaabbbbbc', 'aabbbbbbb', 'abbbbbbbb', 'aaaaaaaaaa', 'aaaaaaaaab', 'aaaaaaaaac', 'aaaaaaaabb', 'aaaaaaaabc', 'aaaaaaaacc', 'aaaaaaabbb', 'aaaaaaabbc', 'aaaaaaabcc', 'aaaaaabbbb', 'aaaaaabbbc', 'aaaaaabbcc', 'aaaaabbbbb', 'aaaaabbbbc', 'aaaaabbbcc', 'aaaabbbbbb', 'aaaabbbbbc', 'aaabbbbbbb', 'aaabbbbbbc', 'aabbbbbbbb', 'abbbbbbbbb', 'aaaaaaaaaaa', 'aaaaaaaaaab', 'aaaaaaaaaac', 'aaaaaaaaabb', 'aaaaaaaaabc', 'aaaaaaaaacc', 'aaaaaaaabbb', 'aaaaaaaabbc', 'aaaaaaaabcc', 'aaaaaaaaccc', 'aaaaaaabbbb', 'aaaaaaabbbc', 'aaaaaaabbcc', 'aaaaaaabccc', 'aaaaaabbbbb', 'aaaaaabbbbc', 'aaaaaabbbcc', 'aaaaabbbbbb', 'aaaaabbbbbc', 'aaaaabbbbcc', 'aaaabbbbbbb', 'aaaabbbbbbc', 'aaabbbbbbbb', 'aaabbbbbbbc', 'aabbbbbbbbb', 'abbbbbbbbbb', 'aaaaaaaaaaaa', 'aaaaaaaaaaab', 'aaaaaaaaaaac', 'aaaaaaaaaabb', 'aaaaaaaaaabc', 'aaaaaaaaaacc', 'aaaaaaaaabbb', 'aaaaaaaaabbc', 'aaaaaaaaabcc', 'aaaaaaaaaccc', 'aaaaaaaabbbb', 'aaaaaaaabbbc', 'aaaaaaaabbcc', 'aaaaaaaabccc', 'aaaaaaabbbbb', 'aaaaaaabbbbc', 'aaaaaaabbbcc', 'aaaaaaabbccc', 'aaaaaabbbbbb', 'aaaaaabbbbbc', 'aaaaaabbbbcc', 'aaaaabbbbbbb', 'aaaaabbbbbbc', 'aaaaabbbbbcc', 'aaaabbbbbbbb', 'aaaabbbbbbbc', 'aaabbbbbbbbb', 'aaabbbbbbbbc', 'aabbbbbbbbbb', 'abbbbbbbbbbb', 'aaaaaaaaaaaaa', 'aaaaaaaaaaaab', 'aaaaaaaaaaaac', 'aaaaaaaaaaabb', 'aaaaaaaaaaabc', 'aaaaaaaaaaacc', 'aaaaaaaaaabbb', 'aaaaaaaaaabbc', 'aaaaaaaaaabcc', 'aaaaaaaaaaccc', 'aaaaaaaaabbbb', 'aaaaaaaaabbbc', 'aaaaaaaaabbcc', 'aaaaaaaaabccc', 'aaaaaaaabbbbb', 'aaaaaaaabbbbc', 'aaaaaaaabbbcc', 'aaaaaaaabbccc', 'aaaaaaabbbbbb', 'aaaaaaabbbbbc', 'aaaaaaabbbbcc', 'aaaaaaabbbccc', 'aaaaaabbbbbbb', 'aaaaaabbbbbbc', 'aaaaaabbbbbcc', 'aaaaabbbbbbbb', 'aaaaabbbbbbbc', 'aaaaabbbbbbcc', 'aaaabbbbbbbbb', 'aaaabbbbbbbbc', 'aaabbbbbbbbbb', 'aaabbbbbbbbbc', 'aabbbbbbbbbbb', 'abbbbbbbbbbbb', 'aaaaaaaaaaaaaa', 'aaaaaaaaaaaaab', 'aaaaaaaaaaaaac', 'aaaaaaaaaaaabb', 'aaaaaaaaaaaabc', 'aaaaaaaaaaaacc', 'aaaaaaaaaaabbb', 'aaaaaaaaaaabbc', 'aaaaaaaaaaabcc', 'aaaaaaaaaaaccc', 'aaaaaaaaaabbbb', 'aaaaaaaaaabbbc', 'aaaaaaaaaabbcc', 'aaaaaaaaaabccc', 'aaaaaaaaaacccc', 'aaaaaaaaabbbbb', 'aaaaaaaaabbbbc', 'aaaaaaaaabbbcc', 'aaaaaaaaabbccc', 'aaaaaaaaabcccc', 'aaaaaaaabbbbbb', 'aaaaaaaabbbbbc', 'aaaaaaaabbbbcc', 'aaaaaaaabbbccc', 'aaaaaaabbbbbbb', 'aaaaaaabbbbbbc', 'aaaaaaabbbbbcc', 'aaaaaaabbbbccc', 'aaaaaabbbbbbbb', 'aaaaaabbbbbbbc', 'aaaaaabbbbbbcc', 'aaaaabbbbbbbbb', 'aaaaabbbbbbbbc', 'aaaaabbbbbbbcc', 'aaaabbbbbbbbbb', 'aaaabbbbbbbbbc', 'aaabbbbbbbbbbb', 'aaabbbbbbbbbbc', 'aabbbbbbbbbbbb', 'abbbbbbbbbbbbb', 'aaaaaaaaaaaaaaa', 'aaaaaaaaaaaaaab', 'aaaaaaaaaaaaaac', 'aaaaaaaaaaaaabb', 'aaaaaaaaaaaaabc', 'aaaaaaaaaaaaacc', 'aaaaaaaaaaaabbb', 'aaaaaaaaaaaabbc', 'aaaaaaaaaaaabcc', 'aaaaaaaaaaaaccc', 'aaaaaaaaaaabbbb', 'aaaaaaaaaaabbbc', 'aaaaaaaaaaabbcc', 'aaaaaaaaaaabccc', 'aaaaaaaaaaacccc', 'aaaaaaaaaabbbbb', 'aaaaaaaaaabbbbc', 'aaaaaaaaaabbbcc', 'aaaaaaaaaabbccc', 'aaaaaaaaaabcccc', 'aaaaaaaaabbbbbb', 'aaaaaaaaabbbbbc', 'aaaaaaaaabbbbcc', 'aaaaaaaaabbbccc', 'aaaaaaaaabbcccc', 'aaaaaaaabbbbbbb', 'aaaaaaaabbbbbbc', 'aaaaaaaabbbbbcc', 'aaaaaaaabbbbccc', 'aaaaaaabbbbbbbb', 'aaaaaaabbbbbbbc', 'aaaaaaabbbbbbcc', 'aaaaaaabbbbbccc', 'aaaaaabbbbbbbbb', 'aaaaaabbbbbbbbc', 'aaaaaabbbbbbbcc', 'aaaaabbbbbbbbbb', 'aaaaabbbbbbbbbc', 'aaaaabbbbbbbbcc', 'aaaabbbbbbbbbbb', 'aaaabbbbbbbbbbc', 'aaabbbbbbbbbbbb', 'aaabbbbbbbbbbbc', 'aabbbbbbbbbbbbb', 'abbbbbbbbbbbbbb']
invalid 0 words: []

Testing Peter Leupold's grammar

I'm not entirely sure I'm interpreting Peter correctly, but I think their full grammar is this:

start = 'S'
rules = {
    "S": ["aS'c", "aB'c", "aS"],
    "B'": ["bB", "b", "bB'"],
    "S'": ["aS", "aB", "aS'"],
    "B": ["bB'c", "bB"]
}
empties = "[']"

Result (Try it online!):

Correct for words up to length 15: False
(That's 471 words.)
missing 206 words: ['', 'a', 'b', 'aa', 'ab', 'bb', 'aaa', 'aab', 'aac', 'abb', 'bbb', 'bbc', 'aaaa', 'aaab', 'aaac', 'aabb', 'abbb', 'bbbb', 'bbbc', 'aaaaa', 'aaaab', 'aaaac', 'aaabb', 'aabbb', 'abbbb', 'bbbbb', 'bbbbc', 'aaaaaa', 'aaaaab', 'aaaaac', 'aaaabb', 'aaaacc', 'aaabbb', 'aabbbb', 'abbbbb', 'bbbbbb', 'bbbbbc', 'bbbbcc', 'aaaaaaa', 'aaaaaab', 'aaaaaac', 'aaaaabb', 'aaaaacc', 'aaaabbb', 'aaabbbb', 'aabbbbb', 'abbbbbb', 'bbbbbbb', 'bbbbbbc', 'bbbbbcc', 'aaaaaaaa', 'aaaaaaab', 'aaaaaaac', 'aaaaaabb', 'aaaaaacc', 'aaaaabbb', 'aaaabbbb', 'aaabbbbb', 'aabbbbbb', 'abbbbbbb', 'bbbbbbbb', 'bbbbbbbc', 'bbbbbbcc', 'aaaaaaaaa', 'aaaaaaaab', 'aaaaaaaac', 'aaaaaaabb', 'aaaaaaacc', 'aaaaaabbb', 'aaaaaaccc', 'aaaaabbbb', 'aaaabbbbb', 'aaabbbbbb', 'aabbbbbbb', 'abbbbbbbb', 'bbbbbbbbb', 'bbbbbbbbc', 'bbbbbbbcc', 'bbbbbbccc', 'aaaaaaaaaa', 'aaaaaaaaab', 'aaaaaaaaac', 'aaaaaaaabb', 'aaaaaaaacc', 'aaaaaaabbb', 'aaaaaaaccc', 'aaaaaabbbb', 'aaaaabbbbb', 'aaaabbbbbb', 'aaabbbbbbb', 'aabbbbbbbb', 'abbbbbbbbb', 'bbbbbbbbbb', 'bbbbbbbbbc', 'bbbbbbbbcc', 'bbbbbbbccc', 'aaaaaaaaaaa', 'aaaaaaaaaab', 'aaaaaaaaaac', 'aaaaaaaaabb', 'aaaaaaaaacc', 'aaaaaaaabbb', 'aaaaaaaaccc', 'aaaaaaabbbb', 'aaaaaabbbbb', 'aaaaabbbbbb', 'aaaabbbbbbb', 'aaabbbbbbbb', 'aabbbbbbbbb', 'abbbbbbbbbb', 'bbbbbbbbbbb', 'bbbbbbbbbbc', 'bbbbbbbbbcc', 'bbbbbbbbccc', 'aaaaaaaaaaaa', 'aaaaaaaaaaab', 'aaaaaaaaaaac', 'aaaaaaaaaabb', 'aaaaaaaaaacc', 'aaaaaaaaabbb', 'aaaaaaaaaccc', 'aaaaaaaabbbb', 'aaaaaaaacccc', 'aaaaaaabbbbb', 'aaaaaabbbbbb', 'aaaaabbbbbbb', 'aaaabbbbbbbb', 'aaabbbbbbbbb', 'aabbbbbbbbbb', 'abbbbbbbbbbb', 'bbbbbbbbbbbb', 'bbbbbbbbbbbc', 'bbbbbbbbbbcc', 'bbbbbbbbbccc', 'bbbbbbbbcccc', 'aaaaaaaaaaaaa', 'aaaaaaaaaaaab', 'aaaaaaaaaaaac', 'aaaaaaaaaaabb', 'aaaaaaaaaaacc', 'aaaaaaaaaabbb', 'aaaaaaaaaaccc', 'aaaaaaaaabbbb', 'aaaaaaaaacccc', 'aaaaaaaabbbbb', 'aaaaaaabbbbbb', 'aaaaaabbbbbbb', 'aaaaabbbbbbbb', 'aaaabbbbbbbbb', 'aaabbbbbbbbbb', 'aabbbbbbbbbbb', 'abbbbbbbbbbbb', 'bbbbbbbbbbbbb', 'bbbbbbbbbbbbc', 'bbbbbbbbbbbcc', 'bbbbbbbbbbccc', 'bbbbbbbbbcccc', 'aaaaaaaaaaaaaa', 'aaaaaaaaaaaaab', 'aaaaaaaaaaaaac', 'aaaaaaaaaaaabb', 'aaaaaaaaaaaacc', 'aaaaaaaaaaabbb', 'aaaaaaaaaaaccc', 'aaaaaaaaaabbbb', 'aaaaaaaaaacccc', 'aaaaaaaaabbbbb', 'aaaaaaaabbbbbb', 'aaaaaaabbbbbbb', 'aaaaaabbbbbbbb', 'aaaaabbbbbbbbb', 'aaaabbbbbbbbbb', 'aaabbbbbbbbbbb', 'aabbbbbbbbbbbb', 'abbbbbbbbbbbbb', 'bbbbbbbbbbbbbb', 'bbbbbbbbbbbbbc', 'bbbbbbbbbbbbcc', 'bbbbbbbbbbbccc', 'bbbbbbbbbbcccc', 'aaaaaaaaaaaaaaa', 'aaaaaaaaaaaaaab', 'aaaaaaaaaaaaaac', 'aaaaaaaaaaaaabb', 'aaaaaaaaaaaaacc', 'aaaaaaaaaaaabbb', 'aaaaaaaaaaaaccc', 'aaaaaaaaaaabbbb', 'aaaaaaaaaaacccc', 'aaaaaaaaaabbbbb', 'aaaaaaaaaaccccc', 'aaaaaaaaabbbbbb', 'aaaaaaaabbbbbbb', 'aaaaaaabbbbbbbb', 'aaaaaabbbbbbbbb', 'aaaaabbbbbbbbbb', 'aaaabbbbbbbbbbb', 'aaabbbbbbbbbbbb', 'aabbbbbbbbbbbbb', 'abbbbbbbbbbbbbb', 'bbbbbbbbbbbbbbb', 'bbbbbbbbbbbbbbc', 'bbbbbbbbbbbbbcc', 'bbbbbbbbbbbbccc', 'bbbbbbbbbbbcccc', 'bbbbbbbbbbccccc']
invalid 0 words: []

Answer 2

Most likely the CFG you made has some transition to an accepting state when it sees the stack is empty.

This is exactly what checks the equality between $i+j$ and $2k$.

If, instead, you would change the transition so that it will always do this transition (Notice, this is a nondeterministic PDA!), then the PDA will accept any word that reaches this state while not "dying out" in the middle of the run. If you will think about it - this is exactly the change you need to also accept words with $i+j\ge 2k$.

Answer 3

Maybe your grammar for the equality in the condition looks something like this (only the productions):

$$ S\rightarrow aS'c | aB'c, \ \ B' \rightarrow bB |b, \ \ S' \rightarrow aS | aB, \ \ B \rightarrow bB'c $$

This supposes that $i$ and $j$ must be at least one. The primed nonterminals say that we have an odd $(i+j)$, the nonprimed ones say that this number is even. $(i+j)$ must be even in accepted words, so can only terminate with productions from the primed versions, which add one more symbol to make $(i+j)$ even. The $c$ are added via the productions from the nonprimed nonterminals.

Now if we add the possibility to produce additional $a$ and/or $b$ via the rules $S\rightarrow aS$ and $B\rightarrow bB$ and the same for the primed versions we can get $i+j> 2k$.

Answer 4

If it was i + j >= k: You first produce a’s and c’s in pairs, then b’s and c’s in pairs, then some more b’s. But it’s i + j >= 2k, so you need 2 a’s and b’s for every c.

To do this we start producing two a’s and one c in pairs. Then we can add a single a and are done. Or we optionally add ab and c, then bb and c in pairs, then more single b’s. In summary:

S -> aaSc  
S -> a  
S -> X   
S -> abXc
X -> bbXc
X -> Y
Y -> bY
Y -> eps  

You can easily see that the result is $a^ib^jc^k$, that i and j can be any integers, and that for each c, we produce at least two of a and b.

For some practice, write a grammar for the case 2i + j >= 3k. You just need to be very careful with the details.