Skip to main content
Post Closed as "Duplicate" by D.W.
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
More descriptive title
Source Link
John L.
  • 39.1k
  • 4
  • 34
  • 91

Formal Languages and Automata - finding productions CSG How to find context sensitive grammar for words like ww?

I'm studying formal languages and automata, and on the section of learning how to find productions that generates the grammergrammar, 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 productionsCSG of this exercisethe 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?

EDIT: It's required to be a CSG

Formal Languages and Automata - finding productions CSG

I'm studying formal languages and automata, and on the section of learning how to find productions that generates the grammer, 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 productions of this exercise (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?

EDIT: It's required to be a CSG

How to find context sensitive grammar for words like ww?

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?

added 35 characters in body; edited title
Source Link

Formal Languages and Automata - finding productions on specific formatCSG

I'm studying formal languages and automata, and on the section of learning how to find productions that generates the grammer, 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 productions of this exercise (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?

EDIT: It's required to be a CSG

Formal Languages and Automata - finding productions on specific format

I'm studying formal languages and automata, and on the section of learning how to find productions that generates the grammer, 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 productions of this exercise (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?

Formal Languages and Automata - finding productions CSG

I'm studying formal languages and automata, and on the section of learning how to find productions that generates the grammer, 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 productions of this exercise (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?

EDIT: It's required to be a CSG

Source Link

Formal Languages and Automata - finding productions on specific format

I'm studying formal languages and automata, and on the section of learning how to find productions that generates the grammer, 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 productions of this exercise (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?