Formal Languages - Context Free Grammar

184 Views Asked by At

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)

1

There are 1 best solutions below

4
On

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.