Hi so consider the language $L= \{(0^i)(1^j)\mid i=k*j \text{ for some positive }k\}$ Could I not rewrite this as $\{((0^k)^j)(b^j)\mid k>1\}$. Seeing it in this form makes me think of a form $a^n b^n$ which we know is context free so therefore it should be context free. Is my logic wrong and if not what would be the best way to show it's context free.

  • $\begingroup$ Your title is a bit strange. Can you make it more direct of explicit. $\endgroup$ – babou Apr 21 '15 at 15:10
  • $\begingroup$ I edited the title now, sorry didn't know how to word it. Do you have any idea on this? $\endgroup$ – learning_user7 Apr 21 '15 at 15:13
  • 1
    $\begingroup$ If you think that this is context free, come up with a context-free grammar generating it or with a push-down automaton accepting it. If you think that this is not context free, try to prove it, say using the pumping lemma. $\endgroup$ – Yuval Filmus Apr 21 '15 at 15:15
  • $\begingroup$ Your intuition is right. One is a homomorphic image of the other. Look at closure properties of CF Languages, and the reference page: cs.stackexchange.com/questions/18524/… $\endgroup$ – babou Apr 21 '15 at 15:23
  • $\begingroup$ Are you saying it should be context free then? And could prove it using homomorphism $\endgroup$ – learning_user7 Apr 21 '15 at 15:42

The best way to show that a language is context-free is to use one of the equivalent definitions of context-free languages. The two most popular ones are:

  • A language is context-free if it is generated by a context-free grammar.
  • A language is context-free if it is accepted by a (non-deterministic) push-down automaton.

The language $\{ a^n b^n : n \geq 0 \}$ is generated by the grammar $S \to aSb | \epsilon$. Let's try to use the same idea for your language: $S \to 0^k S 1 | \epsilon$ (we can implement $0^k$ using context-free rules). The problem is that we can't guarantee that the same $k$ is used in all productions. This leads me to conjecture that the language is not context-free.

How do we show that a language is not context-free? The most popular way is to use the pumping lemma or one of its variants, though this method doesn't always work. Perhaps you should give it a try.

  • $\begingroup$ Right I know what methods to use but trying to represent it as a grammar seems problematic like you said, I just wanted to make sure which road to take as yeah I'll just use the pumping-lemma for this. Thanks! $\endgroup$ – learning_user7 Apr 21 '15 at 15:21
  • 2
    $\begingroup$ In real life you don't always know which road to take. You have to try both options. $\endgroup$ – Yuval Filmus Apr 21 '15 at 15:22
  • $\begingroup$ Would it be ok to choose my pumping string to be (a^p)^p(b^p) $\endgroup$ – learning_user7 Apr 21 '15 at 16:17
  • $\begingroup$ If the proof works out, its ok. If it doesn't, it's not ok. Only one way to find out. $\endgroup$ – Yuval Filmus Apr 21 '15 at 16:28
  • $\begingroup$ I believe it works out unless I messed up my partitions mainly in the cases where if the string is broken into u,v,w,x, and y vwx contains all a's than if we pump the string in the form u(v^0)w(x^0)y there should be more b's than a's which can't happen in L $\endgroup$ – learning_user7 Apr 21 '15 at 16:35

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.