The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
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 (251 points) | 20 views

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 Loyal (8.7k points)
Can you please give me the DFA for both the expressions?
(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
0 answers
asked Jul 26 in Theory of Computation by Deepalitrapti (227 points) | 58 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

38,203 questions
45,703 answers
49,751 users