1
$\begingroup$

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.

$\endgroup$

4 Answers 4

2
$\begingroup$

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: []
$\endgroup$
9
  • $\begingroup$ @JohnL. Ha, indeed. Fixed now? I shouldn't post way past bedtime. Anyway, I think non-empty $a^ib^j$ were the only words I was missing, while for gnasher729 that was just the shortest and easiest-to-check example. I think their grammar also can't produce words like aaaaac, i.e., where there are too many excess a. Do you know a good tool for testing grammars? $\endgroup$ May 8 at 12:30
  • $\begingroup$ There might be. However, equality is undecidable, so there is no tool can guarantee that. As gnasher729 remarked, "be very careful with the details." $\endgroup$
    – John L.
    May 8 at 12:32
  • $\begingroup$ @JohnL. Well, the general problem being undecidable doesn't mean that a single language/grammar can't be decided, right? I'm writing a tool now, testing all words up to a certain length. What do you mean with careful with the details? Just the mistake I already made, or something else? $\endgroup$ May 8 at 12:51
  • $\begingroup$ The quotation "be very careful..." is mostly for myself. I misconstrued "a good tool" as for general situations. It would be great if you can include your code that checks this grammar in your update. $\endgroup$
    – John L.
    May 8 at 13:03
  • $\begingroup$ Call a linear grammar acyclic if the graph formed by connecting the non-terminal at LHS to the non-terminal at RHS is acyclic. Acyclic linear grammars, such as the one here, should be pretty "decidable". It would be interesting to express and implement that idea. Of course, that is a new question. $\endgroup$
    – John L.
    May 8 at 13:35
0
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ Do you mind providing the CFG? It did make some sense but I am still unable to plot out the simplest possible CFG for this $\endgroup$
    – John
    Dec 8, 2021 at 6:55
  • $\begingroup$ What do you mean by "simplest"? Adding this change to what you already have should keep it simple enough. $\endgroup$
    – nir shahar
    Dec 8, 2021 at 13:42
0
$\begingroup$

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$.

$\endgroup$
1
  • $\begingroup$ Can you please add what you mean with "and the same for the primed versions"? I'm trying to test with the tool in my answer, and I think your grammar is missing words, but maybe I just don't understand what you're saying. $\endgroup$ May 8 at 14:35
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Unless I made a mistake, this is missing a lot of words, for example $aa$ and $aaabc$. See the testing results in my answer. $\endgroup$ May 8 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.