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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,650 questions

56,242 answers

194,288 comments

95,936 users