1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Could you add a bit more context to these questions? What are "a_concatenation_n" or "na(w)", for example? $\endgroup$ – siracusa Nov 25 '19 at 14:29
  • 4
    $\begingroup$ The second is a strict superset of the first. Examples of words included only in the second language are $c,aba,baa$. $\endgroup$ – Yuval Filmus Nov 25 '19 at 14:56
  • $\begingroup$ 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. $\endgroup$ – user2994783 Nov 25 '19 at 17:26
1
$\begingroup$

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.
$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.