Regular expression

Question

S -> AaB

A -> aC | $\epsilon$

B -> aB | bB | $\epsilon$

C -> aCb | $\epsilon$

Is the regular expression for the above is this:

a(a + b)* a ( a* + b* )*  ?

Comments

@Pratik Gawali

even non regular grammar can generate regular language

and the above grammar generate regular language whose corresponding regular expression is $a(a+b)^∗$

---

@joshi_nitish Yes, you are right.

Regular Grammar always generate Regular Language. However, Non-Regular Language may or may not generate Regular Language. In this case a non-regular grammar is generating a regular language.

From the grammar, it is clear that the expression that can be generated is of the form (a(aⁿbⁿ)+ ϵ)a(a+b)* . But I am not able to understand how is it equivalent to a(a+b)*?

---

yes can be a(a+b)*

first element of the string always be a

and then u can generate any string

Answer 1

It should be (a(a+b)*)+a(a^nb^n)

because here minimum one "a" is must and by the production B we will get all string of "a and b"

But at the same time by the production C we will get string in a and b will be equal.

Comments

(a+b)*can also generate strings having equal number of a's and b's