in Theory of Computation retagged by
1,546 views
0 votes
0 votes
in Theory of Computation retagged by
by
1.5k views

3 Comments

ba can’t be generated by (a*b*) .
1
1
no,(a*b*)* will be substitute for this
0
0
both are not equal. $(a+b)^*$ can generate $ba,aba….$ but $(a^*b^*)$ not generated such strings.
2
2

1 Answer

0 votes
0 votes

(a,b)* is actually you have written in “easier to write for self understanding“ notation type way of representing “reg Language “ in which comma is understood as union ,although it is generally not seen in ToC and programming . A “union” can be represented using square brackets “[]”  like [a-z] or using 
$\cup$ or using “+”  like (a+b) , according to the use and the convention.
in regex, whereas “,” is just a comma

[a-z] a very famous regex (programming) , means at-least 1 literal from “a or b or or ….z” ,which is quite similar to (a+b+...+z) in ToC

A reg language can be represented in Grammar form or DFA or NFA or e-NFA or in Regex .


Now in terms of ToC, 

(a+b)* means any number of times either a or b or nothing :  $\epsilon$ , a , aa… , aaa...b  ,  b , bb , bbb …… , bbb…..a , ab ,ba , aa..b… , b...aa…. , likewise
(a*b*)* means any number of times a , followed by any number of times b  : a , aa… , aaa...b  ,  b , bb , bbb …… , bbb…..a , ab , but not ba or b...a…

{a,b}*  , means language(or universal language)  over the set of alphabets {a,b} , ={ $\epsilon$ , a , aa… , aaa...b  ,  b , bb , bbb …… , bbb…..a , ab ,ba , aa..b… , b...aa…. } = $\Sigma^1$ $\cup$ $\Sigma^2$ $\cup$ $\Sigma^3$ $\cup$... $\Sigma^5$ $\cup$ ….

Check the brackets and the operators carefully.
(a+b)* $\neq$ (a*b*) $\neq$ {a,b}*
but ,

(a*b*) $\subset$ (a+b)* $\subset$ {a,b}*

Also , (a*b*)  $\neq$ (a*b*)*  , but (a*b*) $\subset$ (a*b*)*

also , (a+b)*  =  (a*b*)*

edited by

Related questions