0

The problem is to demonstrate the regularity of the following language: {xy ∈ {a,b}* | |X|a = 2|Y|b} which refers to words of the form xy where the number of occurrences of a in subword x is twice the number of occurrences of b in subword y. I suspect that it is regular but I don't know how to demonstrate it. Finding its DFA would be enough ?

Thanks in advance

Paul94
  • 1
  • 1
    Finding a DFA is enough, but in fact this language is not regular; use the pumping lemma. – Qiaochu Yuan Nov 22 '17 at 21:39
  • I know the pumping lemma, all of examples that I have read follow the same structure like the typical problem a^n b^n but in this case there is no pattern. So, which word we have to choose initially? – Paul94 Nov 22 '17 at 22:11
  • Hmm, okay, I thought I had a word that worked but it actually doesn't, my bad. – Qiaochu Yuan Nov 22 '17 at 22:50

1 Answers1

1

The set of regular languages is closed under intersection. So suppose your language $L$ is regular. Then $L \cap a^{*}b^{*} = \{ a^{n}b^{2n} : n \in \mathbb{N} \}$ is also regular. A pumping lemma argument easily shows that $L^{\prime} = \{ a^{n}b^{2n} : n \in \mathbb{N}\}$ is not regular.

Pump the string $a^{p}b^{2p} \in L^{\prime}$, where $p$ is the pumping length of $L^{\prime}$.

As $L^{\prime}$ is not regular and $a^{*}b^{*}$ is regular, it follows that $L$ is not regular.

ml0105
  • 14,674