it will be, $a(a+b)^*$

The Gateway to Computer Science Excellence

0 votes

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* )*` ?

0

@rajatmyname

your's expression is generating minimum length string as 'aaba' (i.e 4), but above grammar is generating smallest string as 'a'

your's expression is generating minimum length string as 'aaba' (i.e 4), but above grammar is generating smallest string as 'a'

0

The given grammar is not a regular grammar because S and C does not follow the rule of right linear grammar. Instead the grammar is Context Free Grammar. So Regular Expression in not possible for the language generated by given grammar.

0

@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)^∗$

even non regular grammar can generate regular language

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

0

@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^{n}b^{n})+ *ϵ*)a(a+b)* . But I am not able to understand how is it equivalent to a(a+b)*?

52,217 questions

59,906 answers

201,095 comments

118,144 users