# Difference between $a^{2n} b^n$ and $n_a(w) = 2n_b(w)$

I have encountered two questions related to npda:

1. Construct an npda for $$L_1 = \{a^{2n} b^n \mid n \geq 0\}$$ as a language over $$\Sigma = \{a,b,c\}$$.

2. Construct an npda for $$L_2 = \{w \in \{a, b, c\}^* \mid n_a(w) = 2n_b(w)\}$$.

What is the difference between the above two languages?

• Could you add a bit more context to these questions? What are "a_concatenation_n" or "na(w)", for example? – siracusa Nov 25 '19 at 14:29
• The second is a strict superset of the first. Examples of words included only in the second language are $c,aba,baa$. – Yuval Filmus Nov 25 '19 at 14:56
• First one can have strings like: aab, aaaabb, what about the possibility of 'c' in the first one? Please guide me.@siracusa: Sorry its same as a^2n b ^n. Some people says that use of power symbol not good in place of concatenation. – user2994783 Nov 25 '19 at 17:26

The usual definition is that $$n_a(w)$$ refers to the number of $$a$$s in $$w$$.

Based on this definition, $$L_1$$ consists exactly of words that begin with an even number of $$a$$s followed by half as many $$b$$s (no $$c$$s are permitted). Therefore, you have $$\varepsilon, aab, aaaabb, aaaaaabbb,... \in L_1$$.

Whereas $$L_2$$ consists of words containing an even number of $$a$$s and half as many $$b$$s (in any order and with an arbitrary number of $$c$$ in between).

Thus every word in $$L_1$$ is also in $$L_2$$ (formally $$L_1 \subseteq L_2$$), but there are words in $$L_2$$ that are not in $$L_1$$:

• For some $$n \geq 0$$, consider words of the form $$b^n a^{2n}$$. They are in $$L_2$$, because they contain an even number of $$a$$s and half as many $$b$$s, but if $$n > 0$$, then it does not match $$a^{2n} b^n$$, because the $$a$$s come after the $$b$$s. You have $$\varepsilon, baa,bbaaa,bbbaaaaaa,... \in L_2$$, but $$baa,bbaaa,bbbaaaaaa \notin L_1$$.
• The same argument applies for $$w = (aab)^n$$. You have $$\varepsilon, aab,aabaab,aabaabaab \in L_2$$, but $$aabaab,aabaabaab \notin L_1$$.
• A word can have an even number of $$a$$s and half as many $$b$$s and also contain $$c$$s. For example, $$a^{2n} b^n c \in L_2$$. But the words in $$L_1$$ by definition only contain $$a$$s and $$b$$s.

In both languages, each string must have twice as many $$a$$'s as $$b$$'s. For a string to be in the first language, it must satisfy the additional condition that all the $$a$$'s occur before any of the $$b$$'s. So $$aba$$ does not belong to the first language and does belong to the second language.