0
$\begingroup$

This question already has an answer here:

I've been given the following task and have tried a few things, but none seem to result in what is required.

$L = \{ww \mid w \in \{a,b\}^*\}$

What Chomsky-Type is $L$? Provide a grammar fulfilling that Type.

It can't be context-free, since that wouldn't allow us to force that we write each symbol twice at the right place. Also it shouldn't be Type-0, since I suspect that rules that satisfy context-sensitive should be fine(namely all rules fulfill $u \rightarrow p$ with $\mid u\mid \leq \mid p\mid$)

Now I've tried to find a working grammar that fulfills Type-1, but I fail at getting the right order of $a,b$ in the second word.

How could I go about this and am I even right with suspecting to be able to find a Type-1 grammar?

$\endgroup$

marked as duplicate by Raphael Feb 8 '18 at 11:07

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ I'm fairly sure we already have this on the site somwhere. Also, related question. $\endgroup$ – Raphael Feb 7 '18 at 18:54
  • $\begingroup$ @Raphael That's an awesome topic, thank you. Since the accepted answer is of a TM, I suspect that my assumption that $L$ is of type-1 is false, else they'd use a pushdown automaton, right? $\endgroup$ – Meik Vtune Feb 7 '18 at 19:25
  • $\begingroup$ cs.stackexchange.com/questions/33853/… describes an approach. $\endgroup$ – rici Feb 7 '18 at 19:30
  • $\begingroup$ @rici Thank you so much, that is a great answer, very generic for any Language $L$ with $\{w^k \mid w \in \Sigma^* \} \forall k\in\mathbb{N}$ $\endgroup$ – Meik Vtune Feb 7 '18 at 19:54
  • $\begingroup$ @rici Note that LBAs are eqivalent to type-1, not TMs. Try to figure out if you can implement Klaus Draeger's sketch wthout using additional tape! $\endgroup$ – Raphael Feb 7 '18 at 20:47