Context free grammar for a language

201 Views Asked by At

I have this context free language

$L = \{x^{3i} y^j z^k\ |\ i \ge 0 \land k \gt 2j \gt 0\}$

I'm working out a context free grammar that would generate that language.

I think there should be either 1 or 3 times xs, and 2 times plus 1 more z than y.

Therefore my solution would be:

$S \rightarrow TVU$
$T \rightarrow x \ |\ xxxU$
$U \rightarrow VzzUzU$
$V \rightarrow y \ |\ yV$

Is that fine?

Edit 1 (based on Baranovskiy comment):

$S \rightarrow TVU$
$T \rightarrow x \ |\ xxxU$
$U \rightarrow VzzUz$
$V \rightarrow y \ |\ yV$

Edit 2 (based on Baranovskiy comment):

$S \rightarrow TyUz^3V$
$T \rightarrow xxxT\ |\ \lambda$ (Since x can be $x^0$)
$U \rightarrow yVzz\ |\ \lambda$
$V \rightarrow zV \ |\ \lambda$

1

There are 1 best solutions below

4
On BEST ANSWER

Ok, I'm making an answer from comment. The important thing in this problem is to guarantee that $k > 2j > 0$ will hold in consecutive iterations and we have obviously start with a word at form $TyUVz^3$ to fulfill the same assumption. Hence solution may be following:

$S \to TyUVz^3$

$T \to xxxT | \varepsilon$

$U \to yUzz | \varepsilon$

$V \to Vz | \varepsilon$