# Formal Languages - Context Free Grammar

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)

• Im confused about how I should write my answer and how to format production rules – Sue Jan 22 at 17:45
• 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? – Sue Jan 22 at 18:16
• 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. – MHS Jan 22 at 22:20
• 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? – MHS Jan 22 at 22:22
• I tried express the language as a regular expression, is this correct? – 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)$$
• It is a plus. A short form for non-empty iteration: $a^+ = a\cdot a^*$. – Peter Leupold Jan 23 at 12:31