0
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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

As a result:

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

Context-free languages have a different pumping lemma.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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