Is the language { ww | w ∈ {a,b}* } context free? I have tried to create a pushdown automaton but I didn't find any solution. I think you need a queue and not a stack.

Is there a way to prove this statement using the pumping lemma?

  • 1
    $\begingroup$ See our reference pages. I do not know that the pumping lemma will show a queue is appropriate, but it should help you prove something about being CF. $\endgroup$ – babou Jun 9 '15 at 11:30
  • $\begingroup$ I've wondered the same thing as fabi. It's easy to define a "pushthrough automaton" that uses a queue instead of a stack but the subject doesn't appear to come up in formal language theory. Probably because natural and artificial languages tend to use nesting more than the kind of structures such machines can describe. $\endgroup$ – reinierpost Jun 9 '15 at 11:57
  • $\begingroup$ @reinierpost Queues offer little possibility for detecting local structures (without huge runtime overhead). Are there any uses besides detecting ww patterns? $\endgroup$ – Raphael Jun 9 '15 at 12:41
  • $\begingroup$ You don't include much of an own attempt towards solving the problem, so we can not know what your issue is. The reference answers contain solutions. $\endgroup$ – Raphael Jun 9 '15 at 12:43
  • $\begingroup$ @Raphael: One example might be bulk assignment such as my ($a, $b, $c) = ($c + 4, "d", $a) in Perl. Now Perl variables aren't sufficiently strongly typed to make this a convincing example, but constructs such as this might make it attractive to support queues in your parsing automaton. $\endgroup$ – reinierpost Jun 9 '15 at 14:32