0
$\begingroup$

I have been trying to find a a CFG for this language generated.

I came to the conclusion that I need three parts

  1. When $i \le j$
  2. When $j < 2j < i$
  3. When $j < i < 2j$

I was able to come up the production rules for 1 and 2 but I'm getting stuck at 3.

I thought I found a solution in Context Free Grammar for $\{a^ib^j | i,j ≥ 0; i ≠ 2j\}$, but when I tried for $0^81^5$ it didn't work.

I was however able to come up with a CSG.

Do you know how to solve this?

$\endgroup$
3
  • 1
    $\begingroup$ Does this answer your question? Context Free Grammar for {a^ib^j | i,j ≥ 0; i ≠ 2j} $\endgroup$ Feb 10, 2023 at 10:11
  • $\begingroup$ What evidence do you have that the linked answer doesn't generate $0^81^5$? $\endgroup$
    – rici
    Feb 10, 2023 at 13:53
  • $\begingroup$ Specifically, in the grammar in the accepted answer, the derivation is $S\to S_2, S_2\to Bb$ and then $B\to aaBb$ four times, and finally $B\to\varepsilon$. $\endgroup$
    – rici
    Feb 10, 2023 at 14:51

2 Answers 2

1
$\begingroup$

I will only argue about 3), since this is the case you're having troubles with.

Consider $\{ 0^i 1^j \mid j \le i \le 2j \}$ for a moment. You can get a CFG for this language by noticing that you can "match" each occurrence of a $1$ to either $1$ or $2$ occurrences of $0$s (in such a way that every occurrence of $0$ is matched exactly to a single occurrence of $1$).

$$ S \to 0S1 \mid 00S1 \mid \varepsilon $$

To get a CFG for $\{ 0^i 1^j \mid j < i < 2j \}$ you just need to ensure that a) there is at least one $1$ matched to a single $0$, and b) there is at least one $1$ matched to two $0$s.

Since using the order of the rules is irrelevant and using $S \to 0S1$ followed $S \to S \to 00S1$ generates $3$ zeros and $2$ ones, we can simulate the execution of these rules as the last step each possible derivation by replacing $S \to \varepsilon$ with $S \to 00011$. To summarize, the final grammar is: $$ S \to 0S1 \mid 00S1 \mid 00011. $$

$\endgroup$
0
0
$\begingroup$

You only need a grammar for i < 2j and i > 2j. Have a symbol X that gets converted to 0, 01, 0X, 0X1 or 0X11, so j < 2i. And a symbol Y that gets converted to 1 or 0Y11Z, with Z converted to eps or Z1, so j > 2i.

S -> X | Y
X -> 0 | 01 | 0X | 0X1 | 0x11
Y -> 1 | 0Y11Z
Z -> eps | Z1
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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