I am not well versed in this topic so please pardon any ambiguous notation. I am trying to describe the language of this grammar in set-theoretic notation.

The Grammar is given by:

$ S \rightarrow ASA|B$

$ A \rightarrow a|b$

$ B \rightarrow BC|\epsilon$

$ C \rightarrow a|b|c$

I think I can accurately describe this language in english:

If $w=xyz$ is a string and $xyz$ are substrings of $w$ then

$|x| = |z|$, and $x$ and $z$ are made up of symbols from $\{a,b\}^*$.

Furthermore, $y$ is made up of symbols from $\{a,b,c\}^*$

Mores simply, the strings are made up of two ends that are the same $|length| \ge 0$ and made up of symbols $a,b$. And the middle part of the string is made up of any symbols from $a,b,c$ and also has a $|length| \ge 0$

How do I more formally and accurately describe the language of the grammar $L(G)$? Is it possible to do this in a set-theoretic notation?

  • $\begingroup$ Your question smells like XY problem. Why do you require "in set theoretic notation where the length of strings need to be remembered"? I would bet all you wanted was to describe the language generated by the given grammar. $\endgroup$ – John L. Oct 31 '18 at 4:09
  • $\begingroup$ @Apass.Jack Didn't I already describe the language of the Grammar in my question? All I am asking is what a more formal description of the language would look like (what form would it take), and if that formal description would take a set-theoretic notation, or if it even can. $\endgroup$ – SeesSound Oct 31 '18 at 4:14
  • $\begingroup$ The language of the give grammar can be described simply as "all words over the alphabet $\{a,b,c\}$", which is a formal description. I would say the set-theoretic notation of regular languages is the regular expression. That languages is $(a\mid b\mid c)^*$. Are those what you wanted? $\endgroup$ – John L. Oct 31 '18 at 4:29

Your grammar generates $\Sigma^*$, where $\Sigma = \{a,b,c\}$.

  • $\begingroup$ I'm in disbelief that it is this simple. What about the parts of the grammar that are saying that the outsides are all $a's$ and $b's$, why are you ignoring those rules? Why wouldnt they just make the Grammar as: $S \rightarrow aS|bS|cS|\epsilon$? Is this an equivalent grammar? $\endgroup$ – SeesSound Oct 31 '18 at 4:41
  • 1
    $\begingroup$ The grammar can definitely be simplified. They are just (figuratively) pulling your leg. $\endgroup$ – Yuval Filmus Oct 31 '18 at 4:48

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.