The language of chains with twice as many $a$s as $b$s is regular?

Question

I am trying to understand the pumping lemma and its instrumentation to show a certain language is not regular. My first attempt was the following problem:

Let $L$ be the language of all words that have twice as many $a$s as $b$s. Is it regular? Is it context-free?

I attempted the following. First, let $p>0$ be the pumping length. Observe that $ba^{2p}b^{p-1}$ is in the language, because $b$ occurs $p$ times and $a$ occurs $2p$ times. Let $xy = ba^{2p}$ and $z = b^{p-1}$. According to the pumping lemma, if $L$ is regular then $y$ can be repeated indefinitely many times while keeping the resulting word in the language. In particular, if $L$ is regular, then

$$xy^{2}z = ba^{4p}b^{p-1}$$

is in the language. This is clearly a contradiction, because $4p \neq 2p$. Then the language is not regular.

I have two questions. The first is rather general: is the preceeding proof correct? The second is: how does the fact that a language is regular relate to whether it is context-free? I know a language is context-free if there is a context-free grammar that produces it. Context-free grammars are homomorphic to automatons, and so are regular languages, and hence it should follow that if a language is not a regular language then it cannot be a context free grammar, correct?

Thanks in advance.

Answer 1

These are two really different questions, so your second question really should be asked separately.

Is the preceding proof correct?

Not completely. The lemma says that for some $p$, every word at least $p$ long can be pumped, meaning it can be written as $xyz$ such that all words in $xyy^*z$ are in the language. But it doesn't say you can pick $x,y,z$ at will, which you seem to be doing.

How does the fact that a language is regular relate to whether it is context-free?

A language is regular if and only if

• a regular expression describes it
• a finite state automaton accepts it
• a regular grammar generates it

A language is context-free if and only if

• a pushdown automaton accepts it
• a context-free grammar generates it

Now:

• Every finite automaton is a pushdown automaton, but not vice versa.
• Every regular grammar is a context-free grammar, but not vice versa.

As a result:

• All regular languages are context-free, but not vice versa.

Context-free languages have a different pumping lemma.