0

I have a homework problem that I'm working through:

$L = {ww^R : w \in \{a,b\}^+}$

So I get the following:

$S \to aSa | bSb | \Lambda$

I am confused about the $\{a, b\}^+$, doesn't this mean that our alphabet cannot include $\Lambda$? If so, how do we terminate?

Alex M.
  • 35,207
Julian D
  • 13

1 Answers1

0

I believe that you are mixing two terms: "alphabet" and "language". The alphabet is the underlying set of symbols ("letters"); the language is the set of all words formed with symbols from the alphabet ("vocabulary"). As such, $\Lambda$ is never an element of the alphabet, because it is not supposed to be a letter; it is supposed to be a word, therefore it must belong to the vocabulary, i.e. it is a result of the application of production rules in the grammar. (Your question is like wondering why "abba" is not a member of the alphabet; because it is a word, not a letter.)

Alex M.
  • 35,207
  • Thank you for correcting me. So what impact does the {a, b}^+ have on our grammar then, if \Lambda can be included? – Julian D Sep 10 '15 at 18:11
  • I believe that {a, b}^+ is called a positive closure correct? So this means that we cannot use Lambda to terminate this particular grammar? Because positive closures do not include empty sets. – Julian D Sep 10 '15 at 18:24
  • @JulianD: Your remark is correct: either put a $\star$ instead of $+$ in order to obtain ${a,b}^\star$ (and allowing for $0$ repetitions you effectively obtain $\Lambda$), or define the language as $L = \big( ww^R : w \in {a,b}^+ \big) \cup { \Lambda } = \big( ww^R : w \in {a,b}^+ \cup { \Lambda } \big)$, i.e. make the presence of $\Lambda$ explicit. – Alex M. Sep 10 '15 at 18:36
  • So the production could be defined as $S -> aSa | bSb | a | b$ ? Is this correct? – Julian D Sep 10 '15 at 18:39
  • @JulianD: It is not correct, because $a$ is not a "symmetric word", i.e. is not of the type $ww^R$. – Alex M. Sep 10 '15 at 18:42
  • Good point. So with that being said, the production should be $S-> aSa|bSb|aa|bb$ – Julian D Sep 10 '15 at 18:44
  • @JulianD: Yep, that one seems fine. – Alex M. Sep 10 '15 at 18:44