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

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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.6k
- Engineering Mathematics 7.5k
- Digital Logic 3k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2.1k
- Databases 4.2k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 585
- Exam Queries 572
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,126 questions

53,249 answers

184,749 comments

70,496 users