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.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 486
- Exam Queries 435
- Tier 1 Placement Questions 18
- Job Queries 56
- Projects 9

36,161 questions

43,620 answers

124,003 comments

42,880 users