0
$\begingroup$

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)

$\endgroup$
8
  • $\begingroup$ Im confused about how I should write my answer and how to format production rules $\endgroup$
    – Sue
    Jan 22 '19 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 '19 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 '19 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 '19 at 22:22
  • $\begingroup$ I tried express the language as a regular expression, is this correct? $\endgroup$
    – Sue
    Jan 23 '19 at 9:52
0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I'm curious what the little cross means beside the a $\endgroup$
    – Sue
    Jan 23 '19 at 12:19
  • $\begingroup$ It is a plus. A short form for non-empty iteration: $a^+ = a\cdot a^*$. $\endgroup$ Jan 23 '19 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 '19 at 13:56
  • $\begingroup$ Thanks @MHS! I think I have corrected the expression. $\endgroup$ Jan 26 '19 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.