Ullman Exercise

Question

What language is generated by the following grammer?

S→ a | S+S | SS | S* |  (S)

Answer 1

for writing regular expression . we need three operator like 

• Union: If R1 and R2 are regular expressions, then R1 | R2 (also written as R1 U R2 or R1 + R2) is also a regular expression.
• Concatenation: If R1 and R2 are regular expressions, then R1.R2 (also written as R1.R2) is also a regular expression.

• Kleene closure: If R1 is a regular expression, then R1* (the Kleene closure of R1) is also a regular expression.

so this grammar is converting into regular expression.

​​​​​​​

​​​​​​​

Comments

yes.. thank u...
but one silly question.. ( S ).. what does this imply in regular expression?

---

it is just a bracket.

we can genrate regular expression like (aa+aaa)*.

---

But this grammar is ambiguous? Can it be regular?

---

kirtipurohit yes, this is ambiguous grammar.