Describe the formal language over the alphabet { a,b,c } generated by the context-free grammar whose non-terminals are 〈 S 〉 and 〈 A 〉 , whose start symbol is 〈 S 〉 , and whose production rules are the following:
(1) 〈 S 〉→ a 〈 S 〉
(2) 〈 S 〉→ b 〈 A 〉
(3) 〈 A 〉→ b 〈 A 〉
(4) 〈 A 〉→ c 〈 A 〉
(5) 〈 A 〉→ c
(6) 〈 S 〉→ a
In other words, describe the structure of the strings generated by this grammar and modify to NORMAL FORM(The normal form pasrt I am struggling with)

  • $\begingroup$ Im confused about how I should write my answer and how to format production rules $\endgroup$ – Sue Jan 22 at 17:45
  • $\begingroup$ I've made some progress, I currently have: { a^n b^m c^p | n >= 0, m >= 0, p >= 0 } , not sure how to format it to mean that b cannot come at the end of a word... how could i do this? $\endgroup$ – Sue Jan 22 at 18:16
  • $\begingroup$ It seems this grammar is even regular, since all rules are of the form non-terminal produces terminal or non-terminal produces terminal followed by non-terminal (this is one of the standard forms of a regular grammar). Given this, try to express the language as a regular expression. $\endgroup$ – MHS Jan 22 at 22:20
  • $\begingroup$ Also your description { a^n b^m c^p | n >= 0, m >= 0, p >= 0 } is not (yet) completely correct. There is a difference between words starting with a letter a and those starting with a letter b and what about the order of letters b and c? $\endgroup$ – MHS Jan 22 at 22:22
  • $\begingroup$ I tried express the language as a regular expression, is this correct? $\endgroup$ – Sue Jan 23 at 9:52

The language is indeed regular and can be described by the regular expression $$ a^+\ \cup\ \ (a^*\cdot\{b,c\}^*\cdot c) $$

Concerning the normal form, you need to specify which normal form you are talking about. For right-regular grammars the most common one requires exactly one terminal on the right-hand side of each rule. This holds for your grammar.

  • $\begingroup$ I'm curious what the little cross means beside the a $\endgroup$ – Sue Jan 23 at 12:19
  • $\begingroup$ It is a plus. A short form for non-empty iteration: $a^+ = a\cdot a^*$. $\endgroup$ – Peter Leupold Jan 23 at 12:31
  • 1
    $\begingroup$ Unfortunately the given regular expression is not completely correct either. E.g. the word bc is in the language but can not be produced from the given regular expression. $\endgroup$ – MHS Jan 24 at 13:56
  • $\begingroup$ Thanks @MHS! I think I have corrected the expression. $\endgroup$ – Peter Leupold Jan 26 at 17:26

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.