search
Log In
0 votes
375 views

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

in Theory of Computation 375 views
1
it will be, $a(a+b)^*$
1
I think answer will be a(a^nb^n)a(a+b)*/n>=1
0
@rajatmyname

your's expression is generating minimum length string as 'aaba' (i.e 4), but above grammar is generating smallest string as 'a'
0
You are right. it should be a(a+b)*
0

I think it is (a(anbn)+ epsilon) a(a+b)* for n>=0

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

0
yes can be a(a+b)*

first element of the string always be a

and then u can generate any string

1 Answer

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.
0
(a+b)*can also generate strings having equal number of a's and b's

Related questions

0 votes
1 answer
2
116 views
The answer given is none of these !! I think 1’st statement is the correct one, but still want to confirm
asked Jan 16, 2019 in Theory of Computation Nandkishor3939 116 views
0 votes
1 answer
3
567 views
which one of the following regular expression describe the language over {a,b} consist of no pair of consecutive a’s? a. (b*abb*) (a+€) b. (b+ab)* (a+€) c. (b*abb*)*(a+€)+b* d. (b*ab*)*(a+€)+b*(a+€)
asked Dec 28, 2018 in Theory of Computation Ram Swaroop 567 views
0 votes
0 answers
4
278 views
I tried applying a method where we write equation as state with incoming transition on given dfa - q1 = $\epsilon$ + bq1+bq2 q2 = aq1+aq2 but then able to reach till this conclusion only: q2 = ab*+aq2+abq2b* How to solve further? Here q1 is a start state.
asked Oct 24, 2018 in Theory of Computation Swapnil Naik 278 views
...