2 as hint was not sufficient I put in details. edited Jun 26 '13 at 11:08 Hendrik Jan 22.3k2929 silver badges7676 bronze badges If I understand your question, you should consider $$(a,aa)^*$$$$(a,aa)^* = \{ ( a^n, a^{2n} ) \mid n\ge 0 \}$$. Perhaps the following notation helps $$(a,aa)^* = \{ \left(\begin{array}{c}a^n\\ a^{2n} \end{array}\right)\mid n\ge 0\}$$. Interpreted over a two level alphabet this should be interpreted as $$\{ \left(\begin{array}{c}a\\ a\end{array}\right)^n \left(\begin{array}{c}\\\ a\end{array}\right)^n \mid n\ge 0\}$$. Your turn to conclude. Here I assume \$'s can only be added at the end of the string. If I understand your question, you should consider $$(a,aa)^*$$. If I understand your question, you should consider $$(a,aa)^* = \{ ( a^n, a^{2n} ) \mid n\ge 0 \}$$. Perhaps the following notation helps $$(a,aa)^* = \{ \left(\begin{array}{c}a^n\\ a^{2n} \end{array}\right)\mid n\ge 0\}$$. Interpreted over a two level alphabet this should be interpreted as $$\{ \left(\begin{array}{c}a\\ a\end{array}\right)^n \left(\begin{array}{c}\\\ a\end{array}\right)^n \mid n\ge 0\}$$. Your turn to conclude. Here I assume \$'s can only be added at the end of the string. 1 answered Jun 26 '13 at 7:55 Hendrik Jan 22.3k2929 silver badges7676 bronze badges If I understand your question, you should consider $$(a,aa)^*$$.