Given an alphabet $ Λ = \{a, b, c\}$, I have the following grammar:

$$ S -> aSb | aAb $$ $$ A -> aaA | aBb $$ $$ B -> Bbb | c $$

Which method should I use to write the definition of the language?

  • $\begingroup$ What do you mean by "write"? The generated language is defined by the semantics of formal grammars; check that definition. $\endgroup$ – Raphael Jan 29 '17 at 22:34
  • $\begingroup$ I mean "write the definition of the language", there are no other meanings. From the definition of a language you can write a grammar that generates that language. I need the opposite task, from a grammar to the definition of its language. $\endgroup$ – emaph Jan 30 '17 at 11:39
  • $\begingroup$ $L(G)$ is a definition of the language. $\endgroup$ – Raphael Jan 30 '17 at 12:50
  • $\begingroup$ I needed a definition like this: $ L = \{a^naa^{2m}acb^{2p}bbb^n | n, m, p ≥ 0\}$ $\endgroup$ – emaph Feb 1 '17 at 12:17

This one is very simple because it has a very downward flow to it. For example, $S$ has non-terminals $S$ and $A$, and once you go to $A$, you can never get back to $S$. So we use this fact to just work through incrementally.

Our language started with $a^nXb^n$ for S where X is some other language, then we got to A and get $a^n(aa)^mXb^n$, then finally $a^n(aa)^{m+1}c(bb)^sb^{n+1}=a^{n+2m+1}cb^{n+2s+1}$ where $n,m,s \in \mathbb{N} \setminus{0}$

| cite | improve this answer | |

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.