Is it possible to create this context-free grammatic?

63 Views Asked by At

Is it possible to create this grammatic? $$ \left. 0^i 1^j 2^k \right| i + j \ne 2k $$

I try to create this, but I don't understand. I assume that we have to output $k$ characters '2' beforehand. But I think I'm confused. Can someone help me?

1

There are 1 best solutions below

0
On BEST ANSWER

$S\rightarrow A$

$A\rightarrow 0A2 | B$

$B\rightarrow 1B2 | C$

$C\rightarrow C2 | 2$

This should produce the language $0^i1^j2^k$ with $i+j<k$.

$S\rightarrow A | E$

$A\rightarrow 0A2 | B$

$B\rightarrow 0B | 0C$

$C\rightarrow 1C | \epsilon$

$E\rightarrow 0E2 | F$

$F\rightarrow 1F2 | 2G$

$G\rightarrow 2G | \epsilon$

This should produce the language $0^i1^j2^k$ with $i+j>k$.

Now you can take the union. With a similar idea you should be able to do with $2k$ instead of $k$.