I want to give a grammar for the following language:

$$L = \{x^r \# y |x, y \in \{a, b, c\}^*\\ \text{ and }x\text{ is a contiguous sub-string of }y\}$$

where $x ^ r$ denotes the backward written word $x$

I have tried the grammar, is this right or have I made a mistake:

$S \to Sa \mid Sb \mid Sc \mid T$,

$T \to aTa \mid bTb \mid cTc \mid U$,

$U \to Ua \mid Ub \mid Uc \mid \#$

  • 2
    $\begingroup$ It looks correct. Note however that such "check-my-answer" questions are not really appropriate for this site, since answering "yes, that's correct" is uninteresting in general. For more discussion on such questions: cs.meta.stackexchange.com/questions/597/… $\endgroup$ – chi Feb 28 at 12:25
  • 1
    $\begingroup$ Indeed the grammar is correct since you generate exactly $(x^r (\# \{ a, b, c \}^\ast) x) \{ a, b, c \}^\ast$ with $x \in \{a, b, c\}^\ast$ (the parentheses denoting which part of the produced word is generated by which non-terminal). $\endgroup$ – dkaeae Feb 28 at 12:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy