0

I have a context-free grammar defined: S -> aS, S -> Sb, S -> a

I thouht that correct answer would be: L(G) = {aab}, because: S -> aS -:> aSb -> aab but isn't. Why, and what is correct answer?

Mike
  • 1
  • What about going $a\to aS\to aaS\to aaaS$ first? Maybe some more times... Then doing a lot of $S\to Sb$ on the result. Then finally removing the $S$ from the list to get a final word... Note that $a$ is also a word of the language. Please try more to have a more qualitative question... – dan_fulea Jun 16 '21 at 07:40
  • ok, so far i understand, language is infinite because it can generate a lot of words L(G) = (a^n+1 b^n : n >= 0), or something similar to this? – Mike Jun 16 '21 at 07:49
  • This looks better... Please adjust the question, as it is the guess is definitively false. It is a good idea to use mathjax, https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference, arrows can be better obtained using the latex \to for them. Also, is something like $a^5b^9$ in the language? Try to get closer to the right answer. (A proof would be induction, rather than inspection...) – dan_fulea Jun 16 '21 at 07:55
  • I understand grammar can generate words that contain at least one "a", right? I just don't know how to write it correctly $L(G) = (a^n b^k : n \gt 0, k \ge 0)$ – Mike Jun 16 '21 at 08:05
  • Yes, $L(G) = {\ a^n b^k \ : \ n > 0, k \ge 0\ }$ is the language in a concrete writing! Well done! Welcome to MSE! Please edit the text of the OP to fit the new state of the art, and if there is still a question, write it. (It is clear that any word of the shape $a^nb^k$ with $n>0$ can be generated, e.g. via $$S\to Sb\to Sbb\to\dots\to Sb k\to \dots \to a^{n-1}Sb^k\to a^nb^k\ .$$ So one inclusion is clear. It is maybe less obvious to show that only such words are in $L(G)$, the other inclusion. Depending on religion, maths or informatics, one may need or not a proof...) – dan_fulea Jun 16 '21 at 09:22

0 Answers0