0 votes 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* )* ? Theory of Computation theory-of-computation regular-expression + – Tuhin Dutta asked Feb 1, 2018 Tuhin Dutta 1.1k views answer comment Share Follow See all 9 Comments See all 9 9 Comments reply joshi_nitish commented Feb 1, 2018 reply Follow Share it will be, $a(a+b)^*$ 1 votes 1 votes rajatmyname commented Feb 1, 2018 reply Follow Share I think answer will be a(a^nb^n)a(a+b)*/n>=1 1 votes 1 votes joshi_nitish commented Feb 2, 2018 reply Follow Share @rajatmyname your's expression is generating minimum length string as 'aaba' (i.e 4), but above grammar is generating smallest string as 'a' 0 votes 0 votes rajatmyname commented Feb 3, 2018 reply Follow Share You are right. it should be a(a+b)* 0 votes 0 votes student2018 commented Feb 7, 2018 reply Follow Share I think it is (a(anbn)+ epsilon) a(a+b)* for n>=0 0 votes 0 votes Pratik Gawali commented Feb 18, 2018 i edited by Pratik Gawali Feb 18, 2018 reply Follow Share 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 votes 0 votes joshi_nitish commented Feb 19, 2018 reply Follow Share @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)^∗$ 0 votes 0 votes Pratik Gawali commented Feb 19, 2018 reply Follow Share @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(anbn)+ ϵ)a(a+b)* . But I am not able to understand how is it equivalent to a(a+b)*? 0 votes 0 votes srestha commented Feb 19, 2018 reply Follow Share yes can be a(a+b)* first element of the string always be a and then u can generate any string 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes 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. Poonam Gupta 1 answered Feb 13, 2018 Poonam Gupta 1 comment Share Follow See 1 comment See all 1 1 comment reply Sourav_35 commented Jun 1, 2018 reply Follow Share (a+b)*can also generate strings having equal number of a's and b's 0 votes 0 votes Please log in or register to add a comment.