1
$\begingroup$

Suppose the language is $\{AA^R: A \in \{a,b\}^*\}$.

I know that I can make a context free grammar for it:

$$S\to aSa \mid bSb\mid\epsilon$$

Now if the language was $\{AA^Rcc: A \in \{a,b\}^*\}$, so the same thing but with $cc$ at the end. Would the following context free grammar work?

$$\begin{aligned} S&\to aS \mid bS\mid\epsilon\mid T\\ T&\to cc\\ \end{aligned}$$

I think it works cause you have the options to make the original string and its reverse, but unlike in the first example, the grammar doesn't fit how the output is suppose to be and so you kind of have to remember what the original string was to make the reverse and then append $cc$ at the end. But then I remember that automata doesn't have memory of previous states so what would be correct grammar?

$\endgroup$
2
$\begingroup$

This CFG does not work

$$\begin{aligned} S&\to aS \mid bS\mid\epsilon\mid T\\ T&\to cc\\ \end{aligned}$$ It generates $acc$ by $S\Rightarrow aS\Rightarrow aT\Rightarrow acc$, which is not of form $AA^Rcc$. In fact, it generates the language $\{Acc: A \in \{a,b\}^*\}$.


You might have missed the basic mindset to write a context-free grammar (CFG).

Every non-terminal in a CFG stands for a language.

Thinking in terms of languages instead of strings should be more helpful sometimes for constructing the CFG.

Since the language $S=\{AA^Rcc: A \in \{a,b\}^*\}$ is the concatenation of the language of the palindromes of even length, $P=\{AA^R: A \in \{a,b\}^*\}$ and the language of one word, $C=\{cc\}$, the corresponding substitution rule is $$ S\to PC$$ to which we add the substitution rules for $P$ and $C$ $$\begin{aligned} P&\to aPa\mid bPb\mid\epsilon\\ C&\to cc.\\ \end{aligned}$$ The collection of all substitution rules above is the CFG wanted. Note that each of the symbols $S, P, C$ is abused to denote a non-terminal as well as the languages it stands for, i.e, the context-free language generated if we treat it as the starting symbol.

Exercise

Write a CFG for the language $\{AA^RbcBB^R: A \in \{a,b\}^*, B\in\{c,d\}^*\}$.

$\endgroup$
  • 1
    $\begingroup$ Guess it be like S->ADB, A->aAa|bAb|epsilon, D->bc, B->cBc|dBd|epsilon. I was wrong thinking that they should all linked together. $\endgroup$ – glockm15 Jun 4 at 7:17

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.