0
$\begingroup$

I'm studying formal languages and automata, and on the section of learning how to find productions that generates the grammar, I've done some exercises pretty well and was able to do some of the exercises on the format:

$L(G_1) = \{wcw^r / w\, is\, on\, \{0,1\}^*\}$

Where $w^r$ is the reverse word, and whose productions are:

$S \rightarrow c\, / \,0S0\,/\, 1S1$

But I'm struggling to find CSG of the following language (maybe a difficult one?):

$L(G_1) = \{ww / w\, is\, a\, word\, from\, \{a,b\}^*\}$

Almost every type of production that I tried ended up generating $ww^r$ instead of $ww$ such as:

$S \rightarrow aAa\,/\,bAb$

$A \rightarrow S\,/\, \epsilon$

Is there some kind of production that I'm not considering?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
0
$\begingroup$

What little you write here suggests you are trying to find a context-free grammar for the language you are having difficulty with. As it happens, that language is NOT context-free, i.e no such grammar is possible for that language. If you are aware of context-sensitive grammars, I suggest you try to find one for that language.

Improve this answer
$\endgroup$
3
  • $\begingroup$ So how do I find a context-sensitive grammar? I'm very confused with this one $\endgroup$
    – NumberAddicted
    Commented Feb 21, 2022 at 19:07
  • $\begingroup$ (The question has been edited since the 1st revision of this answer.) $\endgroup$
    – greybeard
    Commented Feb 22, 2022 at 1:51
  • $\begingroup$ A context sensitive grammar basically lets you do general programming. In the most horrible way imaginable. We use grammars because they are often an easy way to check if a string is in a language. If the language is ww: w elem L(G) and I give you some string, some trivial programming will give you w or show that w doesn’t exist. And then you check if w is in L(G). Or you make a horrible context sensitive grammar. $\endgroup$
    – gnasher729
    Commented Nov 14, 2023 at 7:33

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