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?
Asked
Active
Viewed 68 times
0
-
$1224$ is in the language. – zarathustra Dec 31 '13 at 15:35
-
@Antoine Is it something like that? $$ {1^k 2^l 3^m 4^n}$$ – Mary Star Dec 31 '13 at 15:41
-
@Antoine How would you produce $1224$? – Daniel Fischer Dec 31 '13 at 15:43
-
@DanielFischer: luckily you walked by and opened my eyes. Sorry about that! – zarathustra Dec 31 '13 at 15:47
-
So is my first idea right? – Mary Star Dec 31 '13 at 15:50
-
No, because $14$ is in the language, at least until @DanielFischer comes back. You obtain $14$ with the derivation $S \rightarrow S_{14} \rightarrow 1S_{14}4 \rightarrow 1S_{13}4\rightarrow 1S_{23}4 \rightarrow 1\emptyset4 = 14$ – zarathustra Dec 31 '13 at 15:54
1 Answers
2
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\}$.
zarathustra
- 4,891