Which language is accepted by the grammar

Question

Given the following grammar, I have to find which language is accepted. $$\{x \in \{1,2,3,4\}^{*}: S \to S_{14}, S_{14} \to 1S_{14}4 | S_{24}| S_{13}, S_{24} \to 2S_{24}4 | S_{23}, S_{13} \to 1S_{13}3 | S_{23}, S_{23} \to 2S_{23}3 | \varnothing \}$$ where $S$ is the initial symbol. My idea is the following: $$\{1^m2^n3^m4^n, m,n \geq0\}$$ Could you tell if it's right?

Answer 1

In order to do this kind of question, you can try to build the language in a bottom-up fashion, starting from the easiest non-terminals that you find.

Here, one sees that $S_{23}$ generates the language $\{2^n3^n, n\geq 0\}$. $S_{23}$ is used by $S_{13}$ and $S_{24}$, hence the next step would be to guess what language they generate.

The language $S_{13}$ generates must satisfy the equation $L = 1L3 + 2^n3^n$. A solution to this equation is $L_{13} = \{1^m2^n3^{m+n}, m,n\geq 0\}$, that you can find with trial-and-error.

The language $S_{24}$ generates is $\{2^{k+n}3^n4^k, k,n\geq 0\}$ by the same reasoning. Finally, the language generated by the whole grammar is $\{1^{l+m}2^n3^{m+n}4^l, l,m,n\geq 0\} \cup \{1^l 2^{k+n} 3^n 4^{k+l}, l,n,k\geq 0\}$.