The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
23 views
Is there any difference in (a + b)* and a*b* ?

If yes then what is the language generated by this ?
asked in Theory of Computation by (287 points) | 23 views
+1

yes they are different!

$(a+b)^{*}$ can generate ba,baba,abab while $a^{*}b^{*}$ can't generate!

1 Answer

+1 vote
Yes there is Difference in them ..

Have a look at 1st (a+b)* means ...we can have "aaabbbaaa" or "aba" that is after b we can have a again in 1st language..

but when it comes to 2nd language ... a*b* = here once b has occured there is no way we can have occurance of a .. so "aabbaa" is not allowed in 2nd language ...

(a+b)*=(a*b*)* but  a*b* is not equal to (a*b*)*
answered by Boss (10.5k points)
0
Can you please give me the DFA for both the expressions?
0
(a+b)* ====> universal language ===> δ ( A ,a ) = δ ( A , b ) = A where A is final state and initial state

 

a* . b*  ===> δ ( A ,a ) =A, δ ( A , b ) = B and δ ( B , b ) = B but δ ( B , a ) = DS where A and B are final states and A is initial state

Related questions

0 votes
1 answer
5
asked Nov 3 in Theory of Computation by Na462 Loyal (7.4k points) | 42 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,071 questions
49,594 answers
162,952 comments
65,785 users